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

On Wed, Sep 15, 2004 at 11:53:21AM -0400, colin.rafferty-/PgpppG8B+R7qynMiXIxWgC/[email protected] wrote:
> John J. Trammell wrote:
> > On Wed, Sep 15, 2004 at 10:41:14AM -0400, colin.rafferty-/PgpppG8B+R7qynMiXIxWgC/[email protected] wrote:
> >> Zed Lopez wrote:
> 
> >>> Your program should take two parameters: the filename of a file
> >>> containing the state transition instructions, and the tape's initial
> >>> contents. The filename is required.    
> 
> >>> If an initial value for the tape is specified, the read/write head
> >>> begins over the first character of that initial value.  
> 
> >> I would change the specification of the program to allow for a third
> >> argument which is the head's initial location on the tape.  
> 
> >> It's value is any number, positive or negative, which specifies the
> >> head's position relative to the first character of the second
> >> argument.
> 
> > I'd say this is a perfect example of a customization that a user may
> > wish to apply, but this should be implemented via command-line options,
> 
> I disagree.  I think that without it, you cannot specify any finite
> initial state of a turing machine.
> 
> And since it is a defaulted third parameter, it follows perfectly.
> 
> Anyway, that's how I'm going to implement it, but it's a minor detail.
> The interesting part is trying to model an infinite tape.

I don't think that the argument is necessary, but it is
extremely convenient and I'd also implement it as an optional
3rd argument.  (You could take a turing program, initial state,
and starting location and convert it to another program that
does the same thing but starts at the leftmost data column by
prepending a series of states that simply move right (or left)
the desired number of times.

Other additions that would be useful (but not strictly
necessary) would be:

- allow a wildcard or class match to the symbol being examined
- have a "don't change the current symbol" as an alternative
  to always specifying an explicit replacement symbol
- as well as l and r to move the position left and right,
  permit 0 to stay in place

Using * in the second column to allow matching any symbol
and in the fourth column to denote "leave the current symbol
unchanged" the positioning code could be written as:

INIT * XXX * 0
r5 * r4 * r
r4 * r3 * r
r3 * r2 * r
r2 * r1 * r
r1 * START * r
l5 * l4 * l
l4 * l3 * l
l3 * l2 * l
l2 * l1 * l
l1 * START * l

Simply change the name of the original starting state to START,
and change XXX to the desired starting location (e.g. r5 to
start 4 characters to the right of the first non-blank).
(You would not need to include both r* and l* codes, just
the one that matches the desired direction o offset, and
would have to have at least as many states in the chain as
the desired offset.)  It would be easy to write a program to
apply this sort of change to a program file to accomplish a
desired starting location.  (Such a transformation program would
ensure that the l* state names are chosen to not conflict with
statenames used in the original program, and would determine
the name of the original START state; it could skip writing
the INIT state line - that was just a convenience so that you
can choose an offset just by changing the one line.)

--