Multi-tape Turing Machines
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 just be going up or down.
- Each tape needs it own instructions
- BB(n,m,1) = BB(n,m)
The Champion for BB(2,2,2) is this. S(2,2,2) > 16. Sigma(2,2,2) > 6 but not from this TM
| 0 | 1 | |
| A | 1RB | 0LB |
| B | 0LDA | 0RDB |
| 0 | 1 | |
| A | 0LUA | 1LUB |
| B | 1RA | halt |