#8210683 does hot halt

Individual machines
1

The following is @djmati1111’s Discord message showing that machine #8210683 does not halt. You can find the original message here:

I looked at https://bbchallenge.org/8210683 today, which is one of the 34 latest holdouts.
There is this “bouncing from side to side” pattern sometimes, as pictured below.
It seems that if “number of 10s on the left” is less than “number of 01s on the right”, the machine stops, which sounds like something that would make it unCTLable.

A quick check shows that the pattern

n*'10' + 'A>00' + n*'01'

is the state of the tape, at some point, for all n<=10:

34       0000010A>000100000000000000000000000000000000000000000000
156      000001010A>0001010000000000000000000000000000000000000000
522      00000101010A>00010101000000000000000000000000000000000000
1540     0000010101010A>000101010100000000000000000000000000000000
4278     000001010101010A>0001010101010000000000000000000000000000
11532    00000101010101010A>00010101010101000000000000000000000000
30622    0000010101010101010A>000101010101010100000000000000000000
80712    000001010101010101010A>0001010101010101010000000000000000
211974   00000101010101010101010A>00010101010101010101000000000000

However, starting from tape n*'10' + 'A>00' + (n+1)*'01' the machine halts:

0010A>000101 -> 0D>111111111
001010A>00010101 -> 0D>1111111111111
00101010A>0001010101 -> 0D>11111111111111111
0010101010A>000101010101 -> 0D>111111111111111111111
001010101010A>00010101010101 -> 0D>1111111111111111111111111
1 Like
2

Probably good to note here: @Iijil found a second proof using weighted automata: Discord

Generalized a little later to cover more members of the class: Discord

1 Like