A (4,3) TM that never halts

[Pascal Michel]

On May, 25, 2023, in Discord bbchallenge #inductive, uni considered the following (4,3) Turing machine

1RB2RA0LB 0LB2LC1RD 0LD1LB1RZ 1RA2RD0RA

and claimed that this TM halts in about 10^^^(10^^3068)) steps.

Here I give a study of this TM, proving that it never halts.

Let D(a, b, c) = 0^inf (D0) 0 (21)^a 2 0^b (012)^c 0^inf

Then we have:

(1) 0^inf (A0) 0^inf --( 58 )--> D(1,0,2)

(2) if k, m >= 0, D(a(k), k, m + 1) --( t(k + 1, a(k) - k - 1) ) --> D(a(k + 1), k + 1, m)

(3) if n >= 0, k > 0, D(n + k, k, 0) --( t(k, n) + 3(u(k, n) - 1)^2 + 15(u(k, n) - 1) + 24 )--> D(1, 0, u(k, n))

with

if n >=0, u(1, n) = n + 3,

if k, n >= 0, u(k + 2, n) = U(k + 1, n + 3, a(k) - k - 1),

a(0) = 1,

if k >= 0, a(k + 1) = u(k + 1, a(k) - k - 1),

if m, n >=0, k > 0, 

U(1, m, n) = 2m + n + 1,

U(k, 0, n) = n + k,

U(k, m + 1, n) = u(k, U(k, m, n) - k).

t(k, n) is such that

D(n + k, k, 0) --( t(k, n) )--> D(u(k, n) - 1, 0, 0),

D(n + k, k - 1, m + 1) --( t(k, n) )--> D(u(k, n), k, m),

and we have

D(n, 0, 0) --( 3n^2 + 15n + 24 )--> D(1, 0, n + 1).

For example, we have

u(2, n) = 2n + 7, u(3, n) = 3x2^(n + 4) - 3, u(4, n) = about 2^^(n + 5),

and, if k and n are large numbers, u(k, n) = about 2^^ ...^n with (k - 2) "^".

a(1) = 3, a(2) = 9, a(3) = 3069, a(4) = about 2^^3070.

t(1,n) = 12n + 24,

t(2,n) = 12n^2 + 102n + 186,

t(3,n) = 9x4^(n + 5) - 27x2^(n + 5) - 18,

and, if k and n are large numbers, t(k,n) = about 4 u(k,n)^2.

U(2, m, n) = (2^m)(n + 5) - 3.

Then we have the following computation of this TM:

0^inf (A0) 0^inf

--( 58 )--> D(1, 0, 2)

--( 24 )--> D(3, 1, 1)

--( 300 )--> D(9, 2, 0)

--( 3012 )--> D(1, 0, 21)

--( 24 )--> D(3, 1, 20)

--( 300 )--> D(9, 2, 19)

--( 37,693,422 )--> D(3069, 3, 18)

--(  )--> D(a(4), 4, 17)

...

--(  )--> D(a(21), 21, 0)

--(  )--> D(1, 0, u(21, a(21) - 21))

--( 24 )--> D(3, 1, u(21, a(21) - 21) - 1)

--( 300 )--> D(9, 2, u(21, a(21) - 21) - 2)

...

The configurations are D(a(k), k, m), with k increasing and m decreasing,

until m = 0, where k is set to 0 and m becomes a large number: D(a(0), 0, m).

The machine never halts.

[uni...@fu-solution.com]

sorry for the wasted effort.

i've brushed up the code and fixed the bug and the good news is that i found an unintended limitation along the way => new 3x4 and 4x3 scans are in progress and interesting machines are piling up in the logs. this time i'll check them first with Shawn's validator when i get back to it :).

Dátum: utorok 14. mája 2024, čas: 9:37:52 UTC+2, odosielateľ: pascalm...@gmail.com