2023/10/16/bb-3-3-is-hard about sligocki.github.io HOT 8 OPEN

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.

from sligocki.github.io.

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

from sligocki.github.io.

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.

from sligocki.github.io.

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.

from sligocki.github.io.

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 :)

from sligocki.github.io.

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

from sligocki.github.io.

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!

from sligocki.github.io.

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.

from sligocki.github.io.