Multi-tape Turing Machines: Difference between revisions
Jump to navigation
Jump to search
Loader3229 (talk | contribs) m Loader3229 moved page 2D Tms to Multi-tape Turing Machines |
added TM code |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
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. | 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 | '''Rules''' | ||
* Going up or down is not required for each step. | * Going up or down is not required for each step. | ||
| 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) | *BB(n,m,1) = BB(n,m) | ||
'''How to write TMs''' | |||
Writing 2D TMs are mostly like writing them in the first dimension, you just need to add a slash in between every layer of instruction and go top to bottom. | |||
The champion for BB(2,2,2) would be this in TM form - 1RB0LB_0LDA0RDB / 0LUA1LUB_1RA1RZ | |||
'''Current Bounds''' | |||
BB(n,m,o) > BB(n,m)<math>\times</math>o | |||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+2 Tapes | ||
!Domain | |||
!Score | |||
!Runtime | |||
!TM Code | |||
|- | |- | ||
| | |BB(2,2,2) | ||
| | |6 but not from Champion | ||
| | |16 | ||
|1RB0LB_0LDA0RDB / 0LUA1LUB_1RA1RZ | |||
|- | |- | ||
| | |BB(2,3,2) | ||
| | |4 | ||
| | |23 | ||
|0RDB2LB1RZ_1LA1DA1RZ / 2RUB2RB1UA_0LA1LUB0RA | |||
|} | |} | ||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+ | ||
!Domain | |||
!Score | |||
!Runtime | |||
!TM Code | |||
|- | |- | ||
| | |BB(2,2,3) | ||
| | |8 | ||
| | |24 | ||
|1RDB1RZ_0LA1RZ / 0RUB1RZ_0RDA1RZ / 1LUA1RZ_1LUB1LB | |||
|} | |} | ||
Latest revision as of 21:20, 6 November 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. 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)
How to write TMs
Writing 2D TMs are mostly like writing them in the first dimension, you just need to add a slash in between every layer of instruction and go top to bottom.
The champion for BB(2,2,2) would be this in TM form - 1RB0LB_0LDA0RDB / 0LUA1LUB_1RA1RZ
Current Bounds
BB(n,m,o) > BB(n,m)o
| Domain | Score | Runtime | TM Code |
|---|---|---|---|
| BB(2,2,2) | 6 but not from Champion | 16 | 1RB0LB_0LDA0RDB / 0LUA1LUB_1RA1RZ |
| BB(2,3,2) | 4 | 23 | 0RDB2LB1RZ_1LA1DA1RZ / 2RUB2RB1UA_0LA1LUB0RA |
| Domain | Score | Runtime | TM Code |
|---|---|---|---|
| BB(2,2,3) | 8 | 24 | 1RDB1RZ_0LA1RZ / 0RUB1RZ_0RDA1RZ / 1LUA1RZ_1LUB1LB |