Comment by abetusk | Hacker News Reader

Comment by abetusk | Hacker News Reader

Parent Full thread

BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0.

The table in the article (under "The Machine" section) describes the state on the left hand column (A,B,C) and the input on the top row (0,1,2). The entry in the table describes, as far as I can tell, what the Turing machine writes back to the tape, the direction it goes and the state it transitions to.

So for entry 'A', '2', the entry is '1LC', meaning it writes '1' at the tape position it's in, moves one to the left then transitions to state 'C'. State 'C' on reading symbol '0' will halt, as is the requirement for it being a buys beaver machine.

I very weakly understand the 'A(a,b,c)' notation in the 'Analysis' section but I don't quite understand what it's saying. The line that says "A(a,b,c) = 0^\inf 12^a 11^b <A 11^c 0^\inf" is describing the input tape state, with s^x denoting symbol s repeated x times, but I don't quite understand what the "<A" is.

The table below it describes what I believe are essentially reduction rules. That is, "if the state of the TM is like this, we can deduce it will be reduced to this state" which is how it relates back to the Collatz conjecture.

Anyway, nice article. Wish there was a "glossary" section that described the esoteric notation.

[0] https://en.wikipedia.org/wiki/Busy_beaver

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

> An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0.

Technically, that's "halt" _transition_. There's supposed to be an implied Halt state - but it's straight up easier to treat halting as smth like "invalid instruction" hardware exception.

> The line that says "A(a,b,c) = 0^\inf 12^a 11^b <A 11^c 0^\inf" is describing the input tape state

While yes, it can be an input - instead it is mostly treated as "intermediate" state of the tape. TM is quite low level, so various abstractions are welcome. If you can prove that input you're interested in (empty tape) gets to your abstraction and stays there - stuff gets simpler.

> but I don't quite understand what the "<A" is.

One of very useful abstractions without much cost is to keep track of direction head was travelling in. 1) instead of "head is on this cell and state kept outside" it allows inline notation, while visually pointing to the cell the head is on 2) it's mostly explained as representation of TM with 2 stacks which is easy to implement and run 3) direction is already encoded in the transitions "1LC == <C 1"

That allows nice rewrite rules like "B> 1 -> 1 B>" that simplify manual playthrough, and it works nice with intuition - e.g. B> keeps going right all the way until it encounters 0, like a ship with a pointy nose through the water.

And, well, additional state helps a lot of the time.

The “<A” notation indicates that the head of the Turing machine is positioned at the rightmost point to the left of the “<“, and is in state A. [0]

For instance, the notation `0^\inf 1^3 <B 0^2 1 0^\inf` is equivalent to `0^\inf 1 1 (B1) 0 0 1 0^\inf`.

[0] https://www.sligocki.com/2021/07/17/bb-collatz.html

Why does BB sometimes take one number and sometimes 2? What is the difference between BB(3,3) and BB(3)?

BB(n) refers to Turing machines that have n states and 2 symbols. The version with two arguments lets you specify the number of states and the number of symbols respectively.

So BB(n) = BB(n, 2) .

Are they fundamentally different or could you always map a BB(x,y) to a BB(z), where presumably z is much larger than x?

A universal Turing machine can be made with two symbols, so in the sense that there's a reduction from one to the other, yes.

I would say a better question is to determine if there's some type of polynomial time/space reduction from BB(x,y) to BB(z), in construction and runtime. I suspect yes though I wouldn't be able to rattle off a proof without a lot of effort. See [1] which might answer this question.

[0] https://en.wikipedia.org/wiki/Universal_Turing_machine

[1] https://cs.stackexchange.com/questions/63136/does-the-amount...

Reply on news.ycombinator.com