9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ The non-deterministic variant was so efficient, that it could decide any problem in NP in polynomial time! $\endgroup$
    – einpoklum
    Dec 23, 2018 at 9:37

6 Answers 6

Reset to default
61
$\begingroup$

"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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Jasmijn
    Dec 20, 2018 at 16:05
  • $\begingroup$ @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. $\endgroup$
    – JimmyJames
    Dec 20, 2018 at 19:19
  • $\begingroup$ @Robin Good call! Added a footnote about that. $\endgroup$
    – Draconis
    Dec 21, 2018 at 1:58
  • 7
    $\begingroup$ @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. $\endgroup$
    – Sasho Nikolov
    Dec 21, 2018 at 3:47
  • $\begingroup$ @SashoNikolov You are correct sir. Thanks for the clarification/correction. $\endgroup$
    – JimmyJames
    Dec 21, 2018 at 14:56
18
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Barmar
    Dec 20, 2018 at 22:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    Dec 20, 2018 at 22:45
  • $\begingroup$ Maybe better suited as a comment on the OP's question? $\endgroup$
    – AnoE
    Dec 23, 2018 at 1:14
  • $\begingroup$ @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.) $\endgroup$
    – John L.
    Dec 23, 2018 at 2:45
  • $\begingroup$ 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 ...). $\endgroup$
    – AnoE
    Dec 23, 2018 at 10:29
8
$\begingroup$

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).

Improve this answer
$\endgroup$
1
3
$\begingroup$

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.

Improve this answer
$\endgroup$
17
  • 6
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Dec 20, 2018 at 0:29
  • 2
    $\begingroup$ @Pilpel I don't think he actually built anything. Turing was a pure mathematician and worked solely on paper. $\endgroup$
    – xuq01
    Dec 20, 2018 at 1:02
  • 2
    $\begingroup$ @xuq01 <s>Of course, so did his machines.</s> $\endgroup$
    – Draconis
    Dec 20, 2018 at 6:44
  • 2
    $\begingroup$ 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 $\endgroup$
    – allo
    Dec 20, 2018 at 13:27
  • 3
    $\begingroup$ @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”. $\endgroup$
    – Konrad Rudolph
    Dec 20, 2018 at 13:38
0
$\begingroup$

Here is a video with a real Turing machine working. Its quite nice and helped me to stop seeing it as a mere mathematical model:

https://www.youtube.com/watch?v=E3keLeMwfHY

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.