[seqfan] Re: Turing machine sequences

[Frank Adams-Watters]

This is the kind of thing I sometimes look at but wind up abandoning. The thing is, there a lots of ways to read the tape when you decide to. Allan suggests 3, but one can also look at the position of the machine head relative to the start position; or one can read the tape as a binary number - forward or backwards. counting all cells with a mark or only those to the right of the initial position or only to the right of the current position, etc. Unless you can choose some small number of these possibilities, it's just too diffuse.

For the busy beaver problem, there are two main sequences: A028444, the number of 1's on the tape, and A060843, the number of steps. I would suggest limiting to these two, at least at first. These are Allan's first and third kinds.

The first of these will generate every recursive sequence if a big enough machine is used. Straightforward enough.

The second obviously does not - it only generates strictly increasing sequences. It seems obvious that it does not generate all recursive strictly increasing sequences, but I don't see how to prove it off hand.

Franklin T. Adams-Watters

-----Original Message-----
From: Allan Wechsler <acwacw at gmail.com>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Mon, Sep 21, 2015 3:34 pm
Subject: [seqfan] Turing machine sequences


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/