Euclidean geometry in terms of automata theory. (English) Zbl 0678.68055

Summary: The two abstract automata \(GCM_ 0\) and \(A\)-GCM\({}_ 0\) are introduced. A \(GCM_ 0\) is a machine whose primitives are the basic euclidean operations with compass and ruler. It is shown tht some elementary geometric problems can indeed by solved by a \(GCM_ 0\)-algorithm. On the other hand, our definition of \(GCM_ 0\)-constructible functions is so restrictive that not even the perpendicular projection of any arbitrary point \(t\in {\mathbb{E}}^ 2\) onto the x-axis can be \(GCM_ 0\)-constructed. Therefore, the \(A\)-GCM\({}_ 0\) is introduced which has the additional capability to execute jumps under the condition that some x is in A. We shall give a general class of oracle sets A which yield a real extension of the class of constructible functions, and we shall consider another large class of oracles which do not. The last of our theorems deals with a uniform time bound of different constructions effected by nondeterministic \(GCM_ 0\)-operations.


68Q45 Formal languages and automata
51M05 Euclidean geometries (general) and generalizations
Full Text: DOI


[1] Engeler, E., Metamathematik der elementarmathematik, (1983), Springer Berlin · Zbl 0515.03001
[2] Euklid, Die elemente, (1980), Wissenschaftliche Buchgesellschaft Darmstadt, Translation by Clements Thaer · JFM 63.0799.04
[3] Eves, H., A survey of geometry, (1972), Allyn and Bacon Boston · Zbl 0132.14105
[4] Huckenbeck, U., Geometrische maschinenmodelle, () · Zbl 0642.68102
[5] Huckenbeck, U., Geometrical abstract automata, (), 217-231, Würzberg
[6] Lemoine, E.; Lemoine, E., Mésure de la simplicité dans LES constructions mathématiques, Mathesis, Mathesis, 8, 241-244, (1888) · JFM 20.0537.02
[7] Noltemeier, H., Informatik I: einführung in algorithmen und berechenbarkeit, (1981), Hanser Verlag Berlin · Zbl 0477.68002
[8] Preparata, F.P.; Shamos, M.I., Computational geometry, an introduction, (1985), Springer New York · Zbl 0575.68059
[9] Schreiber, P., Grundlagen der konstruktiven geometrie, (1934), VEB Verlag der Wissenschaften Berlin · Zbl 0534.51001
[10] Shamos, M.I., Geometric complexity, Proc. 7th ACM symp. on the theory of computing, 224-233, (1975)
[11] Shamos, M.I., Computational geometry, () · Zbl 0759.68037
[12] Tietze, H., Über die konstruierbarkeit mit lineal und zirkel, Sitzungsber. kaiserl. akad. wiss. wien math. naturw. kl., 118, 735-757, (1909), (Abteilung IIa) · JFM 40.0548.05
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.