Cfrtjryk

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

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.

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

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.