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)

Dubious benefits of Turing machines

The "Comparison with real machines" section contains a bullet point

• Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract machines are usually more general than their counterparts running on real machines, because they have arbitrary-precision data types available and never have to deal with unexpected conditions (including, but not limited to, running out of memory).

which I find to be both dubious and weaselly worded.

1. Most algorithms are not easy to state in the form of Turing machines — TMs are, after all, essentially a sort of machine code program where every instruction (state) is a multiway branch with jump to the next instruction. Writing machine code and decompiling machine code are both difficult operations. The benefit of Turing machines are more in the area having an algorithm in a form that may be translated to something else (for example as in the proof that SAT is NP-complete: given a TM that checks a certificate in a polynomial number of steps, we construct a polynomial size CNF formula which is satisfiable iff there is such a certificate).
2. The switch from ‘Turing machines’ in the first sentence to ‘Turing-equivalent abstract machines’ in the second is quite weaselly, because this sweeps under the rug a mountain of difficulties, in particular concerning the implementation of the "arbitrary-precision data types" used as motivation. Turing machines are less well-suited to deal with arbitrary-precision data than many other computational models (such as general recursive functions or lambda calculus), so it is outright misleading to tout this as a benefit of Turing machines specifically.

130.243.94.123 (talk) 13:06, 7 September 2022 (UTC)

I find this whole section puzzling. Do we need it at all? Rp (talk) 16:19, 7 September 2022 (UTC)

I agree that the section is quite puzzling with some rather absurd statements. Notably, there are no citations in the section. What is its utility? Crescent77 (talk) 19:27, 26 March 2023 (UTC)

Although I agree with many of the comments above about there being much room for improvement in this section, I have to say that comparing TMs to more realistic models of computation and especially to real computers seems like a very valuable topic. I have seen considerable confusion/discussion about this comparison in other wikipedia articles and other wikipedia Talk pages. And when I was teaching this subject at UCLA-CSD, this comparison often came up as a topic of discussion. For that reason, I would "vote" for extensively revising this section rather than deleting it entirely. Unless I hear strong resistance to this idea, I would be willing to take it upon myself to do some non-trivial rewriting of this section, with the understanding that we can always back-out the changes if people feel it is not enough or I have done more harm than good.

That said, I probably won't get to that until next week. I want to see how this comment is received, and I'll be traveling starting later this week.

Mike-c-in-mv (talk) 21:44, 4 June 2023 (UTC)

I agree. Turing machines are meant to model computing, not typical computers, and this should be stressed more. Having a section on this topic is a good idea, but it should be reworded completely. Rp (talk) 15:06, 5 June 2023 (UTC)

I just got done complaining about this entire section, in the comments a further below. Most of the statements in that section appear to be just plain wrong, to me. 67.198.37.16 (talk) 04:54, 29 November 2023 (UTC)

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)

Comparison with the arithmetic model of computation

While the recently added section Turing machine#Comparison with the arithmetic model of computation is quite interesting, I'm afraid it is of undue weight here. Moreover, it confuses readers by apparently suggesting that each real number can be represented in a Turing machine. I suggest that the detailled discussion of comparison is moved to arithmetic model of computation (if not already present there), and that a one-paragraph summary is added to some appropriate section of Turing machine, without an own [sub]section header. - Jochen Burghardt (talk) 20:21, 28 January 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)