Talk:Turing machine

From Scholarpedia
Jump to: navigation, search

    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.


    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)

    Personal tools

    Focal areas