Talk:Turing machine

Bad explanation in the second paragraph

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)

False statements in section "Comparison with real machines"

The section "Comparison with real machines" consists almost entirely of misleading if not outright false statements, from beginning to end. Crazy stuff, like "Like a Turing machine, a real machine can have its storage space enlarged as needed," Uh, no; Turing machines can't/don't "enlarge" their memory. They already have an unbounded amount. Or this blooper: "There is a limit to the memory possessed by any current machine, but this limit can rise arbitrarily in time." Uh, no, not "arbitrarily", but only as much as vendors can manufacture. Ultimately limited by the number of atoms on the Earth, or Solar System, or Universe. By comparison, Turing machines have a literally unbounded amount. Or this entire paragraph: "Descriptions of real machine programs using simpler abstract models are often much more complex than descriptions using Turing machines. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent deterministic finite automaton (DFA) on a given real machine has quadrillions. This makes the DFA representation infeasible to analyze." Each sentence of this last is patently wrong in more than one way. The errors continue onwards in later subsections of this section. Personally, I recommend nuking the entire section, and starting from scratch. But that would probably raise a hornet's nest that I don't want to engage in; so I'd rather leave this drive-by comment. Surely the regular maintainers of this article can do much better. 67.198.37.16 (talk) 04:43, 29 November 2023 (UTC)

You seem very angry at nobody in particular about what are pretty incidental inaccuracies at best, that don't really damage the core understanding of what a Turing machine is or why it's a useful model. Would you like to work with fellow editors to improve the article, or would you prefer to remain totally gobsmacked because a paragraph in an article about an abstract algorithmic object fails to account for the finite number of atoms in the universe in an analogy? Remsense留 05:00, 29 November 2023 (UTC)

Oh, gobsmacked, definitely. These are not "incidental inaccuracies", they are fundamental misunderstandings of the core concept. I imagine this section has been read by millions of high-school and college students, and as a result has successfully planted some serious misunderstandings of what Turing machines are. We demand accuracy and correctness from other WP articles; I don't see why this article should get a free pass. 67.198.37.16 (talk) 05:39, 29 November 2023 (UTC)

I must agree this section contains many examples of complete nonsense and is in need of a complete rewrite from scratch. I think I may have previously said I would undertake that "soon". But that was years ago; so clearly I failed to follow-thru on my good intentions. I'll try to make time for in several weeks. I can understand that not everyone will believe that given my history. So if someone else decides to make the start, I would gladly support that effort with editorial comments and contributions to writing portions of the new section. Mike-c-in-mv (talk) 01:15, 12 July 2024 (UTC)

Reading Level

Hi I came here to say that I think this article’s reading level is too high. The article also assumes the reader has specialized knowledge and this makes the article incomprehensible to many who would benefit from an “explain like I’m five” approach to this subject matter. 74.101.116.31 (talk) 10:15, 24 March 2024 (UTC)

What specifically do you have trouble with? I believe articles should be such that non-experts can easily read them to grasp the essence of a topic, as far as possible without taking a course on the prerequisites. At some point, you do need prerequisite knowledge. The Turing machine itself is certainly simple enough to be easy to explain to a five year old. However, the point of the Turing machine can only be understood given an understanding of the basics of mathematical logic. This is a university level topic and it usually requires a course to master. Explaining those things is far beyond the scope of this article, and teaching things is for Wikibooks. So I think the best we can do is structure the material in such a way that the machine itself is presented first, and its purpose is described next, first in general terms that a non-expert can understand, then in detail. At some point, the non-expert will give up, but with the right pointers, they will at least know where to continue for further learning. Rp (talk) 11:44, 24 March 2024 (UTC)

I agree with AI chatgpt etc it's literally a key press away to explain it if you need extra help .I am a mechanic engineer who is working on a Turing machine as a project and this wiki page wasn't difficult to understand . Bunions Nonsenseses (talk) 01:10, 20 July 2024 (UTC)

The sentence is not fluent

@Remsense Hi, this sentence:

by using one stack to model the tape left of the head and the other stack for the tape to the right.

is not fluent. Please do something to modify that. Hooman Mallahzadeh (talk) 11:48, 13 July 2024 (UTC)

Incorrect theoretical understanding corrected

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)

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)

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)

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)