User:Merieke/2D TMs

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) > 16

Top

	0	1
A	1RB	0LB
B	0LDA	0RDB

Bottom

	0	1
A	0LUA	1LUB
B	1RA	H