# BB(3, 3) is Hard

126 views

### Shawn Ligocki

Oct 16, 2023, 4:34:13 PM10/16/23
to Busy Beaver Discuss
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.

See my blog post for all the details: https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html

This is a machine like the "Mother of Giants" I shared last year. I'm proposing calling these sorts of machines "Cryptids" since they are like the legendary creatures: They are rumored to halt or not, but nobody can prove it.

This TM was first identified by @savask on the bbchallenge Discord server.

-Shawn

### Shawn Ligocki

Oct 17, 2023, 11:49:56 PM10/17/23
to Busy Beaver Discuss
@LegionMammal978 on Discord pointed out that we can "simplify" this collatz-like function by repeating it four times at which point the parameter c is fixed as 2 and b is always odd. This also has the advantage of removing the weird parity situation ... but it also makes the function have 81 cases.

Specifically, let B(a, b) = A(a, 2b+1, 2) then: (where each arrow represents 4 iterations of the original A system)

B(a, 81k +  0)  -->  B(a +  1, 256k +   4)
B(a, 81k +  1)  -->  B(a +  0, 256k +   8)
B(a, 81k +  2)  -->  B(a +  1, 256k +  10)
B(a, 81k +  3)  -->  B(a +  0, 256k +  14)
B(a, 81k +  4)  -->  B(a + -1, 256k +  18)
B(a, 81k +  5)  -->  B(a + -2, 256k +  22)
B(a, 81k +  6)  -->  B(a +  2, 256k +  22)
B(a, 81k +  7)  -->  B(a +  1, 256k +  26)
B(a, 81k +  8)  -->  B(a +  0, 256k +  30)
B(a, 81k +  9)  -->  B(a +  4, 256k +  30)
B(a, 81k + 10)  -->  B(a + -2, 256k +  38)
B(a, 81k + 11)  -->  B(a +  2, 256k +  38)
B(a, 81k + 12)  -->  B(a +  1, 256k +  42)
B(a, 81k + 13)  -->  B(a +  0, 256k +  46)
B(a, 81k + 14)  -->  B(a +  1, 256k +  48)
B(a, 81k + 15)  -->  B(a +  0, 256k +  52)
B(a, 81k + 16)  -->  B(a +  2, 256k +  54)
B(a, 81k + 17)  -->  B(a +  0, 256k +  58)
B(a, 81k + 18)  -->  B(a +  2, 256k +  60)
B(a, 81k + 19)  -->  B(a +  1, 256k +  64)
B(a, 81k + 20)  -->  B(a +  0, 256k +  68)
B(a, 81k + 21)  -->  B(a +  1, 256k +  70)
B(a, 81k + 22)  -->  B(a +  0, 256k +  74)
B(a, 81k + 23)  -->  B(a + -1, 256k +  78)
B(a, 81k + 24)  -->  B(a +  3, 256k +  78)
B(a, 81k + 25)  -->  B(a +  0, 256k +  84)
B(a, 81k + 26)  -->  B(a +  1, 256k +  86)
B(a, 81k + 27)  -->  B(a +  0, 256k +  90)
B(a, 81k + 28)  -->  B(a + -1, 256k +  94)
B(a, 81k + 29)  -->  B(a +  3, 256k +  94)
B(a, 81k + 30)  -->  B(a +  2, 256k +  98)
B(a, 81k + 31)  -->  B(a +  1, 256k + 102)
B(a, 81k + 32)  -->  B(a +  0, 256k + 106)
B(a, 81k + 33)  -->  B(a +  1, 256k + 108)
B(a, 81k + 34)  -->  B(a +  3, 256k + 110)
B(a, 81k + 35)  -->  B(a + -1, 256k + 116)
B(a, 81k + 36)  -->  B(a +  3, 256k + 116)
B(a, 81k + 37)  -->  B(a +  0, 256k + 122)
B(a, 81k + 38)  -->  B(a +  1, 256k + 124)
B(a, 81k + 39)  -->  B(a +  0, 256k + 128)
B(a, 81k + 40)  -->  B(a + -1, 256k + 132)
B(a, 81k + 41)  -->  B(a +  0, 256k + 134)
B(a, 81k + 42)  -->  B(a + -1, 256k + 138)
B(a, 81k + 43)  -->  B(a +  1, 256k + 140)
B(a, 81k + 44)  -->  B(a +  2, 256k + 142)
B(a, 81k + 45)  -->  B(a +  1, 256k + 146)
B(a, 81k + 46)  -->  B(a +  0, 256k + 150)
B(a, 81k + 47)  -->  B(a + -1, 256k + 154)
B(a, 81k + 48)  -->  B(a +  3, 256k + 154)
B(a, 81k + 49)  -->  B(a +  2, 256k + 158)
B(a, 81k + 50)  -->  B(a +  1, 256k + 162)
B(a, 81k + 51)  -->  B(a +  2, 256k + 164)
B(a, 81k + 52)  -->  B(a + -1, 256k + 170)
B(a, 81k + 53)  -->  B(a +  0, 256k + 172)
B(a, 81k + 54)  -->  B(a +  2, 256k + 174)
B(a, 81k + 55)  -->  B(a +  1, 256k + 178)
B(a, 81k + 56)  -->  B(a +  2, 256k + 180)
B(a, 81k + 57)  -->  B(a +  1, 256k + 184)
B(a, 81k + 58)  -->  B(a +  0, 256k + 188)
B(a, 81k + 59)  -->  B(a + -1, 256k + 192)
B(a, 81k + 60)  -->  B(a +  0, 256k + 194)
B(a, 81k + 61)  -->  B(a +  2, 256k + 196)
B(a, 81k + 62)  -->  B(a + -2, 256k + 202)
B(a, 81k + 63)  -->  B(a +  2, 256k + 202)
B(a, 81k + 64)  -->  B(a + -1, 256k + 208)
B(a, 81k + 65)  -->  B(a +  0, 256k + 210)
B(a, 81k + 66)  -->  B(a + -1, 256k + 214)
B(a, 81k + 67)  -->  B(a + -2, 256k + 218)
B(a, 81k + 68)  -->  B(a +  2, 256k + 218)
B(a, 81k + 69)  -->  B(a +  1, 256k + 222)
B(a, 81k + 70)  -->  B(a +  0, 256k + 226)
B(a, 81k + 71)  -->  B(a +  1, 256k + 228)
B(a, 81k + 72)  -->  B(a +  3, 256k + 230)
B(a, 81k + 73)  -->  B(a +  2, 256k + 234)
B(a, 81k + 74)  -->  B(a +  1, 256k + 238)
B(a, 81k + 75)  -->  B(a +  2, 256k + 240)
B(a, 81k + 76)  -->  B(a +  1, 256k + 244)
B(a, 81k + 77)  -->  B(a +  0, 256k + 248)
B(a, 81k + 78)  -->  B(a +  1, 256k + 250)
B(a, 81k + 79)  -->  B(a +  1, 256k + 254)
B(a, 81k + 80)  -->  B(a + -1, 256k + 258)

### Tristan Stérin

Oct 22, 2023, 5:11:35 PM10/22/23
I compiled Shawn's 3x3 machine (https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA) by hand to using 2 symbols, and I got it done to 8 states:

The encoding used in the construction is 0: 00, 1: 11, 2: 10.

This would mean that knowing BB(8) is Collatzish-hard -- using BB notation to mean Rado's S.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.

### Pascal Michel

Nov 9, 2023, 3:31:37 AM11/9/23
to Busy Beaver Discuss
I give here more analysis of this (3,3) machine.

If A(a,b,c) = ...0(12)^a (11)^b  < A (11)^c 0..., as defined by Shawn Ligocki, then
(a) If 8k + c > 0, A(a,6k,c) --( 96k^2 + (24c + 48)k + 2c + 4a +13 )--> A(a,8k + c - 1,2)
(b) If 8k + c > 0, A(a,6k + 1,c) --( 96k^2 + (24c + 80)k + 6c + 4a + 29 )--> A(a + 1,8k + c - 1,3)
(c) If a > 0, A(a,6k + 2, c) --( 96k^2 + (24c + 144)k + 14c + 4a + 51 )--> A(a - 1,8k + c + 3,2)
(d) A(a,6k + 3,c) --( 96k^2 + (24c + 112)k + 10c + 4a + 91 )--> A(a,8k + c + 1,5)
(e) A(a,6k + 4,c= --( 96k^2 + (24c + 144)k + 14c + 4a + 63 )--> A(a + 1,8k + c + 3,2)
(f) A(a,6k + 5,c) --( 96k^2 + (24c + 176)k + 18c + 4a + 103 )--> A(a,8k + c + 5,3)
(g) A(0,6k + 2,c) --( 96k^2 + (24c + 96)k + 8c + 19 )--> ...011 < Z 1^(16k + 2c + 4) 20...

If B(a,b) = A(a,2b + 1,2), then
B(a,81k) --( 808800k^2 + 37728k + 16a + 406 )--> B(a + 1,256k + 4)
I did not compute the other cases.