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