BB(3, 3) is Hard

[Shawn Ligocki]

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]

@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]

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:

https://bbchallenge.org/1RB1RC_1RE1RE_1LD0RA_1RB1LG_1LG1RF_0RE1RE_1LH0LH_---1LC

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.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7BG6kp9k3Sb8eyV3z%3DOyoaWKvxxpWjT97ZhrQf0eYQNTw%40mail.gmail.com.

[Pascal Michel]

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.