Multi-tape Turing Machines
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. All of the champions have been hand simulated (which hopefully will change soon) which means that none of them will be optimal at all.
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 |
The Champion for BB(2,2,3) is this. S(2,2,3) > 24 and (2,2,3) > 8
| 0 | 1 | |
| A | 1RDB | halt |
| B | 0LA | halt |
| 0 | 1 | |
| A | 0RUB | halt |
| B | 0RDA | halt |
| 0 | 1 | |
| A | 1LUA | halt |
| B | 1LUB | 1LB |