view release on metacpan or  search on metacpan

Turing.pm  view on Meta::CPAN

 my $tp = $self->{'tape_pos'};

 for ($i = $tp - $L; $i <= $tp + $R; $i++) {
    print "    Tape [$i] ", ($i == $tp) ? ">>> " : "    ",
      "$self->{'tape'}[$i]\n";
 }
 return;
}

# Run the machine.
sub run {
 my $self = shift;
 my ($L, $R) = @_;
 $L ||= 2; $R ||= 2;

 my $current_state = 'START';
 my $step_num = 0;
 printf "%4d  %s\n", $step_num, $current_state;
 $self->print_tape(2,2);
 while ($current_state ne 'STOP') {
    print '-' x 60, "\n";
    $current_state = $self->step();
    $step_num++;
    printf "%4d  %s\n", $step_num, $current_state;
    $self->print_tape($L,$R);
    if ($step_num == $self->{'steps'}) {
       print "------> Reached maximum number of steps.\n";
       last;
    }
 }
 print "---> Machine stopped.\n";
 return;
}

1;

__END__

=head1 NAME

Acme::Turing - Turing machine emulation

=head1 SYNOPSIS

  use Acme::Turing;

  $machine = Acme::Turing->new(steps=>$steps);
  $machine->add_spec($conditions, $actions);
  $machine->init_tape($startpos, LIST...);
  $machine->step();
  $machine->print_tape($L, $R);
  $machine->run();

=head1 DESCRIPTION

This module gives you the methods needed to emulate a Turing machine
in Perl.

Why? Because we can.

This module is based on Turing's original paper (see REFERENCES),
which allows complete freedom in the actions to be taken
before the machine enters a new state. You can, of course,
impose restrictions if you wish, as John von Neumann's paper does.
This module allows the states to be designated by any alphanumeric
character string, and any non-blank alphanumeric data can be written
on the tape.

=head1 METHODS

The methods are listed below in the order you would be most likely
to call them in.

=over 2

=item B<new> steps=>STEPS

Creates the Turing machine.  The argument
is optional. It specifies a maximum number of steps that
the machine is allowed to go through before it is forced to stop
(to avoid endless looping); the default is 250 steps. The machine
will be created with a tape that is initially 200 squares in length.
Turing machine
tapes, however, are infinite, so the tape will be automatically made
longer whenever necessary; the only limit on the tape length is the
amount of available storage.

The newly created machine is in the START state.  The tape is
initialized to a series of single blanks (i.e., scalars
of length 1 containing ' ').  The tape head is positioned over the
middle of the tape, i.e. at C<int($tape_length/2)> = 100 =
the 101st symbol. Every square must contain
at least one character; empty strings are not allowed.
Also, blanks may not be written except by "erasing" (see below).

new() returns a hash reference.  The specification for the machine
(C<$machine-E<gt>{spec}>) is empty.
You must then populate the specification
for your machine, as described next.

=item B<add_spec> CONDITIONS ACTIONS

Adds an entry to the specification hash.
You can also add an entry by using this statement:

  $machine->{'spec'}{"my_conditions"} = "my_actions";

Both arguments must be specified.  The first must contain a state
and a tape symbol separated by a colon (:).  For example:

  'START: '            state START; tape contains a single blank
  'OUTOFCONTROL:junk'  state OUTOFCONTROL; tape contains 'junk'
  'COMATOSE:'          invalid; tape must contain a non-empty string

There is one reserved tape symbol: ANY (which really means "any
other").  For instance, if the machine is in the BEHIND state,
you can specify both 'BEHIND:time' and 'BEHIND:ANY'.  If the tape
contains 'time', the actions for 'BEHIND:time' will be executed; if
it contains anything else, 'BEHIND:ANY' will be used.

The second argument must contain two elements separated by colons