Under 5n+1, it seems like 7 diverges to infinity, but who knows, it might hit 1.
“Does 7 eventually hit 1?” is equivalent to “Does the following 13-state Turing Machine halt on the blank tape?”
initial A, accept Z, A _ K 1 r, B _ Z 1 r, B 1 D 1 r, D _ F 1 l, D 1 E 1 r, E _ K _ r, E 1 D 1 r, F _ F _ l, F 1 G _ l, G _ H _ r, G 1 I _ r, H _ H _ r, H 1 B _ r, I _ I _ r, I 1 D 1 l, J _ B _ r, J 1 K _ r, K _ L _ r, K 1 K 1 r, L _ M 1 l, L 1 M 1 r, M _ L 1 r, M 1 N 1 l, N _ J 1 l, N 1 N 1 l
This TM can be pasted into this simulator (“New Program”, paste the above TM text, delete anything in the Input box, and hit Start).
It first writes seven 1s onto the tape, then runs the 5n+1 procedure. Kinda fun to watch.
Can anybody find a smaller two-symbol TM that halts iff 7 goes to 1? “Two-symbol” means (0, 1) with no extra blank symbol (#), and the initial tape is all 0s.
I engineered this one by copying clever, local procedures employed by 2-state and 3-state busy-beaver champions. So, part nurture, part nature.
Maybe it’s possible to automatically search through 6- and 7-state machines to find one that seems to be running 5n+1 on 7? That is, somehow generating at intermediate steps the sequence 7-36-18-9-46-23-… (or 7-18-9-23-…). Or maybe more clever engineering would do it.
A small TM would solidify “5n+1 on 7 => 1?” as objectively the simplest unsolved math problem known to humans 