[seqfan] Re: Turing machine sequences

Brad Klee bradklee at gmail.com
Tue Sep 22 18:44:23 CEST 2015


Hi,

Let's do some explicit computation for the Wolfram-(2,3)-machine (
http://demonstrations.wolfram.com/TheWolfram23TuringMachine/ ). We can
easily compute:

RelativePosition = TuringMachine[{596440, 2, 3}, {1, {{}, 0}}, 50][[All, 1,
3]]
ReadTape =  TuringMachine[{596440, 2, 3}, {1, {{}, 0}}, 50] /. {x_, y_} :>
   y[[x[[2]] ]]
MachineState =  TuringMachine[{596440, 2, 3}, {1, {{}, 0}}, 50][[All, 1, 1]]

{0, 1, 0, -1, 0, 1, 0, 1, 2, 1, 0, -1, -2, -1, 0, -1, 0, 1, 2, 3, 4,
3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 1, 0, -1, -2, -3, -2, -1, -2, -1, 0, 1,
2, 3, 2, 3, 4, 5, 6, 7, 6}

{0, 0, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 0, 2, 2, 0, 1, 1, 2, 0, 0, 1, 0,
2, 2, 0, 1, 0, 2, 1, 1, 2, 2, 1, 1, 0, 2, 2, 0, 1, 1, 1, 2, 2, 0, 1,
1, 2, 0, 0, 1}

{1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 2, 1, 1,
2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2,
2, 2, 1, 2, 1}

These are time-indexed sequences that characterize the machine.

Thanks,

Brad




On Mon, Sep 21, 2015 at 5:32 PM, Allan Wechsler <acwacw at gmail.com> wrote:

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



More information about the SeqFan mailing list