Term for "uncheckable constructions" 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.)
 A: 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.
A: 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.
