6
$\begingroup$

By "classical Euclidean geometry" I don't mean the study of $\mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $\mathbb R^2$ that are invariant under the group of rigid motions a la Klein's Erlangen Programme. I mean the geometry of Euclid's Elements, in which lines and points are taken as primitives, and in which postulates corresponding to the operation of a compass and (unmarked) straightedge enable the production of additional lines and/or points from a given configuration of lines and/or points.

As is well-known, in this geometry there are certain things that can be constructed, and other things that can't be. You can bisect any angle, and you can partition any segment into an arbitrary number of congruent segments, but you can't trisect an arbitrary angle. You can dissect any polygon and reassemble it into a square with an equal area, but you can't do the same thing with a circle. You can construct two segments whose ratios are equal to $\sqrt n$ for any natural number $n$, but you can't construct two segments whose ratios are equal to $\sqrt[3] 2$.

With this as background, I am wondering whether it is possible to replicate the operation of an abstract Turing machine using only compass and straightedge operations. For example Euclidean constructions take place in an unbounded "canvas", and Postulate 2 says that you can extend any line segment and make it longer, so there doesn't seem to be any problem constructing a "memory tape". Likewise it doesn't seem that it would be all that difficult to "write" on the memory tape by, for example, constructing perpendicular segments at various points along the tape.

The real question is whether there's some way to translate any algorithm $A$ that can be executed by a TM into some kind of compass-and-straightedge construction $C$, so that given an initial configuration of points and lines, executing $C$ would produce a result that would be equivalent (in some sense) to running $A$.

(The fact that an idealized compass-and-straightedge construction works with segments whose lengths correspond to real numbers suggests that such constructions can actually do more than a TM, but that is a different issue.)

Is it known whether Euclidean geometry is Turing complete, in the sense described above? References would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual. $\endgroup$ – user3482749 Jan 16 at 22:02
  • 1
    $\begingroup$ This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly? $\endgroup$ – Eric Wofsey Jan 16 at 22:04
  • $\begingroup$ @EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not? $\endgroup$ – mweiss Jan 16 at 22:15
  • 2
    $\begingroup$ Your question allows trivial answers, and it is not easy to rule them out. You can simply draw symbols (that are constructible) like a Turing machine yourself. $\endgroup$ – Trebor Apr 4 at 16:08
3
+50
$\begingroup$

Your question seems too unclear to be answerable, but let me say a 'few' things. Firstly, you said that the ability for compass-and-straightedge constructions to handle segments whose lengths are real numbers suggests that it can do more than TMs. That is certainly a misconception. Even if the input is provided as a finite initial configuration of points, all points you can construct from it in finite time are computable from the initial configuration. Adding lines and circles to the initial configuration changes nothing, because each line or circle can be represented by two points.

For reference, a computable real is a real number $r$ for which there is a program $p$ such that $p(k)$ (halts and) outputs a rational number (under any reasonable encoding) that is at most $2^{-k}$ away from $r$. We shall say that this $p$ is a program for $r$, and note that there are infinitely many programs for each real number. Observe that we can pass a computable real around in a program just by passing a program for it. But we cannot computably test equality between two computable reals (since that is equivalent to solving the halting problem).

An oracle for a real number $r$ is an object that can be called as a program for $r$. This definition allows us to talk about computing things from input reals even if the inputs are not computable reals. In particular, we say that a function $f : \mathbb{R}^n→\mathbb{R}$ is computable iff there is a program $q$ such that given any oracles $i[1..n]$ for reals $r[1..n]$ we have that $q(i[1..n])$ outputs a program for $f(r[1..n])$ relative to $i[1..n]$, meaning that the output may make calls to $i[1..n]$.

So when we say that points constructible from a finite initial configuration are computable from the initial configuration, we mean that if the initial configuration comprises two points $O,I$ and a fixed number $n$ of other points, then the function that maps each input $2n$-tuple of coordinates of those $n$ points, treating $O$ as origin and $I$ as $(1,0)$, to each coordinate of the constructed point is a computable function from $\mathbb{R}^{2n}→\mathbb{R}$.

Even if you use a program(!) to determine what geometric operations to do (where a variable can store either an integer or a point or a finite tuple of points, and at each step you can either perform a basic integer/tuple operation or perform a geometric operation involving point variables or output a point), the output sequence of points is still computable (a sequence is encoded as a program $s$ where $s(k)$ is the $k$-th term in the sequence) from the input configuration! In other words, using compass-and-straightedge constructions to manipulate lengths adds absolutely nothing in terms of computability.

Secondly, it is impossible to perform conditional branching if you don't have it in some form. If all you have is a finite sequence of instructions with no possibility of changing execution path based on the current state, then you cannot even perform a for-loop, much less a while-loop. So you do need to allow it somehow in your geometric 'machine' if you ever want it to compute more than a fixed function composed from arithmetic and square-roots.

So until you specify what exactly your geometric computation model is, it is simply an ill-defined question to ask whether it is Turing-complete. But if you wish to ask for a geometry-based kind of programs, perhaps what I had described above will do the job. Note that it is basically the same as the standard notion of oracle programs except that oracles are given as points (in relation to $O,I$).

If you want to replace the integer operations by geometric operations, you need to encode each integer variable as a point. Well, you can encode $n$ as the point $(n,0)$, then you can easily perform addition, subtraction and multiplication. But you cannot perform jump-on-zero (which is one possible sufficient primitive for conditional branching) without literally adding something like it, such as testing whether a point $P$ encoding an integer is closer to $O$ than $I$.

Once you do so, then clearly the resulting computation model is Turing-complete if we encode the input integer as the point $P$ (with respect to $O,I$ as above), since any program can be translated to an equivalent 'geometric program' which permits:

  • Intersection of lines $AB,CD$ given points $A,B,C,D$.
  • Intersection of circles given by their centres and a point on each.
  • Jump to specific instruction if a specified point is closer to $O$ than $I$.

And the output can be recovered from a single point designated by the program after running it on the initial configuration $O,I,P$.

As explained above, we only need the jump-if-closer operation for points encoding integers. But what if we allow it for points in general? It turns out that with restricted initial configuration (i.e. only integer input), the general jump-if-closer operation is actually computable, because RCF is decidable, and we can compute a defining property over RCF for each point when constructing it.

However, the full model (i.e. with arbitrary input) is stronger than Turing-computability, in that the output may be uncomputable even given the input as oracles, for the same reason we cannot computably compare two reals given as oracles.

This raises the question of what exactly this computation model computes. Well, we still cannot solve the halting problem, because there is no way we can obtain the entire execution of a given program on a given input as a single point, even idealistically, without essentially also knowing its halting behaviour.

If I am not mistaken, this computation model computes exactly what can be computed with an oracle that can determine whether any given expression involving the inputs and only arithmetic or square-roots is zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.