BB(3, 3) is Hard

126 views
Skip to first unread message

Shawn Ligocki

unread,
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

unread,
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

unread,
Oct 22, 2023, 5:11:35 PM10/22/23
to busy-beav...@googlegroups.com
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7BG6kp9k3Sb8eyV3z%3DOyoaWKvxxpWjT97ZhrQf0eYQNTw%40mail.gmail.com.

Pascal Michel

unread,
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.
 

Reply all
Reply to author
Forward
0 new messages