(A TM rule has one sub-rule for each valid value / symbol)
Turing machines are characterised by the number of values (or symbols) and the number of rules (or states) (and technically the number of directions but TMs are generally one-dimensional). The Busy Beaver game fixes the number of symbols to 2, and only varies the number of states e.g. BB(3) is played on 3-states 2-symbols turing machines.
Thus the number of possible rules in BB(n) (n-states 2 symbols turing machine) is necessarily limited, to (4n + 4)^2n.
- set the current cell’s value
- move by one cell
- switch to the next rule (or halt)
(A TM rule has one sub-rule for each valid value / symbol)
Turing machines are characterised by the number of values (or symbols) and the number of rules (or states) (and technically the number of directions but TMs are generally one-dimensional). The Busy Beaver game fixes the number of symbols to 2, and only varies the number of states e.g. BB(3) is played on 3-states 2-symbols turing machines.
Thus the number of possible rules in BB(n) (n-states 2 symbols turing machine) is necessarily limited, to (4n + 4)^2n.