Multi-tape Turing Machines: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
Merieke (talk | contribs)
29 edits
Added how to write TMs
Merieke (talk | contribs)
29 edits
fixed and just made it much better
Line 10: Line 10:
*BB(n,m,1) = BB(n,m)
*BB(n,m,1) = BB(n,m)


How to write TMswriting 2d TMs are mostly like writing them in the first dimension. You just need to add a slash in between every layer of instruction.
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
The champion for BB(2,2,2) would be this in TM form - 1RB0LB_0LDA0RDB / 0LUA1LUB_1RA1RZ
The Champion for BB(2,2,2) is this. S(2,2,2) > 16. Sigma<math>\Sigma</math>(2,2,2) > 6 but not from this TM
{| class="wikitable"
{| class="wikitable"
|+ Top
|+2 Tapes
!Domain
!Score
!Runtime
!TM Code
!
|-
|-
| || 0 || 1
|BB(2,2,2)
|6 but not from Champion
|16
|1RB0LB_0LDA0RDB / 0LUA1LUB_1RA1RZ
|
|-
|-
| A || 1RB || 0LB
|BB(2,3,2)
|-
|4
| B || 0LDA || 0RDB
|23
|0RDB2LB1RZ_1LA1DA1RZ / 2RUB2RB1UA_0LA1LUB0RA
|
|}
|}
{| class="wikitable"
{| class="wikitable"
|+ Bottom
|+
!Domain
!Score
!Runtime
!TM Code
|-
|-
| || 0 || 1
|BB(2,2,3)
|later
|24
|later
|-
|-
| A || 0LUA || 1LUB
|
|
|
|
|-
|-
| B || 1RA || halt
|}
The Champion for BB(2,2,3) is this. S(2,2,3) > 24 and <math>\Sigma</math>(2,2,3) > 8
{| class="wikitable"
|+Top
|
|
|0
|1
|-
|A
|1RDB
|halt
|-
|B
|0LA
|halt
|}
{| class="wikitable"
|+Middle
|
|
|0
|1
|-
|A
|0RUB
|halt
|-
|B
|0RDA
|halt
|}
{| class="wikitable"
|+Bottom
|
|
|0
|
|1
|-
|A
|1LUA
|halt
|-
|B
|1LUB
|1LB
|}
|}

Revision as of 21:27, 5 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

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
Domain Score Runtime TM Code
BB(2,2,3) later 24 later
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Multi-tape_Turing_Machines&oldid=10282"