| I believe there is some confusion in the article about whether non-halting Turing machines are properly called "Turing machines"; that is, the author seems to use the phrase "Turing machine" to refer only to halting machines. > Not each of these ways end up being Turing machines since a Turing machine, by definition, must have a finite number of operations that end with a halting state. By contrast, a more accepted definition of a Turing machine is given: > An n-card Turing machine is a machine that has a control unit (as seen above) that transitions between n discrete states until it reaches the halting-state. Note that this definition states that the Turing machine no longer transitions once it has reached the "halting state" [1] but it should not be read to imply that a machine must actually reach the halting state after finitely many operations. The article could be corrected by replacing "Turing machine" in the problematic statement with "Turing machine which halts"; or by making explicit the notion of a candidate BBTM as a TM which must halt. As for the current reading of the statement, it is incorrect given that there are in fact [4(n+1)]^2n possible binary n-state TMs given the formalization used in the article, although there are many symmetries which could reduce that number. [1] The distinction between "a" halting state and "the" halting state is immaterial, since you can view states which specify "HALT" either as many distinct halting states or all leading to a singular state, halting. |