A208229 Consider Wolfram's universal 2-state 3-symbol Turing machine on a one-way-infinite tape with all but the first n cells initially blank and the head initially in state 1. a(n) is the maximum number of steps the Turing machine can make before halting.

3, 3, 15, 19, 37, 51, 69, 97, 111, 161, 167, 241, 247, 327, 341

Offset

0,1

Comments

The head starts in state 1 on the leftmost cell (cell 1.) The machine halts if the head moves to the left of the first cell. a(n) gives the maximum halting time for any of the 3^n initial configurations of the first n cells.

Because the rule (rule 596440) is universal, the halting problem is undecidable for arbitrary tapes. However, it is not known whether universal computation can be achieved with a finite number of nonzero starting cells. Thus, this function might be computable.

Since the head starts in state one, it will immediately move left and halt unless the first cell starts out with a 0.

For initial conditions with n<=11, the machine always halts (the Mathematica code given assumes that the machine halts for all finite configurations). Whether this remains true is an open question.

References

S. Wolfram, A New Kind Kind of Science, Wolfram Media, 2002; p. 709, 1120.

Links

Table of n, a(n) for n=0..14.

Wikipedia, Wolfram's 2-state 3-symbol Turing machine

S. Wolfram, Wolfram 2,3 Turing Machine Research Prize

Example

For n=3, the initial tape 021000000... runs for 19 steps, before terminating in the state 22221200000... with the head one cell to the left of the tape.  This is the longest running time without starting with nonzero symbols further to the right, so a(3)=19

Mathematica

r = {{1, 2} -> {1, 1, -1}, {1, 1} -> {1, 2, -1}, {1, 0} -> {2, 1, 1}, {2,
   2} -> {1, 0, 1}, {2, 1} -> {2, 2, 1}, {2, 0} -> {1, 2, -1}}; len[n_, k_] := Length[NestWhileList[TuringMachine[r, #] &, {{1, 2}, {Prepend[IntegerDigits[k, 3, n], 3], 0}}, UnsameQ, All]] - 2; a[n_] := Max[Table[len[n, k], {k, 0, 3^(n - 1) - 1}]]; Table[a[n], {n, 1, 8}]

Crossrefs

Sequence in context: A353584 A110096 A157526 * A269956 A153512 A369358

Adjacent sequences: A208226 A208227 A208228 * A208230 A208231 A208232

Keyword

nonn,more

Author

Ben Branman, Jan 10 2013

Extensions

a(12)-a(14) from Robert G. Wilson v, Mar 22 2015

Status

approved