Talk:Turing machine

Thanks for the comments. I have followed every suggestion, major and minor, except the second major comment. I believe the theory of computation section is absolutely indispensable for grasping the meaning, application, and universality of the TM concept. There is no problem having a separate "Complexity Theory" article, that, however, should contain more content. I believe the length of the TM item is well within bounds and justified by the importance of the sublect.

Paul

Very well-written article!

Major comments:

• I do not understand why you define U in a "complicated" (and inefficient) way by U(1^i0p)=T_i(p)" enumerating all TM till T_i and reconstructing E(T), rather than directly as "U(E(T)p)=T(p)" (and undefined or arbitrary for inputs not of this form).

• Since Scholarpedia articles should preferably be short, I recommend to single out the "Theory of Computation" section as an own (cross-linked) "Complexity Theory" article.

• The section on the "Importance of the Turing machine" is quite rough (compared the other sections). Saying that "quantum computer [is] in effect an analogous version [of a digital computer?]" is at the very least misleading.

Minor Comments:

• Improved prefix code x' is never used, so could/should be dropped.
• Strings and natural numbers are occasionally identified. This should be mentioning briefly, once.
• d(Q) has not been defined. |Q| or #Q would be clearer.
• Stating the speedup theorem as is without mentioning the "cheat", leaves the reader puzzled and gives the impression that it's a deep theorem (I know it's often stated that way). I recommend to add "(by increasing the number of tape symbols)". This is more "honest" and makes it "obviously" true.
• The last sentence of the "P vs NP" section": It's unclear to what "This" refers to. Likely the previous paragraph. Maybe make it a quote or switch the order of the last two paragraphs.
• "Phi<oo". =oo has not been introduced as meaning undefined. E.g. write that Phi:=oo if Phi is undefined.
• When you introduce non-deterministic Turing machine, it would help to complete the definition by writing that NTM accepts if one accepting path leads to acceptance.
• Most external links are broken. Probably some conversion introduced a "[" at the end of each link. I've corrected a few but not all.

I've fixed a few small typos directly in the text. (a diff reveals the places).

Reviewer B

(comments sent directly to the author)