User:Merieke/2D TMs: Difference between revisions
Jump to navigation
Jump to search
added stuff |
added a champion |
||
| Line 7: | Line 7: | ||
* The head starts on the lowermost tape. | * The head starts on the lowermost tape. | ||
* A step can't just be going up or down. | * 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 | |||
The Champion for BB(2,2,2) is this. S(2,2,2) = 11 and <math>\Sigma</math>(2,2,2) = 5 | |||
{| class="wikitable" | {| class="wikitable" | ||
|+Top | |+Top | ||
| Line 18: | Line 19: | ||
|- | |- | ||
|A | |A | ||
| | |1RDB | ||
| | |H | ||
|- | |- | ||
|B | |B | ||
| | |0LA | ||
| | |1RDB | ||
|} | |} | ||
{| class="wikitable" | {| class="wikitable" | ||
| Line 32: | Line 33: | ||
|- | |- | ||
|A | |A | ||
| | |1RUB | ||
| | |0LUA | ||
|- | |- | ||
|B | |B | ||
| | |1LA | ||
| | |1LA | ||
|} | |} | ||
Revision as of 22:32, 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. S(2,2,2) = 11 and (2,2,2) = 5
| 0 | 1 | |
| A | 1RDB | H |
| B | 0LA | 1RDB |
| 0 | 1 | |
| A | 1RUB | 0LUA |
| B | 1LA | 1LA |