view release on metacpan or  search on metacpan

Turing.pm  view on Meta::CPAN

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
(:).  These specify
the actions to be taken by the machine
and the next state to be assumed by the machine (any alphanumeric
string).
The first field may contain any combination of these commands,
separated by commas:

  Px  print symbol <x> (character string without blanks) on the tape
  R   move the tape one square to the right
  L   move the tape one square to the left
  E   "erase" the current square on the tape (i.e., make it a blank)

The symbol to be printed cannot contain blanks.
If the first field is empty, the machine will do nothing. For example:

  'Phohum, R:NEXT'  Write 'hohum', move tape forward, enter state NEXT
  'PX, L:5'         Write 'X', move tape backward, enter state 5
  'L, P1:Q'         Move tape backward, write '1', enter state Q
  ':STOP'           Do not write, don't move the tape, go to STOP

There are two reserved states: START and STOP.  The machine always
begins in state START and stops when it enters state STOP.

=item B<init_tape> STARTPOS LIST

Writes symbols to the tape.  You may use this method to initialize
the tape before starting the machine.  STARTPOS is the position of
the tape to start writing in; there may be any number of symbols
after that.

=item B<step>

After the machine has been specified, this method will execute
one instruction (one state transition) on the machine.
It returns the resulting state of the machine, which is also stored
in C<$machine-E<gt>{cur_state}>.

=item B<run> L R

Runs the machine, beginning at state START.  After each step, the
current machine state and part of the tape will be printed.  The
machine will stop when it reaches the STOP state or when the maximum
number of steps has been executed. L and R are as defined for
print_tape().

=item B<print_tape> L R

Prints part of the current contents of the tape: the symbol under
the read/write head, L symbols to the left of it, and R symbols
to the right.  Both L and R default to 2.

=back

=head1 EXAMPLE

The following example computes the logical OR of two symbols.

  use Acme::Turing;
  $m1 = Acme::Turing->new();
  $m1->init_tape(100, '0', '1');
  $m1->add_spec('START:0', "R:MAYBE");
  $m1->add_spec('START:1', "R:IGNORE");
  $m1->add_spec('MAYBE:1', "R, Ptrue:STOP");
  $m1->add_spec('MAYBE:0', "R,Pfalse, R:STOP");
  $m1->add_spec('IGNORE:ANY', "R,Ptrue:STOP");
  $m1->run();

=head1 USEFULNESS

Well, uh, this module isn't really useful for much of anything.

=head1 REFERENCES

Alan M. Turing, "On Computable Numbers, with an Application to the
Entscheidungsproblem", I<Proceedings of the London Mathematical
Society>, 2nd series, 42 (1936-37), 230-265.

This paper is also reprinted in his I<Collected Works>,
specifically in I<Mathematical Logic>,
ed. R. O. Gandy and C. E. M. Yates
(Amsterdam: Elsevier Science, 2001).
At this writing, it is also available at
http://www.abelard.org/turpap2/tp2-ie.asp.

John von Neumann, "The General and Logical Theory of Automata", in
I<The World of Mathematics> (New York: Simon and Schuster, 1956),
vol. 4, p. 2093.

Von Neumann's description is more restrictive than Turing's.
To emulate the machine that von Neumann describes, you must restrict
your tape to two possible symbols ('0' and '1', for instance, or
' ' and 'X') and perform no more than one write and one tape movement
per step.  He also designates the machine states by numbers (0..n)
rather than by arbitrary character strings.

=head1 AUTHOR

Geoffrey Rommel (GROMMEL@cpan.org), January 2003.

=cut