How to square the circle using only a straightedge, compass, pencil, eraser, and Turing machine

🎙️ obsidian_golem · 32 points · Posted at 03:00:35 on April 20, 2018 · (Permalink)

Just to be clear, the comic is a joke. I considered whether to post it on /r/math, but figured that it was more relevant here. Sadly enough, this seems like something someone could honestly do.

I_regret_my_name · 34 points · Posted at 03:21:51 on April 20, 2018 · (Permalink)

There's always /r/shittymath for intentionally bad math. It's not as popular, though.

AngelTC · 9 points · Posted at 05:00:10 on April 20, 2018 · (Permalink)

Its my favorite math sub, tho

ResidentNileist · 1 points · Posted at 19:22:09 on April 20, 2018 · (Permalink)

You’re my favorite math sub.

ForgettableWorse · 2 points · Posted at 08:09:45 on April 23, 2018 · (Permalink)

Who's your favorite math dom?

yoshiK · 10 points · Posted at 13:58:10 on April 20, 2018 · (Permalink)

Somebody who actually knows something about field extensions should check my argument, but I believe that since infinite precision arithmetic is equivalent to a Turing oracle, you can't square the circle using compass, straight edge and an computer.

[deleted] · 6 points · Posted at 20:47:29 on April 20, 2018 · (Permalink)

I'm pretty sure that arbitrary infinite precision arithmetic is at least a Turing jump past computable, but I'm not sure about what happens if we just declare that we have "all of pi's digits at once". Seems likely to be outside the realm of computable but I don't see a proof right away.

yoshiK · 1 points · Posted at 22:28:20 on April 20, 2018 · (Permalink)

That's not the problem I had in mind, but I think it is the right question. (I hadn't thought about how we get the result from the computer back into the Euclidean plane and turns out that made the problem I thought about appears ill defined.)

[deleted] · 1 points · Posted at 23:37:32 on April 20, 2018 · (Permalink)

There's a reason we care about PSPACE and EXPSPACE and all that

yoshiK · 1 points · Posted at 12:32:19 on April 21, 2018 · (Permalink)*

Yes, but that was not my confusion.

In the diagram, C are the constructible numbers, [;<l_{1}, +, \cdot, \dots >;] is the space of almost all zero integer sequences with some additional algebraic structure s.t. [;f;] is an isomorphism. On the upper right we have the constructible numbers with [;\sqrt{\pi};] added,¹ there we can square the circle, and there is an obvious embedding [;i;], the top arrow.

Now [;a;], left lower arrow, adds an additional dimension to the computational representation of the constructible numbers, such that we have [;<l_{1} \oplus <\sqrt{\pi}>, \dots>;] and from there we have an imbedding into the reals [;g;] and a bijection into our target space of the extended "constructible numbers." Now [;j=h \circ g;] (I know.) is a bijection, but as I would formalize the question "can we square the circle with compass, straight edge and computer?", is if [;j;] is computable. Clearly the "digits of pi" oracle gives us that [;g;] is computable, and I guess [;h;] should also be computable, in fact I would claim that [;h;] is just the identity, but is [;g;] computable without such an oracle?

¹ And all the other stuff we need to add, like [;1+\sqrt{\pi};], I should probably have called that [;span<C \cup \{\sqrt{\pi}\}>;].

imguralbumbot · 1 points · Posted at 12:32:24 on April 21, 2018 · (Permalink)

^{Hi, I'm a bot for linking direct images of albums with only 1 image}

https://i.imgur.com/wTnBYkQ.png

^{^Source} ^{^|} ^{^Why?} ^{^|} ^{^Creator} ^{^|} ^{^ignoreme} ^{^|} ^{^deletthis}

[deleted] · 1 points · Posted at 00:45:07 on April 26, 2018 · (Permalink)

Wait, are you sure? Like what the impossibility of squaring the circle means is that the existence of such a square is not entailed by the usual compass-and-straightedge axioms of geometry, right? But if we pretend that we can just make a universal computer, then don't we automatically have a language for describing any mathematical idea? In particular, within the Turing machine, surely we could talk about domain of discourse where such a square can be proven to exist, right? E.g., R^2.

Or put another way, my interpretation of the joke is that it's saying that since we have a pencil and paper, we can construct any geometric object whose definition we can encode with pencil and paper. (This is the same as the more formal Turing machine implementation because of the Church-Turing thesis, right?)

[deleted] · 2 points · Posted at 22:11:53 on April 26, 2018 · (Permalink)

A computer (whatever model of Turing machine you want) cannot compute infinite precision, it can only compute arbitrarily large finite precision. Put another way: a computer (without an oracle) cannot ever actually calculate the totality of pi. We can encode it of course, but that doesn't let us do infinite precision arithmetic with it.

[deleted] · 1 points · Posted at 13:01:41 on April 28, 2018 · (Permalink)*

Well, if we're using positional notation, sure, but that's not necessary for squaring the circle, right? Like, aren't we merely "encoding" literally every number?

Why can't we just do all our arithmetic in Q(sqrt(pi))? That is, the infinite-dimensional field extension of the rationals (or some other number field if that's more convenient) extended by the square root of pi. We can do basic arithmetic there. (We can even easily impose a total ordering on it, right? Since we can calculate pi with arbitrarily large rational precision?) Why would that represntation "count" any less than encoding Q as (the subset of N^\inf of eventually repeating sequences (modulo the appropriate equivalence relation to take care of infinite sequences of 9's))?

To the point of the joke---the axioms of geometry don't entail the existence of a square with the same area as a given circle. The axioms of R² do. So given a computer, can't we reasonably talk about the latter?

(note that none of these questions are rhetorical. i don't know much about any of this, and the very little I do know i am very confused about.)

Number154 · 1 points · Posted at 14:34:35 on April 20, 2018 · (Permalink)*

A number is constructible by straightedge and compass if and only if it’s an algebraic number such that the order of the Galois group of its splitting field is a power of 2. Equivalently, it can be written starting with 1 and using the operations of addition, subtraction, multiplication, division by nonzero numbers, and taking the square root. You could easily store expressions of this form on a computer and unless I’m making a mistake the equality relation seems to be decidable, because of minimal polynomials.

Of course, it’s not obvious how the computational power of the computer will help in actually performing the constructions themselves, if it’s just doing calculations. We could suppose the straightedge and compass were controlled by any kind of oracle but that wouldn’t change the possible constructions (of course, writing on the straightedge violates the rules of the idealized straightedge and compass, this seems to be a neusis construction).

eario · 2 points · Posted at 16:19:22 on April 25, 2018 · (Permalink)

A number is constructible by straightedge and compass if and only if it’s an algebraic number with degree a power of 2

I think you´re using slightly non-standard terminology. Usually the "degree of an algebraic number" refers to the degree of the minimal polynomial of the algebraic number (that´s the definition I know, and the one on the "Algebraic number" page of wikipedia), but in your statement the "degree of an algebraic number" refers to the dimension of the splitting field of its minimal polynomial.

For example a root of X⁴ -X-1 would usually be called an algebraic number of degree 4, but such a root cannot be constructed using straight edge and compass, because the dimension of the splitting field of X⁴ -X-1 is 24.

But that´s just a minor nitpick.

Number154 · 1 points · Posted at 16:58:46 on April 25, 2018 · (Permalink)

Whoops you’re right. I was being careless. I’ll edit my comment just in case anyone might be misled.

yoshiK · 1 points · Posted at 15:20:08 on April 20, 2018 · (Permalink)*

If I am not mistaken, then your first paragraph is equivalent to setting up the 2 dimensional vector space over [;\mathbb{Q}[\sqrt{\pi}];] and then fixing the points I just left out, such that it contains the constructible numbers, at which point we no longer need the compass and straight edge. However, I think that you get into trouble if you want to decide [;x\in\mathbb{Q}, x > \sqrt{\pi};], that is if you want to construct the topology of the constructible points.

[deleted] · 1 points · Posted at 17:33:15 on April 20, 2018 · (Permalink)

can you translate what you mean by that last line?

yoshiK · 2 points · Posted at 18:12:44 on April 20, 2018 · (Permalink)

As I think about it, you are constructing ordered sets of integers [;(a,b, c, d, \dots)\to a/b+c/d \cdot \sqrt{\pi} +... ;]. It is then non trivial to decide if one point is larger than another, because [;\sqrt{\pi};] here plays the role of a symbol and you need the value [;\sqrt{\pi} \in \mathbb{R};] to decide if [; (0, 1, 1, 1, 0, \dots)= \sqrt{\pi} > (x_1, x_2, 0, 1, 0, \dots)=x;]. However the Turing machine can not do that, because I can find an [;x\in \mathbb{Q};] close enough to exhaust it's precision.

[deleted] · 2 points · Posted at 18:18:09 on April 20, 2018 · (Permalink)

oh! thank you for the explanation!

it is sad that turing machines have precision

Number154 · 1 points · Posted at 19:09:03 on April 20, 2018 · (Permalink)

I’m not sure I follow, it sounds like you’re saying a Turing machine can’t decide the equality of two expressions built up from the rationals and pi using field operations and square roots? If I understand correctly I don’t think that’s right. For any number constructible from Q(pi) we can find the minimal polynomial with coefficients in Q(pi). We can check whether members of Q(pi) are equal because pi is transcendental so we know the only polynomial in pi equal to 0 is the zero polynomial, so checking the equality of rational functions of pi is just checking the equality of formal polynomials in Q[X]. Once we’ve determined whether two numbers constructible from pi have the same minimal polynomial we can find the roots to sufficiently good precision to distinguish them from each other, because pi is computable and there are only finitely many roots.

Sorry if I misunderstand what you’re saying completely.

yoshiK · 1 points · Posted at 20:07:50 on April 20, 2018 · (Permalink)

No, I meant the ordering of the constructible numbers as a subset of the reals, for a given x, I want to know wether that x > pi. And I think that one could run out of precision there.

(To a certain extend, one could probably argue that we do not need a topology on the constructible numbers, but I think squaring the circle is basically a geometric notion, so we should be able to talk about shapes.)

Number154 · 1 points · Posted at 20:24:25 on April 20, 2018 · (Permalink)

Maybe I’m confused because pi is not constructible so if we assume it’s constructible we can get weird results. We know a constructible number is computable and not equal to pi so if you calculate it to increasingly good precision you will eventually confine it to an interval that separates it from pi (and therefore also reveals it to be either less than or greater than pi if it is real). Even if you can’t put a simple bound on how long it takes (not sure if you can off the top off my head) we know it will happen eventually. And if we consider pi given and consider numbers constructible from that starting point, we can compute the order for two elements by first checking for equality as I described above and then separating them by neighborhood if we determine they are not equal.

Either way the claim in the comic isn’t right (I mean, duh, it’s a joke) because having a computer doesn’t help. We know that no sequence of constructions will make pi so having a computer pick the constructions doesn’t help.

yoshiK · 1 points · Posted at 21:34:53 on April 20, 2018 · (Permalink)

Well, my claim is, even if we add a computer to straight edge and compass, then in the deformed constructible numbers we could not square the circle. My intuition about the problem is, that we can introduce a symbol sqrt(pi) but there is no obvious way to place it on the real line. (And I conjecture that this placement is not computable.)

yoshiK · 1 points · Posted at 12:37:48 on April 21, 2018 · (Permalink)*

In the diagram

, C are the constructible numbers, [;<l_1, +, \cdot, \dots >;] is the space of almost all zero integer sequences with some additional algebraic structure s.t. [;f;] is an isomorphism. On the upper right we have the constructible numbers with [;\sqrt{\pi};] added,1 there we can square the circle, and there is an obvious embedding [;i;], the top arrow.

Now [;a;], left lower arrow, adds an additional dimension to the computational representation of the constructible numbers, such that we have [;<l_1 \oplus <\sqrt{\pi}>, \dots>;] and from there we have an imbedding into the reals [;g;] and a bijection into our target space of the extended "constructible numbers."

Your claim is, that the computer does not help us because you are thinking about [;i\circ f^{-1};], and the argument is, we are going through [;C;] so we can't reach [;\sqrt{\pi};], and of course I agree.

Now [;j=h \circ g;] (I know.) is a bijection, but as I would formalize the question "can we square the circle with compass, straight edge and computer?", is asking if [;j;] is computable. And my argument is, that [;g;] should not be computable and therefore [;j;] should not be computable.

1 And all the other stuff we need to add, like [;1+\sqrt{\pi};], i should probably have called that [;span<C \cup \{\sqrt{\pi}\}>;].

TheKing01 · 8 points · Posted at 22:56:13 on April 20, 2018 · (Permalink)

The more pressing question is can you solve the halting problem using only a straightedge and compass.

[deleted] · 1 points · Posted at 00:46:42 on April 26, 2018 · (Permalink)

sure you can. hell, you don't even need the compass, or even the straightedge! conservation of energy and the law of entropy means that every algorithm halts! bam, halting problem solved. wonder what all the fuss was about. ^{^{^{^{^{^{^{^{^/s}}}}}}}}