User:Merieke/2D TMs
Jump to navigation
Jump to search
Multi-tape Turing Machines are like normal Turing machines but with more tapes. BB(n,m,o) = the maximum number of steps taken by a n state, m symbol, o tape Turing machine. In addition to going left and right, it can also go up and down.
Rules
- Going up or down is not required for each step.
- The head starts on the lowermost tape.
- A step can't just be going up or down. if it goes up or down it also has to go left or right.
The Champion for BB(2,2,2) is this
| 0 | 1 | |
| A | ||
| B |
| 0 | 1 | |
| A | ||
| B |