BB(3, 4) > Ack(14)

supriyo-biswas wrote: post #4

Can someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?

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.

Re: BB(3, 4) > Ack(14)

#7

Post by treyd » Thu, May 23, 2024, 3:07 PM UTC

supriyo-biswas wrote: post #4

Can someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?

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.

Re: BB(3, 4) > Ack(14)

#8

Post by LegionMammal978 » Thu, May 23, 2024, 3:09 PM UTC

supriyo-biswas wrote: post #4

Can someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?

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...

Re: BB(3, 4) > Ack(14)

#9

Post by immibis » Thu, May 23, 2024, 3:25 PM UTC

Discord links! As citations for major results in foundational computer science!

Re: BB(3, 4) > Ack(14)

#10

Post by tromp » Thu, May 23, 2024, 3:28 PM UTC

The new BB(3,4) record holder is

         0   1   2   3
    A   1RB 3LB 1RZ 2RA
    B   2LC 3RB 1LC 2RA
    C   3RB 1LB 3LC 2RC

with the triple (t',d, s') in row s column t specifying the transition from state s with symbol t under the tape head. the machine overwrites symbol t with t', moves the tape Left/Right according to direction d, and changes state from s to s', halting if s'==Z.

This is 3*4*log2(4*2*log2(4+1)) or about 64 bits of information. Meanwhile, in only 49 bits, BBλ(49) far exceeds Graham's number [1].

[1] https://oeis.org/A333479