num(5) = 165

[Andrés Sancho]

I created a program that checked all halting 5-state machines and determined the longest string of contiguous 1s that could be generated by them: https://github.com/MatterAndy/BB5-contiguous-1s

My original record was a string of 164 1s generated by machines 0RB1LD_1LC1RB_1LD1RE_1LA1LE_---0RC and 1RB1LA_1RC1LE_1RD1RE_0LA1RC_---0LB. Shawn Ligocki noted that this could be improved by adding an explicit halting instruction that wrote an additional 1 like in the machines 0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC and 1RB1LA_1RC1LE_1RD1RE_0LA1RC_1RZ0LB, which achieved a record of 165. Since all halting machines were checked, this means that 165 is the maximum length of a string of contiguous 1s that can be generated by any halting 5-state machine.

Shawn Ligocki also created a wiki entry (https://wiki.bbchallenge.org/wiki/0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC) and an analysis for the champion machine:

A(a, b) = $ 1^a <A 11^b $

A(a+3, b) -> A(a, b+2)
A(0, b) -> A(2b, 1)
A(1, b) -> A(0, b+1)
A(2, b) -> $ <Z 1^{2b+3} $

A(3k,   1) -> A(4k+2, 1)
A(3k+1, 1) -> A(4k+4, 1)
A(3k+2, 1) -> $ <Z 1^{4k+5} $

@13: A(3, 1)

Trajectory of "a" values starting from A(3, 1):
3 6 10 16 24 34 48 66 90 122 Halt(165)

[Shawn Ligocki]

Great find Andrés!

A couple notes:

• The terminology "num(5)" comes from (Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). A note on busy beavers and other creatures. Mathematical Systems Theory 29 (4), July-August 1996, 375-386.) who (as far as I know) were the first to consider this Busy Beaver variation and list the earlier values in this paper: num(1) = 1, num(2) = 4, num(3) = 6, num(4) = 12. Does anyone know of any previous definition of this function or other investigations into it?
• Note that 1RB1LA_1RC1LE_1RD1RE_0LA1RC_1RZ0LB is just the TNF-1RB form of 0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC (that is to say: the same TM started in state B, since the first transition [A0->0RB] does not change anything on the tape).
  
• By choosing the (slightly unorthodox) 1LZ halting transition in 0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC, we end up with the pleasing final tape 0^inf <Z 1^165 0^inf (that is, the final TM head is just one cell to the left of the contiguous sequence of 1s).

--
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 visit https://groups.google.com/d/msgid/busy-beaver-discuss/2c117e3b-df8d-4a8e-a089-ba3cc3ff5ac7n%40googlegroups.com.