Term for "uncheckable constructions"

Question

Is there a term for "uncheckable geometric constructions"?

Say, Angle Trisection and Doubling the Cube are checkable; i.e., if the answer is given one can do finite Compass-and-straightedge construction which checks that this is a right answer. (We assume that we can see if two points coincide.)

On the other hand Squaring the Circle is not checkable --- there is no way to say "yes" by performing a finite Compass-and-straightedge construction.

Similarly one can not check that a given point is a center of given circle by straightedge only. (Here I assume that straightedge can not draw infinite lines, so one can not check whether two lines are parallel.)

Answer 1

Your question amounts to treating construction problems in geometry as decision problems, and so it makes sense to me to adopt the terminology of computability theory. This same kind of distinction arises in computability theory, where we have the following terminology:

• A set $A$ is decidable if we can computably verify yes-or-no whether a given input $a$ is in $A$ or not.
• A set $A$ is semi-decidable if we can computably verify positive instances of $a\in A$.
• A set $A$ is co-semi-decidable if we can computably verify negative instances, that is, instances where $a\notin A$. (that is, the complement is semi-decidable)

This might at first suggest the terminology of

• semi-constructible, if you can constructibly verify positive instances, and
• co-semi-constructible if you can constructibly verify failing instances.

But actually, since what you have is explicitly a decision problem---namely, given this geometrical configuration, is it acceptable?---I find it natural to use the terminology:

• constructibly decidable: if you can constructibly verify yes-or-no.
• constructibly semi-decidable: if you can constructibly verify positive instances. (or: constructibly verifiable)
• constructibly co-semi-decidable: if you can constructibly verify negative instances. (or: constructibly co-verifiable)

This raises the question: is every constructibly decidable construction problem also constructible? As Anton notes in the comments, the answer is no, because the angle trisection problem is both constructibly semi-decidable and constructibly co-semi-decidable (and hence constructibly decidable), but not constructible.

So these are the interesting situations for which you can decide yes-or-no correctly in every instance whether a proposed solution to a construction is correct or not, but you cannot produce the solution constructibly. This phenomenon does not arise in classical computability theory, because of our ability there to computably enumerate the entire domain---in the context of the natural numbers, we can just keep trying every single number in order until we hit upon the "Yes" answer in order to find it. But in geometry, we cannot constructibly enumerate the entire (uncountable) space.

The same phenomenon arises in infinitary computability theory, where we have the lost-melody phenomenon, which occurs when there is an infinity binary string $c$ such that one can computably verify (in the infinitary sense) whether a given infinite string $x$ is equal to $c$ or not, but there is no infinitary computable procedure to produce $c$ from scratch. The "lost-melody" idea is that these are like the song that you know well enough to say, "yes, that's it!" or "no, that isn't it", but you cannot sing it on your own. The lost-melody phenomenon is known to occur in several distinct infinitary contexts, where we are not able computably to enumerate the domain.

Let me finish by mentioning that it would seem very natural to explore the analogues of P and NP in geometry. For example, a geometric construction problem would be constructibly P, if there is a construcible decision procedure taking suitably few steps (like polynomial time). It would be constructibly NP, if an input is acceptable just in case there are a (suitably few) extra points that can be added, such that the whole configuration can now be verified in (suitably few) steps.

Answer 2

Quick claims about Joel's definition:

Constructibly decidable, semi-decidable, and co-semi-decidable are identical for constructions which, like most classic geometric constructions, take bounded numbers of steps. (By the same proof that those decidable, semi-decidable, and co-semi-decidable are identical with a bound on the computation time.)

A constructible semi-decidable problem is exactly a countable disjunction of bounded constructible decision problems, and similarly for co-semi-decidable and conjunction. (Assuming there is no computably criterion in the definition of a geometric construction that takes unbounded time.)

We can classify the constructibly decidable in bounded time problems using the Euclidean geometry - algebra correspondence. Representing each point by a pair of numbers, any geometric input can be represented as a tuple of numbers. The constructible functions are exactly the compositions of rational functions and square roots.

To get a yes-or-no value rather than a number as the result of our computations, we need a test. We can test whether two points are equal, so we can test equality, and we can test whether a line is on a circle, so we can test inequality.

Any finite decision procedure is thus described by a logical combination of formulas where you take a function generated by rational functions and square roots and test whether it is positive. Such a decision procedure is clearly a first-order statement in the theory of real closed fields (if we take a real closure of our number line). By quantifier elimination, every first-order statement in the theory of real closed fields is given by a decision procedure, and you don't need to mess with square roots.

So a constructibly decidable problem is a partition of $\mathbb R^n$ into two sets, each a countable union of first order definable sets.

Need such a partition be a partition into two first order definable sets? No. For instance the set of real numbers whose integer part is even is a countable union of the intervals $[2n,2n+1)$, which are first order definable, but it is not definable, and similarly for its complement.