FANDOM


On the Turing golf page I saw an interesting challenge: compute BB(2) with a Turing machine. I believe it is quite possible to do and shouldn't take more than 1000 states (probably much, much less), and that's what I'm planning to do here.

Stage 1: Reading Instructions

The first stage is obviously letting a Turing machine having its input as a set of instructions for a smaller TM (namely, for two states and two symbols). It so happens that I tried to do this a while ago with bigger TMs (5 states and 5 symbols took me 369 lines of instructions on this simulator), so this was the easy part for me. Full code as follows:

; A: Moves to the right and checks what the current symbol is (encodes it as "s").
0 * * r 0
0 x x r 1
1 x x r 1
1 _ s l pp0b
1 1 s l pp01
; B: Moves left till it reaches the "n" and starts reading the instructions.
pp0b * * l pp0b
pp0b n n r ps0b
pp01 * * l pp01
pp01 n n r ps01
pp1b * * l pp1b
pp1b n n r ps1b
pp11 * * l pp11
pp11 n n r ps11
; C: Moves right after each vertical line to check if it's the right instruction.
ps0b * * r ps0b
ps0b | | r s0b
ps0b x ? r error ; Will happen only if you did not include an instruction for a certain situation
ps01 * * r ps01
ps01 | | r s01
ps01 x ? r error
ps1b * * r ps1b
ps1b | | r s1b
ps1b x ? r error
ps11 * * r ps11
ps11 | | r s11
ps11 x ? r error
; D: Checks if the instruction is about the right state. If not, goes back to B.
s0b 0 0 r r0b
s0b * * r ps0b
s01 0 0 r r01
s01 * * r ps01
s1b 1 1 r r1b
s1b * * r ps1b
s11 1 1 r r11
s11 * * r ps11
; E: Checks if the instruction is about the right symbol. If not, goes back to B
r0b b b r pc
r0b * * r ps0b
r01 1 1 r pc
r01 * * r ps01
r1b b b r pc
r1b * * r ps1b
r11 1 1 r pc
r11 * * r ps11
; F: Checks to which symbol to change the current symbol.
pc b d r chb
pc 1 i r ch1
; G: Changes the current symbol and encodes it for a later purpose.
chb * * r chb
chb s d l ppm
ch1 * * r ch1
ch1 s i l ppm
; H: Moves left to allow checking of direction.
ppm * * l ppm
ppm i 1 r pm
ppm d b r pm
; I: Checks to which direction to move.
pm r v r mr
pm p q r m*
pm l i r ml
; J: Decodes the encoded symbol (from G) and moves to the right direction.
mr * * r mr
mr i 1 r m
mr d _ r m
m* * * r m*
m* i 1 * m
m* d _ * m
ml * * r ml
ml i 1 l m
ml d _ l m
; K: Checks what the current symbol is, encodes it as s and moves left to check what the new state is.
m 1 s l psb1
m * s l psbb
; L: Moves right to find the new state.
psb1 * * l psb1
psb1 v r r ppb1
psb1 q p r ppb1
psb1 i l r ppb1
psbb * * l psbb
psbb v r r ppbb
psbb q p r ppbb
psbb i l r ppbb
; M: Checks what the new state is and goes back to B (or if state is halt, to N).
ppb1 0 0 l pp01
ppb1 1 1 l pp11
ppb1 h h r end1
ppbb 0 0 l pp0b
ppbb 1 1 l pp1b
ppbb h h r endb
; N: Decodes the current symbol and halts.
end1 * * r end1
end1 s 1 * halt
endb * * r endb
endb s _ * halt

The input must start with "n|" and follow with lines of instructions that are built like this: <state (0/1)><current symbol (_ is replaced by b, does not accept *)><new symbol (likewise>)<direction (* is replaced by p)><new state (you can shorten halt to h if you want)>, all consecutive. An example of an instruction would be "0b1rh". In the normal code, this would be: "0 _ 1 r halt".

Each instruction is separated by a vertical line "|". To mark the end of the instructions, type 1 or more consecutive "x"'s (not neccesarily straight after the last instruction), and after them the input. If the input moves on the x's, it will regard them as blank.

Here is an example for a valid input: "n|0b1l1|011r1|1b1r0|111lh xx". This is equivalent to:

0 _ 1 l 1
0 1 1 r 1
1 _ 1 r 0
1 1 1 l halt

That's the two state busy beaver. If you want to see the program working, click here.

Stage 2: Counting steps

We cannot run each TM for infinity (well, we could, but first I'll post a normal bound), so we must let it be able to figure out how many steps have passed. This is fairly straightforward:

; A: Moves to the right and checks what the current symbol is (encodes it as "s").
0 * * r 0
0 x x r 1
1 x x r 1
1 _ s l pp0b
1 1 s l pp01
; B: Moves left till it reaches the "n" and starts reading the instructions.
pp0b * * l pp0b
pp0b n n r ps0b
pp01 * * l pp01
pp01 n n r ps01
pp1b * * l pp1b
pp1b n n r ps1b
pp11 * * l pp11
pp11 n n r ps11
; C: Moves right after each vertical line to check if it's the right instruction.
ps0b * * r ps0b
ps0b | | r s0b
ps0b x ? r error ; Will happen only if you did not include an instruction for a certain situation
ps01 * * r ps01
ps01 | | r s01
ps01 x ? r error
ps1b * * r ps1b
ps1b | | r s1b
ps1b x ? r error
ps11 * * r ps11
ps11 | | r s11
ps11 x ? r error
; D: Checks if the instruction is about the right state. If not, goes back to B.
s0b 0 0 r r0b
s0b * * r ps0b
s01 0 0 r r01
s01 * * r ps01
s1b 1 1 r r1b
s1b * * r ps1b
s11 1 1 r r11
s11 * * r ps11
; E: Checks if the instruction is about the right symbol. If not, goes back to B
r0b b b r pc
r0b * * r ps0b
r01 1 1 r pc
r01 * * r ps01
r1b b b r pc
r1b * * r ps1b
r11 1 1 r pc
r11 * * r ps11
; F: Checks to which symbol to change the current symbol.
pc b d r chb
pc 1 i r ch1
; G: Changes the current symbol and encodes it for a later purpose.
chb * * r chb
chb s d l ppm
ch1 * * r ch1
ch1 s i l ppm
; H: Moves left to allow checking of direction.
ppm * * l ppm
ppm i 1 r pm
ppm d b r pm
; I: Checks to which direction to move.
pm r v r mr
pm p q r m*
pm l i r ml
; J: Decodes the encoded symbol (from G) and moves to the right direction.
mr * * r mr
mr i 1 r m
mr d _ r m
m* * * r m*
m* i 1 * m
m* d _ * m
ml * * r ml
ml i 1 l m
ml d _ l m
; K: Checks what the current symbol is, encodes it and moves left to count a step.
m 1 I l pcs
m * d l pcs
; L: Moves to find the new state.
psb1 * * l psb1
psb1 v r r ppb1
psb1 q p r ppb1
psb1 i l r ppb1
psbb * * l psbb
psbb v r r ppbb
psbb q p r ppbb
psbb i l r ppbb
; M: Checks what the new state is and goes back to B (or if state is halt, to N).
ppb1 0 0 l pp01
ppb1 1 1 l pp11
ppb1 h h r end1
ppbb 0 0 l pp0b
ppbb 1 1 l pp1b
ppbb h h r endb
; N: Decodes the current symbol and halts.
end1 * * r end1
end1 s 1 * halt
endb * * r endb
endb s _ * halt
end * * r end
end d _ * halt
end I 1 * halt
; O: Moves left to count a step
pcs * * l pcs
pcs n n l ppcs
ppcs * * l ppcs
ppcs _ _ r cs
; P: Count a step.
cs 1 i r ps
cs i i r cs
cs | | r end ; No steps left
; Q: Move right to the current symbol and go to L.
ps * * r ps
ps I s l psb1
ps d s l psbb

Now input is in the form of "111...11|n|rule1|rule2|rule3|rule4xx...xx'input'" where the rules and the n serve the same purpose as before, the consecutive 1's are the amount of steps the TM can run, and the x's are the amount of leftward steps the TM can move. Here's an example when we put a non halting program with steps to run. That program keeps moving right till it meets a 1, but as it is started on an empty tape, after 10 steps it halts.

Stage 3

Alternative

Here's a four headed Turing machine (each instruction is in the form "<current tape> <current state> <current symbol> <new symbol> <direction> <new tape> <new state>") that given an input, a ruleset, and a counter for how many steps it can run, gives how many 1's the tape can produce. Tape 1 is the simulation tape, Tape 2 is the instructions, Tape 3 is the counter (counts down how many steps the simulation can run) and Tape 4 is the output (how many 1s the Turing machine printed). Tape 4 and 3 could be merged (Tape 4 literally has 2 states), but this isn't for maximum efficiency, rather just for cleanness.

1 0 _ _ * 2 sb0
1 0 1 1 * 2 s10
1 pr1 * 1 * 2 dir
1 prb * b * 2 dir
1 mr * * r 3 mr
1 ml * * l 3 mr
1 m 1 1 * 2 ps1b
1 m _ _ * 2 psbb
1 countl _ _ l 3 ml
1 countl 1 _ l 4 plus1
1 pcount _ _ r 3 mrr
1 countr _ _ r 3 mll
1 countr 1 _ r 4 pluus1

2 psb0 | | r 2 sb0
2 psb0 * * r 2 psb1
2 ps10 | | r 2 s10
2 ps10 * * r 2 ps10
2 psb1 | | r 2 sb1
2 psb1 * * r 2 psb1
2 psb1 _ ? l 2 halt
2 ps11 | | r 2 s11
2 ps11 * * r 2 ps11
2 ps11 _ ? l 2 halt 
2 sb0 0 0 r 2 rb0
2 sb0 1 1 r 2 psb0
2 s10 0 0 r 2 r10
2 s10 1 1 r 2 ps10
2 sb1 1 1 r 2 rb1
2 sb1 0 0 r 2 psb1
2 s11 1 1 r 2 r11
2 s11 0 0 r 2 ps11
2 rb0 b b r 2 cs
2 rb0 * * r 2 psb0
2 r10 1 1 r 2 cs
2 r10 * * r 2 ps10
2 rb1 b b r 2 cs
2 rb1 * * r 2 psb1
2 r11 1 1 r 2 cs
2 r11 * * r 2 ps11
2 cs 1 1 r 1 pr1
2 cs b b r 1 prb
2 dir r r r 1 mr
2 dir l l r 1 ml
2 dir p p r 1 m
2 psbb 1 1 l 2 ppb1
2 psbb 0 0 l 2 ppb0
2 ps1b 1 1 l 2 pp11
2 ps1b 0 0 l 2 pp10
2 psbb h h * 3 count
2 ps1b h h * 3 count
2 ppb1 * * l ppb1
2 ppb1 _ _ r psb1
2 ppb0 * * l ppb0
2 ppb0 _ _ r psb0
2 pp10 * * l pp10
2 pp10 _ _ r ps10
2 pp11 * * l pp11
2 pp11 _ _ r ps11

3 mr 1 1 r 1 m
3 mr _ _ l 1 countl
3 ml 1 1 l 1 countl
3 ml _ _ r 1 pcount
3 mrr 1 1 r 1 pcount
3 mrr _ _ l 1 countr
3 mll 1 1 l 1 countr
3 mll _ _ r 3 halt

4 plus1 _ 1 r 3 ml
4 pluus1 _ 1 r 3 mll

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.