[seqfan] Re: Turing machine sequences

[Brad Klee]

I had a similar idea, but I thought of recording the state at each instant of time. This bears no reference to markings on the tape, but could still be an interesting sequence.

Another related idea is to look at other machines. For example, output of fractran programs are frac sequences.

Thanks,

Brad

> On Sep 21, 2015, at 3:02 PM, Allan Wechsler <acwacw at gmail.com> wrote:
> 
> 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.
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/