Acme::Turing - Turing machine emulation

NAME

Acme::Turing - Turing machine emulation

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();

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.

METHODS

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

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 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 ($machine-{spec}>) is empty. You must then populate the specification for your machine, as described next.

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

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.

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 $machine-{cur_state}>.

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

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.

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();

USEFULNESS

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

REFERENCES

Alan M. Turing, ``On Computable Numbers, with an Application to the Entscheidungsproblem'', Proceedings of the London Mathematical Society, 2nd series, vol. 42 (1936-37), pp. 230-265.

This paper is also reprinted in his Collected Works; I believe it is in the volume Mathematical Logic, ed. R. O. Gandy and C. E. M. Yates (Amsterdam: North-Holland, 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 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.

AUTHOR

Geoffrey Rommel (grommel@sears.com), January 2003.

Acme::Turing - Turing machine emulation