User:Merieke/2D TMs: Difference between revisions
Jump to navigation
Jump to search
added some stuff and will delete multi tape tm page bc not needed |
added stuff |
||
| Line 1: | Line 1: | ||
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. | 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 | |||
{| class="wikitable" | |||
|+Top | |||
| | |||
|0 | |||
|1 | |||
|- | |||
|A | |||
| | |||
| | |||
|- | |||
|B | |||
| | |||
| | |||
|} | |||
{| class="wikitable" | |||
|+Bottom | |||
| | |||
|0 | |||
|1 | |||
|- | |||
|A | |||
| | |||
| | |||
|- | |||
|B | |||
| | |||
| | |||
|} | |||
Revision as of 20:12, 21 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'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 |