Re: Perl Quiz of the Week #24 (Turing Machine simulation)

On Wed, Sep 15, 2004 at 12:06:54PM -0400, Ronald J Kimball wrote:

>You are mistaken.  You can easily include instructions to move the tape
>head to the appropriate position on the tape before executing the actual
>program.

But without it there exist states which are valid, but cannot be
specified as an initial state. (To wit, any states with non-blank cells
to the "left" of the pointer.) The instructions cannot, I think, both
put the pointer in the right place and erase themselves.

In fact, there's another limitation, slightly more easily got round: the
setting of the initial register state by the first state-vector
specification. (But unless you want the program to quit immediately,
there will be at least one line with the desired initial state in that
specification. So it's only a slight limitation on the space of
representable initial states.)

Roger