5
$\begingroup$

Hello,

I am looking for a discussion on computability and algorithms in relation to geometric constructions.

Does anyone know if the subject has been treated from the viewpoint of elementary euclidean geometry (ex. ruler and compass constructibility)?

Thank you

Davide

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This paper of Pippenger's is often cited in this context, but I haven't read it myself: "Computational complexity in algebraic function fields," 1979. portal.acm.org/citation.cfm?id=1382433.1382606 $\endgroup$
    – Joseph O'Rourke
    Commented Jul 5, 2010 at 15:55
  • $\begingroup$ I once asked T. Y. Lam a related question, he was firm in saying there is no canonical form possible for numbers in the "constructible numbers," meaning the smallest field extension of the rationals such that the square root of any positive element is also in the field. $\endgroup$
    – Will Jagy
    Commented Jul 5, 2010 at 18:50
  • 1
    $\begingroup$ @Will Jagy: Do you know what Lam meant? Here's a weak version. Let $E$ be the set of expressions for constructible numbers (you can use rational numbers, arithmetic operations, and square roots; no division by zero or square roots of negative numbers), and let $e : E \to \mathbb{R}$ be the evaluation map. Then we want a computable function $f : E \to E$ such that for $\alpha,\beta in E$, we have $e(\alpha) = e(\beta)$ if and only if $f(\alpha) = f(\beta)$, and $f(f(\alpha)) = f(\alpha)$. Such a function does exist, but I imagine Lam meant there's no canonical choice of canonical form? $\endgroup$
    – Henry Cohn
    Commented Sep 2, 2011 at 13:00

3 Answers 3

Reset to default
5
$\begingroup$

I personally like this elegant but somewhat obscure (relatively) recent paper by Alekhnovich and Belov (MR1866477; Russian version is downloadable; it was written while Misha was still in Moscow). Enjoy!

Improve this answer
$\endgroup$
0
4
$\begingroup$

Tarski's theorem on real-closed fields shows that there is a decision procedure to compute the truth or falsity of any first-order statement in the real closed field $\langle\mathbb{R},+,\cdot,\lt,0,1\rangle$, which includes via Cartesian geometry many of the usual concepts of Euclidean geometry and more. For example, this language is expressive enough to speak of circles, lines, paraboloids, and so on, real algebraic equations in any finite dimension, the $n$-dimensional metric, concepts of bounded or unbounded solution sets and so on. Tarski's algorithm provably determines the truth of any statement expressible in this language, even when these statements involve complex alternations of quantifiers (for every circle, there are three lines such that for every parabola of a certain kind and so on...), which in other contexts often cause undecidability.

Unfortunately, the set of integers is not definable in this language (since this would immediate refute decidability by allowing the halting problem to be expressed), and it follows that Tarski's theorem does not apply very well to questions about algorithms, which is the main focus of your question, since one seems to need the integers to express concepts of iterating a procedure, a central consideration with algorithms.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Tarski's theorem doesn't address ruler and compass constructability, if that was the original question, since it allows for more general algebraic equations. $\endgroup$
    – Peter Shor
    Commented Jul 5, 2010 at 22:13
  • $\begingroup$ Given this answer, I can recommend "Old and New Results in the Foundations of Elementary Plane Euclidean and Non-Euclidean Geometries" by Marvin Jay Greenberg, the M.A.A.'s American Mathematical Monthly, March 2010, vol. 117, no. 3, pages 198-219; especially references to works of one Victor Pambuccian. If people cannot find it I have a pdf. I know from my own work that one can prove something is constructible with compass and straightedge while having no clue of how to go about it in practice. $\endgroup$
    – Will Jagy
    Commented Jul 5, 2010 at 22:33
  • $\begingroup$ Peter, it doesn't matter that Tarski's theorem allows for greater expressibility, since his decision algorithm works even for the weaker cases. For example, it seems to me that for any fixed number $k$, the relation "$z$ is consructible by ruler-and-compass from $w$, $x$ and $y$ in $k$ steps or less" is expressible in the language of real-closed fields. So Tarski's theorem provides a decision procedure for all such statements. One could easily also allow more complex construction methods, as long as they were algebraic. What does not seem to be expressible are questions that quantify over $k$. $\endgroup$
    – Joel David Hamkins
    Commented Jul 6, 2010 at 0:02
1
$\begingroup$

You might want to look at George Stiny's Shape: Talking about Seeing and Doing (MIT Press, 2006) and Dominic Widdows's Geometry and Meaning (CSLI Publications, 2004).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .