The first Turing machine
Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.
turing-machines
New contributor
add a comment |
Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.
turing-machines
New contributor
The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time!
– einpoklum
2 days ago
add a comment |
Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.
turing-machines
New contributor
Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.
turing-machines
turing-machines
New contributor
New contributor
New contributor
asked Dec 20 at 0:00
Pilpel
14912
14912
New contributor
New contributor
The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time!
– einpoklum
2 days ago
add a comment |
The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time!
– einpoklum
2 days ago
The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time!
– einpoklum
2 days ago
The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time!
– einpoklum
2 days ago
add a comment |
5 Answers
5
active
oldest
votes
"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:
- Writing proofs about physical wires and switches is extremely difficult.
- Writing proofs about Turing machines is (relatively) easy.
- Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).
But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
5
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
add a comment |
Turing never built a physical Turing machine. The point of Turing machines was not to be a practical physical computer but to formalize what it's possible to compute and, indeed, to formalize what "computation" even means.
add a comment |
Let me bring some serious fun, although it might not be the wanted answer.
Claim One: Lots of Turing machines have been built, by Alan Turing and by many others.
Proof. Pointing to an immovable bolt in a bombe, Alan Turing said with his usual keen insight and simplicity, "look, a Turing machine that halts upon any given input".
Moral: There are many kinds of Turing machines. Many of them are extremely simple. But they are (functionally) Turing machines.
Claim Two: It is undecidable whether a machine has unbounded memory.
Proof. I have a computing machine, for which it will take one second to demonstrate each additional bit of memory. I want to convince you that it does not have unbounded memory. However, being a cautious positivist, you insists that nobody can reject that it has unbounded memory in any time soon or even forever.
Moral: be careful when we are talking about objects that expand on demand.
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
1
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
|
show 2 more comments
This is a perfect place and time to referr to the actual paper where the Turing machine is first described. One link is here:
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Of course, he is more modest, so he calls it the "automatic machine". There is no actual machine, only a beast of imagination.
Turing, as far as we know, never even tried to build the "automatic machine". He was however extremely influential in making a number of other machines. The WW2 bombe, used to break Nazi Germany ziphers, is the most famous example.
Sadly, it was first well after his death that the general public was made aware of his achievements. (He killed himself it is said, after beeing brutally subjected to chemical sterilization as beeing a convicted homosexual).
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
add a comment |
The TM only exists on paper. It is a theoretical model of computation. It actually can't be built (because the tape is infinitely long).
So, the answer is: no, Turing never built a TM in real life, because he can't.
Please do not keep arguing that "we can build a Turing machine, just that it doesn't have infinite tape, because by definition a TM has an infinitely long tape. If it does not have an infinitely long tape, then it is not a Turing machine. It is as simple as that.
I am fully aware that people have built "TMs with finite tapes" and neither am I doubting the usefulness of that (i.e. bounded automata): in fact, given an long enough tape, we can compute basically all practically interesting things (that are Turing computable). But for every natural number $n$, there will be a TM that would necessarily require a tape of length $n+1$ to simulate, so there's never a "large enough" tape. (Think why.)
Setting a step back, there are easily TMs we can't build or evem simulate with finite resources. Take the TM which writes one * on its first step, goes right and writes two *s on its second step, etc. This TM can not be built or even simulated without an infinite amount of memory.
6
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
2
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
2
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
2
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
3
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
|
show 10 more comments
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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Pilpel is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f101812%2fthe-first-turing-machine%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:
- Writing proofs about physical wires and switches is extremely difficult.
- Writing proofs about Turing machines is (relatively) easy.
- Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).
But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
5
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
add a comment |
"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:
- Writing proofs about physical wires and switches is extremely difficult.
- Writing proofs about Turing machines is (relatively) easy.
- Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).
But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
5
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
add a comment |
"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:
- Writing proofs about physical wires and switches is extremely difficult.
- Writing proofs about Turing machines is (relatively) easy.
- Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).
But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.
"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:
- Writing proofs about physical wires and switches is extremely difficult.
- Writing proofs about Turing machines is (relatively) easy.
- Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).
But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.
edited Dec 21 at 1:58
answered Dec 20 at 0:32
Draconis
3,515615
3,515615
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
5
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
add a comment |
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
5
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
I'm pretty sure the computer Turing was writing proofs about, referred to people following fixed instructions: en.wikipedia.org/wiki/Human_computer (the second footnote). Writing proofs about humans following instructions is very hard because people can in principle follow arbitrary instructions.
– Robin
Dec 20 at 16:05
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin For historical completeness, Turing developed the Turing machine to prove that (his teacher) Alonzo Church's lamba-calculus was a universal model of computation. He achieved this by proving that it was true for Turing machines and then proving that the Turing machine was equivalent to the lambda-calculus.
– JimmyJames
Dec 20 at 19:19
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
@Robin Good call! Added a footnote about that.
– Draconis
Dec 21 at 1:58
5
5
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@JimmyJames I don't think that's accurate. Turing's solution to Entscheidungsproblem was independent of Church's and before he became a student of Church. Church published his proof slightly earlier and when Turing heard of it, he rushed to finish writing his results. He included a proof of the equivalence of his machines and lambda calculus in response to Church's paper, but this was not his initial goal.
– Sasho Nikolov
Dec 21 at 3:47
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
@SashoNikolov You are correct sir. Thanks for the clarification/correction.
– JimmyJames
Dec 21 at 14:56
add a comment |
Turing never built a physical Turing machine. The point of Turing machines was not to be a practical physical computer but to formalize what it's possible to compute and, indeed, to formalize what "computation" even means.
add a comment |
Turing never built a physical Turing machine. The point of Turing machines was not to be a practical physical computer but to formalize what it's possible to compute and, indeed, to formalize what "computation" even means.
add a comment |
Turing never built a physical Turing machine. The point of Turing machines was not to be a practical physical computer but to formalize what it's possible to compute and, indeed, to formalize what "computation" even means.
Turing never built a physical Turing machine. The point of Turing machines was not to be a practical physical computer but to formalize what it's possible to compute and, indeed, to formalize what "computation" even means.
answered Dec 20 at 0:31
David Richerby
65.8k15100190
65.8k15100190
add a comment |
add a comment |
Let me bring some serious fun, although it might not be the wanted answer.
Claim One: Lots of Turing machines have been built, by Alan Turing and by many others.
Proof. Pointing to an immovable bolt in a bombe, Alan Turing said with his usual keen insight and simplicity, "look, a Turing machine that halts upon any given input".
Moral: There are many kinds of Turing machines. Many of them are extremely simple. But they are (functionally) Turing machines.
Claim Two: It is undecidable whether a machine has unbounded memory.
Proof. I have a computing machine, for which it will take one second to demonstrate each additional bit of memory. I want to convince you that it does not have unbounded memory. However, being a cautious positivist, you insists that nobody can reject that it has unbounded memory in any time soon or even forever.
Moral: be careful when we are talking about objects that expand on demand.
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
1
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
|
show 2 more comments
Let me bring some serious fun, although it might not be the wanted answer.
Claim One: Lots of Turing machines have been built, by Alan Turing and by many others.
Proof. Pointing to an immovable bolt in a bombe, Alan Turing said with his usual keen insight and simplicity, "look, a Turing machine that halts upon any given input".
Moral: There are many kinds of Turing machines. Many of them are extremely simple. But they are (functionally) Turing machines.
Claim Two: It is undecidable whether a machine has unbounded memory.
Proof. I have a computing machine, for which it will take one second to demonstrate each additional bit of memory. I want to convince you that it does not have unbounded memory. However, being a cautious positivist, you insists that nobody can reject that it has unbounded memory in any time soon or even forever.
Moral: be careful when we are talking about objects that expand on demand.
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
1
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
|
show 2 more comments
Let me bring some serious fun, although it might not be the wanted answer.
Claim One: Lots of Turing machines have been built, by Alan Turing and by many others.
Proof. Pointing to an immovable bolt in a bombe, Alan Turing said with his usual keen insight and simplicity, "look, a Turing machine that halts upon any given input".
Moral: There are many kinds of Turing machines. Many of them are extremely simple. But they are (functionally) Turing machines.
Claim Two: It is undecidable whether a machine has unbounded memory.
Proof. I have a computing machine, for which it will take one second to demonstrate each additional bit of memory. I want to convince you that it does not have unbounded memory. However, being a cautious positivist, you insists that nobody can reject that it has unbounded memory in any time soon or even forever.
Moral: be careful when we are talking about objects that expand on demand.
Let me bring some serious fun, although it might not be the wanted answer.
Claim One: Lots of Turing machines have been built, by Alan Turing and by many others.
Proof. Pointing to an immovable bolt in a bombe, Alan Turing said with his usual keen insight and simplicity, "look, a Turing machine that halts upon any given input".
Moral: There are many kinds of Turing machines. Many of them are extremely simple. But they are (functionally) Turing machines.
Claim Two: It is undecidable whether a machine has unbounded memory.
Proof. I have a computing machine, for which it will take one second to demonstrate each additional bit of memory. I want to convince you that it does not have unbounded memory. However, being a cautious positivist, you insists that nobody can reject that it has unbounded memory in any time soon or even forever.
Moral: be careful when we are talking about objects that expand on demand.
edited Dec 20 at 9:23
answered Dec 20 at 0:51
Apass.Jack
6,6811533
6,6811533
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
1
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
|
show 2 more comments
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
1
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
That first example sounds apocryphal, do you have a citation? And even if he did say it, it seems like he was speaking metaphorically, since a TM contains a tape holding the data. Of course, the TM itself is a metaphor, since it's a conceptual device, not a physical one.
– Barmar
Dec 20 at 22:17
1
1
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
The first proof/example might be more true than the second proof/example. Had I had a more relevant citation than the bombe, I would have used it. Alan Turing is known for inspecting a comprehensive list of computing machines, from the simplest to the most exotic ones (such as human mind). He reduced the most complicated and powerful ones (without oracle) to the simplest model possible. The first example is a new anecdote to pay tribute to the enlightenment he brought to us.
– Apass.Jack
Dec 20 at 22:45
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
Maybe better suited as a comment on the OP's question?
– AnoE
Dec 23 at 1:14
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
@AnoE, your suggestion makes sense. On the other hand, had I written as comments on the OP's question, it might look less appropriate than a standalone answer. In fact, my answer also pointed out, implicitly in a roundabout way, that Alan Turing had not built a physical Turing machine in its strict interpretation. The first claim just emphasized the fact that Turing machines are ubiquitous. (I was and am contemplating another claim that shows the pervasiveness of Turing-complete machines as well, which would make this being comment even less appealing.)
– Apass.Jack
Dec 23 at 2:45
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
If I may suggest, you might be more specific about "there are many kinds of TMs". A "TM" is the specific thing with the head, the tape and the symbols. The other machines are equivalent to that, but not the same. A code cracker is certainly not a TM, albeit it being equivalent in computing capability. OP is seemingly not asking whether Turing built a computer, but whether he built an actual TM (with a reading/writing head, band ...).
– AnoE
2 days ago
|
show 2 more comments
This is a perfect place and time to referr to the actual paper where the Turing machine is first described. One link is here:
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Of course, he is more modest, so he calls it the "automatic machine". There is no actual machine, only a beast of imagination.
Turing, as far as we know, never even tried to build the "automatic machine". He was however extremely influential in making a number of other machines. The WW2 bombe, used to break Nazi Germany ziphers, is the most famous example.
Sadly, it was first well after his death that the general public was made aware of his achievements. (He killed himself it is said, after beeing brutally subjected to chemical sterilization as beeing a convicted homosexual).
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
add a comment |
This is a perfect place and time to referr to the actual paper where the Turing machine is first described. One link is here:
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Of course, he is more modest, so he calls it the "automatic machine". There is no actual machine, only a beast of imagination.
Turing, as far as we know, never even tried to build the "automatic machine". He was however extremely influential in making a number of other machines. The WW2 bombe, used to break Nazi Germany ziphers, is the most famous example.
Sadly, it was first well after his death that the general public was made aware of his achievements. (He killed himself it is said, after beeing brutally subjected to chemical sterilization as beeing a convicted homosexual).
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
add a comment |
This is a perfect place and time to referr to the actual paper where the Turing machine is first described. One link is here:
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Of course, he is more modest, so he calls it the "automatic machine". There is no actual machine, only a beast of imagination.
Turing, as far as we know, never even tried to build the "automatic machine". He was however extremely influential in making a number of other machines. The WW2 bombe, used to break Nazi Germany ziphers, is the most famous example.
Sadly, it was first well after his death that the general public was made aware of his achievements. (He killed himself it is said, after beeing brutally subjected to chemical sterilization as beeing a convicted homosexual).
This is a perfect place and time to referr to the actual paper where the Turing machine is first described. One link is here:
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Of course, he is more modest, so he calls it the "automatic machine". There is no actual machine, only a beast of imagination.
Turing, as far as we know, never even tried to build the "automatic machine". He was however extremely influential in making a number of other machines. The WW2 bombe, used to break Nazi Germany ziphers, is the most famous example.
Sadly, it was first well after his death that the general public was made aware of his achievements. (He killed himself it is said, after beeing brutally subjected to chemical sterilization as beeing a convicted homosexual).
answered Dec 20 at 21:05
ghellquist
2714
2714
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
add a comment |
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
There is a more accessible explanation he wrote I found, I've been hosting a mirror of it as it was kind of hard to find: "Turing, Alan M. (1936), On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Ser. 2-42, 230-265." Linking to it now reminds me that the online Turing Machine simulator link I put there in 2005 is very dated (Java!), wonder what a good replacement link would be.
– HostileFork
Dec 22 at 14:33
add a comment |
The TM only exists on paper. It is a theoretical model of computation. It actually can't be built (because the tape is infinitely long).
So, the answer is: no, Turing never built a TM in real life, because he can't.
Please do not keep arguing that "we can build a Turing machine, just that it doesn't have infinite tape, because by definition a TM has an infinitely long tape. If it does not have an infinitely long tape, then it is not a Turing machine. It is as simple as that.
I am fully aware that people have built "TMs with finite tapes" and neither am I doubting the usefulness of that (i.e. bounded automata): in fact, given an long enough tape, we can compute basically all practically interesting things (that are Turing computable). But for every natural number $n$, there will be a TM that would necessarily require a tape of length $n+1$ to simulate, so there's never a "large enough" tape. (Think why.)
Setting a step back, there are easily TMs we can't build or evem simulate with finite resources. Take the TM which writes one * on its first step, goes right and writes two *s on its second step, etc. This TM can not be built or even simulated without an infinite amount of memory.
6
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
2
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
2
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
2
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
3
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
|
show 10 more comments
The TM only exists on paper. It is a theoretical model of computation. It actually can't be built (because the tape is infinitely long).
So, the answer is: no, Turing never built a TM in real life, because he can't.
Please do not keep arguing that "we can build a Turing machine, just that it doesn't have infinite tape, because by definition a TM has an infinitely long tape. If it does not have an infinitely long tape, then it is not a Turing machine. It is as simple as that.
I am fully aware that people have built "TMs with finite tapes" and neither am I doubting the usefulness of that (i.e. bounded automata): in fact, given an long enough tape, we can compute basically all practically interesting things (that are Turing computable). But for every natural number $n$, there will be a TM that would necessarily require a tape of length $n+1$ to simulate, so there's never a "large enough" tape. (Think why.)
Setting a step back, there are easily TMs we can't build or evem simulate with finite resources. Take the TM which writes one * on its first step, goes right and writes two *s on its second step, etc. This TM can not be built or even simulated without an infinite amount of memory.
6
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
2
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
2
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
2
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
3
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
|
show 10 more comments
The TM only exists on paper. It is a theoretical model of computation. It actually can't be built (because the tape is infinitely long).
So, the answer is: no, Turing never built a TM in real life, because he can't.
Please do not keep arguing that "we can build a Turing machine, just that it doesn't have infinite tape, because by definition a TM has an infinitely long tape. If it does not have an infinitely long tape, then it is not a Turing machine. It is as simple as that.
I am fully aware that people have built "TMs with finite tapes" and neither am I doubting the usefulness of that (i.e. bounded automata): in fact, given an long enough tape, we can compute basically all practically interesting things (that are Turing computable). But for every natural number $n$, there will be a TM that would necessarily require a tape of length $n+1$ to simulate, so there's never a "large enough" tape. (Think why.)
Setting a step back, there are easily TMs we can't build or evem simulate with finite resources. Take the TM which writes one * on its first step, goes right and writes two *s on its second step, etc. This TM can not be built or even simulated without an infinite amount of memory.
The TM only exists on paper. It is a theoretical model of computation. It actually can't be built (because the tape is infinitely long).
So, the answer is: no, Turing never built a TM in real life, because he can't.
Please do not keep arguing that "we can build a Turing machine, just that it doesn't have infinite tape, because by definition a TM has an infinitely long tape. If it does not have an infinitely long tape, then it is not a Turing machine. It is as simple as that.
I am fully aware that people have built "TMs with finite tapes" and neither am I doubting the usefulness of that (i.e. bounded automata): in fact, given an long enough tape, we can compute basically all practically interesting things (that are Turing computable). But for every natural number $n$, there will be a TM that would necessarily require a tape of length $n+1$ to simulate, so there's never a "large enough" tape. (Think why.)
Setting a step back, there are easily TMs we can't build or evem simulate with finite resources. Take the TM which writes one * on its first step, goes right and writes two *s on its second step, etc. This TM can not be built or even simulated without an infinite amount of memory.
edited Dec 21 at 10:26
answered Dec 20 at 0:08
xuq01
985513
985513
6
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
2
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
2
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
2
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
3
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
|
show 10 more comments
6
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
2
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
2
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
2
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
3
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
6
6
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
It's perfectly possible to build a Turing machine. The tape doesn't need to be infinitely long: you just need to add some more every time the machine reaches the end.
– David Richerby
Dec 20 at 0:29
2
2
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
@Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper.
– xuq01
Dec 20 at 1:02
2
2
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
@xuq01 <s>Of course, so did his machines.</s>
– Draconis
Dec 20 at 6:44
2
2
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
There are real turing machines, except that they do not have unlimited memory (and thus can only compute a limited set of programs and input values). See this amazing video of a real turing machine: youtube.com/watch?v=E3keLeMwfHY
– allo
Dec 20 at 13:27
3
3
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
@Pilpel The most notable actual device Turing built was the bombe, which is not a universal computing machine, and fairly unrelated to what we call “Turing machine”.
– Konrad Rudolph
Dec 20 at 13:38
|
show 10 more comments
Pilpel is a new contributor. Be nice, and check out our Code of Conduct.
Pilpel is a new contributor. Be nice, and check out our Code of Conduct.
Pilpel is a new contributor. Be nice, and check out our Code of Conduct.
Pilpel is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fcs.stackexchange.com%2fquestions%2f101812%2fthe-first-turing-machine%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
The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time!
– einpoklum
2 days ago