by mishkinf on 3/27/15, 3:04 PM with 1 comments
by belovedeagle on 3/27/15, 5:49 PM
> 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.