3 ms·
Can someone explain how there can a finite number of rules ? Could the rule "If it's a 0, change it to 1 and move 3 squares to the left" produce a different res
by Jean-Papoulos 2y ago
Can someone explain how there can a finite number of rules ?
Could the rule "If it's a 0, change it to 1 and move 3 squares to the left" produce a different result than when moving 4 squares, or is that not the case ?
- hmry 2y agoYou can only ever move one step to the left or right. If you want to move multiple steps, you need multiple states to use as a counter, or set up the tape a specific way ahead of time so you know when to stop moving.
- masklinn 2y agoA turing machine rule can only: - 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.