Talk:Turing machine

  1. Home
  2. Wiki

Bad explanation in the second paragraph

[edit]

The second paragraph of this article presently (2017-06-05 16:42ET) talks about the machine moving to a cell, reading it, then writing into it. There is, however, no explanation why it would do so or where is the written content is coming from. The article continues with the mention of the head or tape moving left or right with no clarity as to how the choice of left or right is made. I did not delete the confusing paragraph because it does contain a lot of reference (which I did not follow). However, as it stands it is wrong. — Preceding unsigned comment added by 174.113.207.5 (talk)

Incorrect theoretical understanding corrected

[edit]

regarding the latest revision on this page: Permanent Link

Full disclosure: I'm not an expert (ie I am not professor of computer science) and I haven't cited a source here. This could benefit from a source. I welcome such an addition.

But please do not reverse this change if you are not -- or have not consulted -- an expert (eg professor of computer science).

The key issue here is that this is not just a clarification of a claim but that the previous version included a claim that was exactly counter to well understood theoretical computer science; it refers directly to the very issue that Turing addressed in his (very difficult to read) original pager on this subject but the previous version of this paragraph asserted exactly the opposite of Turing's conclusion: He proved that despite the simplicity of the Universal Turing Machine, no one will ever build a real computer that can out do it. If this seems hard to understand, it is because this claim is not widely understood nor sufficiently appreciated; arguably, Turing's conclusion could be considered another one of the basic principles of Physics alongside Conservation of Energy and similar principles. D wigglesworth (talk) 02:56, 10 November 2024 (UTC)[reply]

Perhaps you would find Wolfgang Maass's "Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines" (STOC 1984) relevant. He shows that there are problems that are easy to compute in linear time on classical random-access machines but that require quadratic time on a Turing machine with a single scratch tape (as well as a separate input tape). For Turing machines that use the same tape for both input and scratch memory the situation is even worse, with even very simple problems like recognizing palindromes requiring quadratic time. And much recent thought on quantum computing suggests that for some problems, the disadvantage of Turing machines relative to quantum computers is much worse. They can simulate everything, but the passage you deleted was not about that, but about the efficiency of the simulation. Your claim that they are as efficient at computing as anything else is clearly and blatantly untrue. —David Eppstein (talk) 03:09, 10 November 2024 (UTC)[reply]
I think I see what you mean. I had not correctly read the emphasis on the words "mechanical" and "in practice" all of which are in the passage I had removed. And so I had completely misunderstood the paragraph.
That is, this paragraph appears to make the point that since Turing's machine is based on "classical" (non-quantum) physics, it is too slow in practice; it cannot efficiently simulate a quantum computer.
But if that is indeed the point (not sure!) then the following line could benefit from some clarifying modification: "their minimalist design makes them too slow"... While it is true that they have a "minimalist design", this point is confusing since, as you point out, they are too slow compared to quantum computers because they are classical, not because they are "minimalist design".
This is particularly confusing since the first line on the page opens with, "A Turing machine is a mathematical model of computation describing an abstract machine..."
And that means that the Turing machine is a mathematical object unconstrained by physical limits and hence even a "classical"-design Turing machine can out do a (physically instantiated) quantum computer.
In fairness, if we are to compare apples to apples -- ie, a physically-unconstrained classical-Physics-design Turing machine to a physically-unconstrained quantum-physics-design Turing machine (a "Deutsch machine"?!) then ... there is no contest; we cannot compare two mathematical objects based on physical performance measures ("efficiency").
I could go on but I think you will agree that there is something awry with the paragraph; no matter how it is interpreted.
Not sure how to correct it! I'm beginning to think the entire page needs an overhaul!
Here is a copy of it for convenient reference:
Turing machines proved the existence of fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalist design makes them too slow for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory. D wigglesworth (talk) 03:35, 10 November 2024 (UTC)[reply]
It's not so much that the Turing machine is slow because it's based on classical physics. It's slow because it has to spend so much time moving the tape head back and forth and can carry very little information at a time from one part of the tape to another as it does so. The random-access machine model is a closer match to how real computers work and to how quickly they work, but for some purposes less amenable to theoretical analysis. —David Eppstein (talk) 05:39, 10 November 2024 (UTC)[reply]

The image titled "A physical Turing machine model."

[edit]

The image titled "A physical Turing machine model." https://en.wikipedia.org/w/index.php?title=Turing_machine&oldid=1261936405

It is my understanding that this is an image of a machine that INTERPRETS a Turing Machine. A Turing Machine is a rectangular array of instructions, sometimes known as a "State Transition Table", I believe that Alan Turing never built any mechanical representation of his Turing Machines.

The article goes on to say "A Turing machine is a mathematical model of computation describing an abstract machine" which to my mind contradicts an image of a tangible machine.

This is a minor edit, but my studies of Turing's work confirm that his "Turing Machines" were ideas to support his mathematical ideas in his 1936 paper. Thanks to Gryllida for support. I hope I've "done this right"! Chris Greaves www.chrisgreaves.com 96.30.182.81 (talk) 18:46, 10 January 2025 (UTC)[reply]

The transition table is analogous to the 'program' that the turing machine runs. The 'Turing Machine' is an abstraction describing the theoretical machine with the linear array of infinite memory with the single head for reading symbols. The picture is of a 'model' of a Turing Machine, which is no more the machine itself than a model of a car is a car. MrOllie (talk) 19:41, 10 January 2025 (UTC)[reply]

Aren't real computers finite state automata?

[edit]

The article says that real computers are linear bounded automata, but as i understand it, the defining feature of a LBA is that its tape size is proportional to the length of its input, which is not the case for most computers. Binarycat64 (talk) 03:29, 18 March 2025 (UTC)[reply]

Machines on the tape of the machine?

[edit]

Apologies if this should file under "Reading Level" above, but the bullet-points in the 3rd paragraph fatally undermined my sense that I was gaining a superficial understanding of the topic's actual definition, which feels like a broader category of imperfection. To wit:

"Does a machine exist that [...] any arbitrary machine on its tape"

I assume that this is how those questions are phrased verbatim, but as a reader lacking the context in which they are posed and only having the preceding paragraphs to go on, this is very confusing. I had got this far taking the "Turing machine" to be the (abstract) apparatus in its entirety: head, tape, everything involved. But what then is the "machine" that is on the tape?

I appreciate what is said above about some background knowledge being expected, but I still feel that within this introductory section of the article it would be useful if these lines could be contextualised with some preamble that helps to deobfuscate the outwardly bewildering phrasing for the sake of the casual reader. Otherwise the actual definition of the subject is left imprecise. ~2025-36276-51 (talk) 14:06, 25 November 2025 (UTC)[reply]

You a perfectly right that this phrasing must be confusing. Thanks for finding this "blind spot" of all article editors.
To understand the phrasing, one has to know the concept of universal Turing machine. It is similar to an interpreter (computing): both take some text file in a certain programming language and execute what the text says. On today's computers, the text file is usually read from the hard disk; on a Turing machine, the text file (written in a programming language devised by Turing) is read from the tape.
I suggest to simply delete the words "on its tape" in the lead section. The two sentences in question are repeated in section Turing_machine#Alan_Turing's_a-machine, anyway; there, they should be left untouched, but somewhere before the concept of universal Turing machine should be explained. - Jochen Burghardt (talk) 19:08, 25 November 2025 (UTC)[reply]
Thank you for the followup. Again I hope my expectations are in line with what is expected of the reader, but I have to say that excising "on its tape" does not really dispel the ambiguity, because it leaves us with:
"Does a machine exist that can determine whether any arbitrary machine [...]"
Still two distinct machines, from the plain-English POV. Are they both Turing machines? Is one a subdivision of the other? (I'm afraid the universal Turing Machine article you linked commenced at a level well above what I'm here to try to engage with, so it did not help me to conceptualise what we have in front of us here, which in my view ought to be made a little more accessible if possible.) ~2025-36276-51 (talk) 18:39, 29 November 2025 (UTC)[reply]
I'm afraid I don't have a good and brief explanation that doesn't require some computer programming knowledge. Hofstadter ("Gödel, Escher, Bach: an Eternal Golden Braid", New York, Basic Books, 1979) discusses the issue pretty late, in Ch.13 (on p.457 in my German translation).
To answer at least your particular questions: "Machine" always means "Turing machine" here. Both machines mentioned can be completely different, but need not. Also keep in mind that (e.g.) the (first) sentence is a question ("Does a machine exist ..."), and Turing proved that its answer is "no". I came up with the following analogy to illustrate the situation: A good cardiologist can inspect any arbitrary human, including herself, to detect heart problems. So inspector and inspectee are both humans, and they can be the same person, but needn't (and usually aren't). On the other hand, even a whatever perfect cardiologist cannot fix heart problems of any arbitrary human - in particular not her own (when a surgical operation under anesthetic is necessary). However, this analogy gets misleading when it comes to the details of Turing's proof (although at least he reasoned about self-application, too).
Maybe it is helpful to speak of a "description of a (Turing) machine on its a tape"? The "inspector" machine is supposed to look at the description, imagine how the described machine would act, and tell us if it would (e.g.) be "circular". - Jochen Burghardt (talk) 19:02, 30 November 2025 (UTC)[reply]