Each row is a state and each column is the symbol that was just read off the tape. So the first row & first column mean "I have just read symbol 0 and am currently in state A".

The cell in the table describes which actions to perform. The first row & first column has "1RB" which means: "replace the symbol on the tape with '1', shift 1 symbol to the right on the tape and switch to state 'B'".

The state 'Z' corresponds to the halting state.

There's a brief explanation at [0]. (Note that "1RZ" is understood to be a halting transition, since state "Z" has no rules.) Wikipedia also has a more elaborated example of a TM state table [1]. You can see the trace of this particular TM at [2].

[0] https://bbchallenge.org/story#turing-machines

[1] https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...

[2] https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2...

Each triplet seems to be the symbol to write, and direction to move in, and the next state. You can think of the behavior of a turing machine as a function of the current state and the symbol read that's repeated iteratively.

The "states" (A, B, C) correspond to goto targets. The "colors" (0, 1, 2, 3) are runtime data. At each state, the current color is read, and an instruction is executed (print some color, move left or right, goto some state) based on which color is there. Transliterated into C it looks like this:

  #include "machine.h"
  
  int main(void)
  {
   A:
    switch (SCAN) {
      case 0:
        WRITE(1); RIGHT; goto B;
  
      case 1:
        WRITE(3); LEFT; goto B;
  
      case 2:
        WRITE(1); RIGHT; goto H;
  
      case 3:
        WRITE(2); RIGHT; goto A;
    }
  
   B:
    switch (SCAN) {
      case 0:
        WRITE(2); LEFT; goto C;
  
      case 1:
        WRITE(3); RIGHT; goto B;
  
      case 2:
        WRITE(1); LEFT; goto C;
  
      case 3:
        WRITE(2); RIGHT; goto A;
    }
  
   C:
    switch (SCAN) {
      case 0:
        WRITE(3); RIGHT; goto B;
  
      case 1:
        WRITE(1); LEFT; goto B;
  
      case 2:
        WRITE(3); LEFT; goto C;
  
      case 3:
        WRITE(2); RIGHT; goto C;
    }
  
   H:
    HALT;
  }

Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

> Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO:

    let mut a = true;
    loop {
        loop {
            if a { // state A
                match scan() {
                    0 => { write(1); right(); break }
                    1 => { write(3); left(); break }
                    2 => { write(1); right(); return }
                    3 => { write(2); right() }
                }
            } else { // state C
                match scan() {
                    0 => { write(3); right(); break }
                    1 => { write(1); left(); break }
                    2 => { write(3); left() }
                    3 => { write(2); right() }
                }
            }
        }

        a = loop { // state B
            match scan() {
                0 => { write(2); left(); break false }
                1 => { write(3); right() }
                2 => { write(1); left(); break false }
                3 => { write(2); right(); break true }
            }
        }
    }

Of course it is possible to rewrite this as a single loop if you are willing to accept two bits of extra state rather than one.

Wow! I don't know if I would call that "structured", but it's pretty clever. And horrifying. Well-done!

I love these puzzles. GNU C supports a label as value for computed goto. This is useful for direct threaded dispatch. You trade off a branch instruction for an address lookup, but it makes the code more structured.

  int main(void) {
    void* A[] = {&&A0, &&A1, &&A2, &&A3};
    void* B[] = {&&B0, &&B1, &&B2, &&B3};
    void* C[] = {&&C0, &&C1, &&C2, &&C3};
    goto *A[SCAN];
    A0: WRITE(1); RIGHT; goto *B[SCAN];
    A1: WRITE(3); LEFT ; goto *B[SCAN];
    A2: WRITE(1); RIGHT; HALT; return 0;
    A3: WRITE(2); RIGHT; goto *A[SCAN];
    B0: WRITE(2); LEFT ; goto *C[SCAN];
    B1: WRITE(3); RIGHT; goto *B[SCAN];
    B2: WRITE(1); LEFT ; goto *C[SCAN];
    B3: WRITE(2); RIGHT; goto *A[SCAN];
    C0: WRITE(3); RIGHT; goto *B[SCAN];
    C1: WRITE(1); LEFT ; goto *B[SCAN];
    C2: WRITE(3); LEFT ; goto *C[SCAN];
    C3: WRITE(2); RIGHT; goto *C[SCAN];
  }

> GNU C supports a label as value for computed goto.

Why doesn't any modern C standard like C23 include this? Seems like a glaring omission.

Sometimes, the fact that one implementation includes it can make it actually more difficult to standardize, if there are some implementation details that are disagreeable (see GNU's nested functions)

What's the initial state supposed to be?

My understanding is that the states are conventionally listed in order, so A would be the initial state:

> A TM string is in lexical normal form iff the following conditions obtain: …The non-initial active states first occur in ascending order…

Infinite tape of zeros.

Zero is neither A nor B or C...?

The start state is A.

The initial state is A, the tape is full of 0 (on both sides).

I've made a small repository with current record holders that also shows examples of running these machines with Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-B.... I guess I also need to update it now.

In Python:

    def L():
        global index, tape
        if index: index -= 1
        else: tape.insert(0, 0)

    def R():
        global index, tape
        index += 1
        if index >= len(tape): tape.append(0)

    table = {
     ('A', 0): (1, R, 'B'),
     ('A', 1): (3, L, 'B'),
     ('A', 2): (1, R, 'Z'),
     ('A', 3): (2, R, 'A'),
     ('B', 0): (2, L, 'C'),
     ('B', 1): (3, R, 'B'),
     ('B', 2): (1, L, 'C'),
     ('B', 3): (2, R, 'A'),
     ('C', 0): (3, R, 'B'),
     ('C', 1): (1, L, 'B'),
     ('C', 2): (3, L, 'C'),
     ('C', 3): (2, R, 'C'),
     }

    state = 'A'
    tape = [0]
    index = 0
    while state != 'Z':
        tape[index], direction, state = table[state, tape[index]]
        direction()

I found this quite helpful: https://nickdrozd.github.io/2020/10/04/turing-machine-notati...

Despite a CS undergrad I don’t recall really learning any of these canonical representations of TMs before.