Settings

Theme

Turing Machines and the Busy Beaver Game

drivenbycode.com

11 points by mishkinf 11 years ago · 1 comment

Reader

belovedeagle 11 years ago

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.

Keyboard Shortcuts

j
Next item
k
Previous item
o / Enter
Open selected item
?
Show this help
Esc
Close modal / clear selection