Euclid's first three postulates are the basis of compass and straight edge constructions which are as complex as arithmetic.

The constructions themselves may be expressed as a formula with each of the six operations of addition, subtraction, multiplication, division, complex conjugate, and square root corresponding to a simple compass and straight edge construction.

Q1Do Gödel's incompleteness theorems apply in the feild of Compass-and-straight edge-constructions ?

Q2Do we have any problems in compass and straight edge constructions which haveneither been constructed nor proved impossible, and may just be un-decidable ?

The question asked nearly two months back here on maths.SE got many opinions but no answers.>

The opinions ranged from addition of new postulates to Tarski's Elementary Geometry (in order to make it inconsistent) to finding a (weak) subset of Peano Arithmetic which can be encoded as a statement in Euclidean Geometry.

**EDIT**

We talk of statements such as

- $\mathcal construct$ regular $(2^{2^n}+1)$-gon :
**undecided; maybe undecidable**( taken from a comment by @AngelaRichardson, based on Gauss–Wantzel theorem) - $\mathcal construct$ regular n-gon :
**decidable; True** - $\mathcal construct$ trisection of angle $\theta$:
**decidable; False**(Is this how you classify impossible constructions)

**Motivation was to introduce undecideability without a direct referance to arithmatic** not withstanding the fact that each of the above bullets would have an equivalent arithmetical statement with the same decideability status;

constructability here may take into account the decideability of the equivalent arithmetical statement or the Construction itself based, maybe , on a decision routine for Tarski's Elementary geometry].

Besides geometry, dynamical systems is another field which can be used to state decidability problems ; of course the essential language remains that of arithmetic but the context changes. ( Decidability in dynamical systems )

isundecidable: michaelbeeson.com/research/papers/Ziegler.pdf $\endgroup$ – Emil Jeřábek Sep 13 '13 at 13:10