[seqfan] Turing machine sequences

[Allan Wechsler]

I would like to (tentatively) propose an investigation into sequences that
can be generated by simple Turing machines.

For the moment, for simplicity, I confine my comments to machines with only
two tape symbols, 0 and 1. Rather than a termination state, I propose that
a sequence-generating machine have a particular "sample state", and every
time it enters the sample state it generates a sequence element.

I presume that the machine always starts with an empty tape (that is, all
0's). We lose no generality here, since if we require a special initial
pattern of 1's, we can arrange that the machine write them before entering
the sample state for the first time.

I propose the following definitions: a Turing sequence of the first kind is
obtained by recording the number of 1's on the tape whenever the machine
enters the sample state; one of the second kind by recording the number of
cells between the leftmost and rightmost 1 (inclusive); and one of the
third kind by recording the total number of steps the machine has taken.
(Alternatively, we could call these "count", "span", and "step" sequences.)

Now the natural question is: what is the smallest number of states needed
to produce a Turing sequence that is not already in OEIS? I think there are
only two one-state sequences (of any kind), A001477 (0,1,2,3,...) and
A000004 (0,0,0,0,...). It would surprise me if we didn't have all the
two-state sequences, but I wonder if we have all the three-staters.

Any well-defined sequence can be expressed as a Turing sequence (this is
one form of the Church-Turing Thesis), but the minimum number of states
required to do so provides a sort of measure of how "simple" the sequence
is. It would be fun to try to produce minimal Turing machines that generate
classic sequences.