Multi-tape Turing Machines: Difference between revisions
Jump to navigation
Jump to search
Created page with " 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 The Champion for BB(2,2,2) is this. S(2,2,2) > 16. Sigma(2..." |
added stuff |
||
| Line 8: | Line 8: | ||
* A step can just be going up or down. | * A step can just be going up or down. | ||
* Each tape needs it own instructions | * Each tape needs it own instructions | ||
* BB(n,m,1) = BB(n,m) | |||
Revision as of 21:05, 28 October 2026
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 |