2023/10/16/bb-3-3-is-hard

[utterances-bot]

BB(3, 3) is Hard | sligocki

I’m excited to share a 3 state, 3 symbol Turing Machine that cannot be proven to halt or not (when starting on a blank tape) without solving a Collatz-like problem. Therefore, solving the (BB(3, 3)) problem is at least as hard as solving this Collatz-like problem, a class of problem for which Paul Erdős famously said: “Mathematics may not be ready for such problems.”

https://www.sligocki.com//2023/10/16/bb-3-3-is-hard.html

[nickdrozd]

My backward reasoner is unable to verify that Bigfoot cannot halt. So that is a piece of weak evidence in favor of it being difficult to decide. On the other hand, it is possible to verify that none of the Bigfoot extensions can blank the tape.

[sligocki]

On the other hand, it is possible to verify that none of the Bigfoot extensions can blank the tape.

Well, since Bigfoot never writes 0s that's a pretty straightforward argument :)

[sligocki]

LegionMammal978 noticed further that b is always even after the B transitions listed above, so we can define C(a, b) = B(a, 2b) = A(a, 4b+1, 2) and a new table of 81 cases here (starting with C(a, 81k + 0) -> C(a+1, 256k + 2) and ending with C(a, 81k + 80) -> C(a+1, 256k + 255))

[tcosmo]

I compiled the machine by hand to using 2 symbols and 8 states: https://bbchallenge.org/1RB1RC_1RE1RE_1LD0RA_1RB1LG_1LG1RF_0RE1RE_1LH0LH_---1LC

The encoding used for symbols is 0: 00, 1: 11, 2: 10.

I was surprised to get it down to only 8 states, this bings knowledge on the hardness of S(8) which is cool!

[sligocki]

Awesome, thanks @tcosmo! I can confirm this TM has the same behavior using the mapping:

0: 00
1: 11
2: 10

 A>:  A>
<A : <C
 B>:  E>
<C : <G

[LegionMammal978]

As an exercise, I've computed how many TM steps each iteration of this function takes. For A(a, b, c) in general, the step counts for the primitive iterations are:

A(a, 0, 0) -> A(a+2, 0,   1):   12a+21
A(a, 0, c) -> A(a,   c-1, 2):   4a+2c+13   [c ≥ 1]
A(a, 1, 0) -> A(a+3, 0,   1):   8a+30
A(a, 1, c) -> A(a+1, c-1, 3):   4a+6c+29   [c ≥ 1]
A(a, 2, c) -> A(a-1, 0,   c+4): 12c+34     [a ≥ 1]
A(a, 3, c) -> A(a,   c+1, 5):   4a+10c+91
A(a, 4, c) -> A(a+1, c+3, 2):   4a+14c+63
A(a, 5, c) -> A(a,   c+5, 3):   4a+18c+103
A(a, b, c) -> A(a,   b-6, c+8): 24c+128    [b ≥ 6]
A(0, 2, c) -> Halt(2c+7): 8c+19

For the derived iterations of A(a, b, c) in this post, the step counts are:

A(a, 6k,   c) -> A(a,   8k+c-1, 2): 8k(12k+3c+4)+4a+16k+2c+13    [8k+c ≥ 1]
A(a, 6k+1, c) -> A(a+1, 8k+c-1, 3): 8k(12k+3c+4)+4a+48k+6c+29    [8k+c ≥ 1]
A(a, 6k+2, c) -> A(a-1, 8k+c+3, 2): 8k(12k+3c+4)+4a+112k+14c+51  [a ≥ 1]
A(a, 6k+3, c) -> A(a,   8k+c+1, 5): 8k(12k+3c+4)+4a+80k+10c+91
A(a, 6k+4, c) -> A(a+1, 8k+c+3, 2): 8k(12k+3c+4)+4a+112k+14c+63
A(a, 6k+5, c) -> A(a,   8k+c+5, 3): 8k(12k+3c+4)+4a+144k+18c+103
A(0, 6k+2, c) -> Halt(16k+2c+7): 8k(12k+3c+4)+64k+8c+19
A(a, 0, 0) -> A(a+2, 0, 1): 12a+21
A(a, 1, 0) -> A(a+3, 0, 1): 8a+30

For the reduced iteration B(a, 81k + r) → B(a + Δa, 256k + s), the step count depends on r. It takes at least 808800k² + 37728k + 16a + 406 steps for r = 0, and at most 808800k² + 1638528k + 16a + 829842 steps for r = 80. Similarly, the reduced iteration C(a, 81k + r) → C(a + Δa, 256k + s) takes at least 3235200k² + 75456k + 16a + 406 steps for r = 0, and at most 3235200k² + 6471552k + 16a + 3236326 steps for r = 80.

[Iijil1]

I think I have a compilation of bigfoot to 2 symbols 7 states: 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB

it uses encoding 0->00, 1->11, 2->10. I found it with an experimental 4 to 2 symbol compiler, so some verification is needed. More info on discord.

[sligocki]

I think I have a compilation of bigfoot to 2 symbols 7 states: 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB

I can confirm this with the details (left is original 3x3 Bigfoot, right is @Iijil1's 7x2 version):

0: 00
1: 11
2: 10

 A> :  A>
<A  : <B
 B> :  D>
<C  : <F

A> 0  -->  1 B>  :  A> 00  -->  11 D>
A> 1  -->  2 A>  :  A> 11  -->  10 A>
A> 2  -->  <C 1  :  A> 10  -->  <F 11

0 <A  -->  1 B>  :  00 <B  -->  11 D>
1 <A  -->  2 A>  :  11 <B  -->  10 A>
2 <A  -->  <C 1  :  10 <B  -->  <F 11

B> 0  -->  <C 2  :  D> 00  -->  <F 10
B> 1  -->  1 B>  :  D> 11  -->  11 D>
B> 2  -->  2 B>  :  D> 10  -->  10 D>

0 <C  -->  Halt  :  00 <F  -->  Halt 
1 <C  -->  <A 2  :  11 <F  -->  <B 10
2 <C  -->  <A 1  :  10 <F  -->  <B 11

Note that in original TM we never have <B nor C>, so those don't need to be encoded/checked.