Is classical Euclidean geometry Turing complete?
$begingroup$
By "classical Euclidean geometry" I don't mean the study of $mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $mathbb R^2$ that are invariant under the group of rigid motions a la Klein's Erlangen Programme. I mean the geometry of Euclid's Elements, in which lines and points are taken as primitives, and in which postulates corresponding to the operation of a compass and (unmarked) straightedge enable the production of additional lines and/or points from a given configuration of lines and/or points.
As is well-known, in this geometry there are certain things that can be constructed, and other things that can't be. You can bisect any angle, and you can partition any segment into an arbitrary number of congruent segments, but you can't trisect an arbitrary angle. You can dissect any polygon and square with an equal area, but you can't do the same thing with a circle. You can construct two segments whose ratios are equal to $sqrt n$ for any natural number $n$, but you can't construct two segments whose ratios are equal to $sqrt[3] 2$.
With this as background, I am wondering whether it is possible to replicate the operation of an abstract Turing machine using only compass and straightedge operations. For example Euclidean constructions take place in an unbounded "canvas", and Postulate 2 says that you can extend any line segment and make it longer, so there doesn't seem to be any problem constructing a "memory tape". Likewise it doesn't seem that it would be all that difficult to "write" on the memory tape by, for example, constructing perpendicular segments at various points along the tape.
The real question is whether there's some way to translate any algorithm $A$ that can be executed by a TM into some kind of compass-and-straightedge construction $C$, so that given an initial configuration of points and lines, executing $C$ would produce a result that would be equivalent (in some sense) to running $A$.
(The fact that an idealized compass-and-straightedge construction works with segments whose lengths correspond to real numbers suggests that such constructions can actually do more than a TM, but that is a different issue.)
Is it known whether Euclidean geometry is Turing complete, in the sense described above? References would be appreciated.
euclidean-geometry computer-science computability turing-machines geometric-construction
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
$endgroup$
add a comment |
$begingroup$
By "classical Euclidean geometry" I don't mean the study of $mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $mathbb R^2$ that are invariant under the group of rigid motions a la Klein's Erlangen Programme. I mean the geometry of Euclid's Elements, in which lines and points are taken as primitives, and in which postulates corresponding to the operation of a compass and (unmarked) straightedge enable the production of additional lines and/or points from a given configuration of lines and/or points.
As is well-known, in this geometry there are certain things that can be constructed, and other things that can't be. You can bisect any angle, and you can partition any segment into an arbitrary number of congruent segments, but you can't trisect an arbitrary angle. You can dissect any polygon and square with an equal area, but you can't do the same thing with a circle. You can construct two segments whose ratios are equal to $sqrt n$ for any natural number $n$, but you can't construct two segments whose ratios are equal to $sqrt[3] 2$.
With this as background, I am wondering whether it is possible to replicate the operation of an abstract Turing machine using only compass and straightedge operations. For example Euclidean constructions take place in an unbounded "canvas", and Postulate 2 says that you can extend any line segment and make it longer, so there doesn't seem to be any problem constructing a "memory tape". Likewise it doesn't seem that it would be all that difficult to "write" on the memory tape by, for example, constructing perpendicular segments at various points along the tape.
The real question is whether there's some way to translate any algorithm $A$ that can be executed by a TM into some kind of compass-and-straightedge construction $C$, so that given an initial configuration of points and lines, executing $C$ would produce a result that would be equivalent (in some sense) to running $A$.
(The fact that an idealized compass-and-straightedge construction works with segments whose lengths correspond to real numbers suggests that such constructions can actually do more than a TM, but that is a different issue.)
Is it known whether Euclidean geometry is Turing complete, in the sense described above? References would be appreciated.
euclidean-geometry computer-science computability turing-machines geometric-construction
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
$endgroup$
$begingroup$
You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual.
$endgroup$
– user3482749
Jan 16 at 22:02
$begingroup$
This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly?
$endgroup$
– Eric Wofsey
Jan 16 at 22:04
$begingroup$
@EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not?
$endgroup$
– mweiss
Jan 16 at 22:15
add a comment |
$begingroup$
By "classical Euclidean geometry" I don't mean the study of $mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $mathbb R^2$ that are invariant under the group of rigid motions a la Klein's Erlangen Programme. I mean the geometry of Euclid's Elements, in which lines and points are taken as primitives, and in which postulates corresponding to the operation of a compass and (unmarked) straightedge enable the production of additional lines and/or points from a given configuration of lines and/or points.
As is well-known, in this geometry there are certain things that can be constructed, and other things that can't be. You can bisect any angle, and you can partition any segment into an arbitrary number of congruent segments, but you can't trisect an arbitrary angle. You can dissect any polygon and square with an equal area, but you can't do the same thing with a circle. You can construct two segments whose ratios are equal to $sqrt n$ for any natural number $n$, but you can't construct two segments whose ratios are equal to $sqrt[3] 2$.
With this as background, I am wondering whether it is possible to replicate the operation of an abstract Turing machine using only compass and straightedge operations. For example Euclidean constructions take place in an unbounded "canvas", and Postulate 2 says that you can extend any line segment and make it longer, so there doesn't seem to be any problem constructing a "memory tape". Likewise it doesn't seem that it would be all that difficult to "write" on the memory tape by, for example, constructing perpendicular segments at various points along the tape.
The real question is whether there's some way to translate any algorithm $A$ that can be executed by a TM into some kind of compass-and-straightedge construction $C$, so that given an initial configuration of points and lines, executing $C$ would produce a result that would be equivalent (in some sense) to running $A$.
(The fact that an idealized compass-and-straightedge construction works with segments whose lengths correspond to real numbers suggests that such constructions can actually do more than a TM, but that is a different issue.)
Is it known whether Euclidean geometry is Turing complete, in the sense described above? References would be appreciated.
euclidean-geometry computer-science computability turing-machines geometric-construction
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
$endgroup$
By "classical Euclidean geometry" I don't mean the study of $mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $mathbb R^2$ that are invariant under the group of rigid motions a la Klein's Erlangen Programme. I mean the geometry of Euclid's Elements, in which lines and points are taken as primitives, and in which postulates corresponding to the operation of a compass and (unmarked) straightedge enable the production of additional lines and/or points from a given configuration of lines and/or points.
As is well-known, in this geometry there are certain things that can be constructed, and other things that can't be. You can bisect any angle, and you can partition any segment into an arbitrary number of congruent segments, but you can't trisect an arbitrary angle. You can dissect any polygon and square with an equal area, but you can't do the same thing with a circle. You can construct two segments whose ratios are equal to $sqrt n$ for any natural number $n$, but you can't construct two segments whose ratios are equal to $sqrt[3] 2$.
With this as background, I am wondering whether it is possible to replicate the operation of an abstract Turing machine using only compass and straightedge operations. For example Euclidean constructions take place in an unbounded "canvas", and Postulate 2 says that you can extend any line segment and make it longer, so there doesn't seem to be any problem constructing a "memory tape". Likewise it doesn't seem that it would be all that difficult to "write" on the memory tape by, for example, constructing perpendicular segments at various points along the tape.
The real question is whether there's some way to translate any algorithm $A$ that can be executed by a TM into some kind of compass-and-straightedge construction $C$, so that given an initial configuration of points and lines, executing $C$ would produce a result that would be equivalent (in some sense) to running $A$.
(The fact that an idealized compass-and-straightedge construction works with segments whose lengths correspond to real numbers suggests that such constructions can actually do more than a TM, but that is a different issue.)
Is it known whether Euclidean geometry is Turing complete, in the sense described above? References would be appreciated.
euclidean-geometry computer-science computability turing-machines geometric-construction
euclidean-geometry computer-science computability turing-machines geometric-construction
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
asked Jan 16 at 21:55
mweissmweiss
17.6k23370
17.6k23370
$begingroup$
You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual.
$endgroup$
– user3482749
Jan 16 at 22:02
$begingroup$
This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly?
$endgroup$
– Eric Wofsey
Jan 16 at 22:04
$begingroup$
@EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not?
$endgroup$
– mweiss
Jan 16 at 22:15
add a comment |
$begingroup$
You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual.
$endgroup$
– user3482749
Jan 16 at 22:02
$begingroup$
This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly?
$endgroup$
– Eric Wofsey
Jan 16 at 22:04
$begingroup$
@EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not?
$endgroup$
– mweiss
Jan 16 at 22:15
$begingroup$
You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual.
$endgroup$
– user3482749
Jan 16 at 22:02
$begingroup$
You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual.
$endgroup$
– user3482749
Jan 16 at 22:02
$begingroup$
This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly?
$endgroup$
– Eric Wofsey
Jan 16 at 22:04
$begingroup$
This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly?
$endgroup$
– Eric Wofsey
Jan 16 at 22:04
$begingroup$
@EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not?
$endgroup$
– mweiss
Jan 16 at 22:15
$begingroup$
@EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not?
$endgroup$
– mweiss
Jan 16 at 22:15
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076343%2fis-classical-euclidean-geometry-turing-complete%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076343%2fis-classical-euclidean-geometry-turing-complete%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
You could just make your "symbols" stacks of unit squares: you can trivially construct those in Euclidean geometry, and then just define your "execution" to be treating those as symbols on a tape and executing as usual.
$endgroup$
– user3482749
Jan 16 at 22:02
$begingroup$
This seems poorly defined. What counts as a "compass-and-straightedge construction", exactly?
$endgroup$
– Eric Wofsey
Jan 16 at 22:04
$begingroup$
@EricWofsey indeed part of what I am hoping to get from this is to see if anyone can define it more sharply as part of their answer, because I don't know exactly how to. Euclid's constructions don't include branches (if this, do that, otherwise this) which seems like something you would need to have, but maybe not?
$endgroup$
– mweiss
Jan 16 at 22:15