Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


[Turing] machine 600720

(Case (h) of page 763.) The maximum halting times for the first few sizes n are

{5, 159, 161, 1021, 5419, 315391, 1978213883, 1978213885, 3018415453261}

These occur for inputs {1, 2, 5, 10, 26, 34, 106, 213, 426} and correspond to outputs (each themselves maximal for given n)

2^{3, 23, 24, 63, 148, 1148, 91148, 91149, 3560523}-1

Such maxima often seem to occur when the input x has the form (20 4^s - 2)/3 (and so has digits {1, 1, 0, 1, 0, …, 1, 0}). The output f[x] in such cases is always 2^u-1 where

u=Nest[(13+(6#+8)(5/2)^IntegerExponent[6#+8,2])/6&,1,s+1]

One then finds that 6u+8 has the form Nest[If[EvenQ[#],5#/2,#+21]&,14,m] for some m, suggesting a connection with the number theory systems of page 122. The corresponding halting time t[x] is Last[Nest[h, {8, 4s + 24 }, s]] - 1 with

h[{i_, j_}] := With[{e = IntegerExponent[3i + 4, 2]}, {13/6 + (i + 4/3)(5/2)^(e + 1), ((154 + 75(i + 4/3)(5/2)^e)^2 - 16321 - 7860i - 900i^2 + 3360e )/3780 + j}]

For s>3 it then turns out that f[x] is extremely close to 3560523 (5/2)^r, and t[x] to 18865098979373 (5/2)^(2 r), for some integer r.

It is very difficult in general to find traditional formulas for f[x] and t[x]. But if IntegerDigits[x,2] involves no consecutive 0's then for example f[x] can be obtained from

2^(b[Join[{1, 1}, #], Length[#]] &[IntegerDigits[x, 2]]) - 1 a[{l_, _}, r_] := {l + (5r - 3#)/2, #} &[Mod[r, 2]] a[{l_, 0}, 0] := {l + 1, 0} a[{l_, 1}, 0] := {(13 + #(5/2)^IntegerExponent[#, 2])/6, 0} &[6l + 2] b[list_, i_] := First[Fold[a, {Apply[Plus, Drop[list, -i]], 0}, Apply[Plus, Split[Take[list, -i], #1 == #2 != 0 &], 1]]]

(The corresponding expression for t[x] is more complicated.) A few special cases are:

f[4s] = 4s+3 f[4s+1] = 2f[2s]+1 f[2^s-1] = 2^((10s+5+3(-1)^s)/4)-1

How the halting times behave for large n is not clear. It is certainly possible that they could increase like NestList[#^2 &, 2, n], or 2^2^n, although for x=(20 4^s - 2)/3 a better fit for n\[LessTilde]200 is just 2^(2.6 n), with outputs increasing like 2^2^(1.3 n).


From Stephen Wolfram: A New Kind of Science [citation]