[One-sided] Turing machines

The Turing machines used here in effect have tapes that extend only to the left, and have no explicit halt states. (They thus differ from the Turing machines which Marvin Minsky and Daniel Bobrow studied in 1961 in the s = 2, k = 2 case and concluded all had simple behavior.) One can think of each Turing machine as computing a function f[x] of the number x given as its input. The function is total (i.e. defined for all x) if the Turing machine always halts; otherwise it is partial (and undefined for at least some x). Turing machines can be numbered according to the scheme on page 888. The number of steps before a machine with given rule halts can be computed from (see page 888)

Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2〚1〛] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i  0, Return[t]], {t, tmax}]]

Of the 4096 Turing machines with s = 2, k = 2, 748 never halt, 3348 sometimes halt and 1683 always halt. (The most rarely halting are ones like machine 3112 that halt only when x = 4j - 1.) The number of distinct functions f[x] that can be computed by such machines is 351, of which 149 are total. 17 machines compute x + 1; none compute x + 2; 17 compute x - 1 and do not halt when x = 0—an example being 2575. Most machines compute functions that involve digit manipulations without traditional interpretations as mathematical functions. It is quite common to find machines that compute almost the same function: 1507 and 1511 disagree (where 1507 halts) only for x ≥ 35. If t[x] is the number of steps to compute f[x] then the number of distinct pairs {f[x], t[x]} is 492, or 230 for total f[x]. In 164 t[x] does not increase with the number of digits n in x, in 295 it increases linearly, in 27 quadratically, and in 6 exponentially. For total f[x] the corresponding numbers are 84, 136, 7, 3; the 3 machines with exponential growth are 378 (example (f) on page 761), 1953 and 2289; all compute trivial functions. Machine 1447 (example (e)) computes the function which takes the digit sequence of x and replaces its first 3 + IntegerExponent[x + 1, 2] 0's by 1's.

Among the 2,985,984 Turing machines with s = 3, k = 2, at least 2,550,972 sometimes halt, and about 1,271,304 always do. The number of distinct functions that can be computed is about 36,392 (or 75,726 for {f[x], t[x]} pairs). 8934 machines compute x + 1 (by 25 different methods, including ones like machine 164850 that take exponential steps), 14 compute x + 2, and none compute x + 3. Those machines that take times that grow precisely like 2ⁿ all tend to compute very straightforward functions which can be computed much faster by other machines.

Among the 2,985,984 Turing machines with s = 2, k = 3, at least 2,760,721 sometimes halt, and about 974,595 always halt. The number of distinct functions that can be computed is about 315,959 (or 457,508 for {f[x], t[x]} pairs). (The fact that there are far fewer distinct functions in the s = 3, k = 2 case is a consequence of equivalences between states but not colors.)

Among the 2³² Turing machines with s = 4, k = 2 about 80% at least sometimes halt, and about 16% always do. Still none compute x + 3. And no Turing machine of any size can directly compute a function like x², 2x or Mod[x, 2] that involves manipulating all digits in x.