Undecidable “Elementary” Geometry
According to Augustus De Morgan (quoted in A Long Way from Euclid by Constance Reid):
What distinguishes the straight line and circle more than anything else, and properly separates them for the purpose of elementary geometry? Their self-similarity, Every inch of a straight line coincides with every other inch, and of a circle with every other of the same circle. Where, then, did Euclid fail? In not introducing the third curve which has the same property—the screw. The right line, the circle, the screw—the representation of translation, rotation, and the two combined—ought to have been the instruments of geometry. With a screw we should never have heard of the impossibility of trisecting an angle, squaring a circle, etc.In some ways, the elementary geometry of points, lines, and circles is radically different from elementary geometry including screws. The former is decidable, a fact also covered in A Long Way from Euclid. (Betweeness and congruence can be expressed in terms of lines and circles and vice versa.) The latter, on the other hand, is undecidable. It includes a model for the Peano Axioms: The points on one side of a given point in the intersection of a line and a screw.
This is probably well-known but I haven't seen it anywhere …
Addendum: Mícheál Mac an Airchinnigh had some speculations along these lines over a decade ago:
It seems reasonable to put forward the working hypothesis that there is a geometry of curves which is computationally equivalent to a Turing Machine. Such a geometry of curves we call GeometriaOn the other hand, the following claim differs from my result:
One might consider trying to construct geometrical equivalents to essential programming features. For example, it seems reasonable that the spiral ought to correspond to the loop.In my construction, spirals are more analogous to counters.