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

On Wed, Sep 15, 2004 at 05:14:20PM +0100, Roger Burton West wrote:
> 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.

No, that's exactly my point.  You can add instructions to move the
tape-head to the right before executing the actual program.

Why would the instructions need to erase themselves?  They can just use
states that are not used elsewhere in the instructions.


> 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.)

So instead of N initial states, where N is unbounded, there are only N-1
initial states?  ;)


Ronald