[seqfan] Re: Turing machine sequences

[Allan Wechsler]

I want to clarify that in the case of "binary" machines, as I originally
suggested, with only 1 and 0 as tape symbols, the formalism I suggested
will not work with the generality I had hoped. If a sequence of the first
kind returns to 0, it must be periodic, because when the value is 0, the
tape is all 0's, and the machine has returned to its original state. So,
for example, A000035 (0,1,0,1,0,1,...) cannot be implemented as a Turing
sequence of any of the three kinds I proposed. That is why, with some
disappointment, I am starting to think about "ternary" machines, which have
three tape symbols.

On Mon, Sep 21, 2015 at 6:22 PM, Frank Adams-Watters <franktaw at netscape.net>
wrote:

> 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/
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>