Virtual Turing Machine (VTM)
$M = new VTM();
$M->tape("_1_");
$M->blank("_");
$M->start_state("start");
$M->set_instruction("start", "1", "start", "_", 1);
$M->step();
The VTM.pm module emulates a Turing machine as a Perl object. You can write your own instruction input for it or use the supplied ones.
A Turing machine is theoretical computer consisting of a finite set of internal states, a finite alphabet that includes a blank symbol, and a finite set of instructions. It has a physical head and a physical infinitely long tape, which is divided into cells. The cell values consist of the alphabet. The tape has a finite number of non-blank cells. The head can read and write to the cells and move the tape one cell to the left and one cell to the right.
An instruction is defined as a five tuple: initial state, read value, final state, write value, movement. The inital state is the current internal state of the machine. The read value is the value of the cell the head is currently positioned at. The final state becomes the new state of the machine. The write value overwrites the cell the head is positioned at. Movement specifies which direction the head moves, either left or right.
When the machine does not have an instruction for a given internal state and cell value, it will halt. The Turing machine will start at the leftmost non-blank cell on the tape (if there are no non-blank cells in the tape, the VTM will start in the middle of the tape).
The VTM's state names consist of letters, underscores, plus signs, minus signs, asterixes, less than signs, greater than signs, equal signs, and forward slashes. There are no restrictions on length or what the first character is.
The VTM's alphabet is fixed. It consists of letters, numbers, underscores, plus signs, minus signs, asterixes, forward slashes, backslashes, less than signs, greater than signs, equal signs, periods, exclamation marks, at signs, dollar signs, percentage, ampersands, parentheses, square brackets, braces, pipes, single quotation marks, double quotation marks, and pipes. (Phew!)
All the interactions with the VTM is handled through methods. This means you do NOT look inside the internal structure. Got it?
new()
Creates a new instance. This method does not accept any arguments.
is_not_run()
Returns 1 if the machine hasn't been run yet, 0 otherwise. The status of the VTM must be ``not_run'' to change its options (e.g., to add instructions, set modes, etc.).
is_halted()
Returns 1 if the machine is halted after executing, 0 otherwise.
is_in_infinite_loop()
Returns 1 if the machine is in a detectable infinite loop, 0 otherwise.
is_executing()
Returns 1 if the machine is currently executing, 0 otherwise.
error_msg()
Methods that return errors will set an error message. This method will return that error message.
blank($blank_char)
blank($string)
Sets $blank_char as the machine's symbol for the blank character. The status of the machine must be ``not_run''. If $blank_char is a string of more than one character, then only the first character is used. Returns the new blank character.
blank()
Without an argument, $M->blank() returns the machine's blank
character. If no blank character is set, an empty string is returned.
tape($tape_string)
tape(@tape)
tape(\@tape)
With an argument, tape() sets the machine's initial tape. The status
of the machine must be ``not_run''. It returns 1 if the tape was set
successfully, 0 otherwise (in case the tape given is not valid).
tape()
Without an argument, tape() returns the machine's current tape as a
list.
start_state($start_state)
Sets the starting state of the machine. The status of the machine must be ``not_run''. Returns the starting state of the machine.
start_state()
Returns the starting state of the machine. If there is no start state, an empty string is returned.
infinite_tape($boolean)
If $boolean is true, then infinite tape mode is enabled. Otherwise, it's disabled. Infinite tapes are simulated by having the tape grow as needed. By default, the VTM simulates an infinite tape. If you do use infinite tapes, see $M->offset(), which will return how far the tape grew to the left. If you don't use infinite tapes, be aware that the VTM will halt when the head goes past either end of the tape.
infinite_tape()
Without an argument, $M->infinite_tape() returns 1 if it the machine
is simulating infinite tapes, 0 otherwise.
infinite_loop_check($boolean)
If $boolean is true, then infinite loop checking is enabled. Otherwise, it's disabled. By default, the VTM attempts to detect infinite loops.
By no means does the VTM detect all infinite loops, but I'm working on it :-). Currently, the VTM detects infinite loops in two ways. The first is by checking the ``total state'' of the machine (which consists of the internal state, the position of the head, and the tape) and making sure the current total state has not been previously encountered. The second applies only to infinite tapes, by detecting machines with states that do nothing but go to the left or nothing but go to right.
You can only set infinite loop checking when the VTM's status is ``not_run.''
infinite_loop_check()
Without an argument, returns 1 if infinite loop checking is on, 0 otherwise.
half_step($boolean)
If $boolean is true, then half-step mode will be enabled. Otherwise,
it's disabled. With half-step mode on, $M->step() needs to be called
twice for the Turing machine to complete a full step. In the first
half-step, $M->step() will write the new cell value and change to a
new state. In the second half-step, $M->step() will move the position
of the head.
You can only set the half-step mode when the VTM's status is ``not_run.''
half_step()
Without an argument, $M->half_step() will return 1 if half-step mode
is on, 0 otherwise.
Adds the instruction to the machine's set, returning 1 if the instruction was added sucessfully, 0 otherwise. The status of the machine must be ``not_run''.
$i_state and $f_state must be valid state names, $r_cell and $w_cell must be valid cell values, and $movement must be -1 for left or 1 for right.
Returns 1 if successful, 2 if successful but the instruction already existed, or 0 if unsuccessful.
parse_instruction($line)
Adds a single line of a Virtual Turing Machine Language (VTML) instruction. You cannot add instructions unless the status of the VTM is ``not_run.''
Returns 1 if successful, 2 if successful but the instruction already existed, or 0 if unsuccessful.
Deletes the given instruction from the Turing machine. You cannot delete instructions unless the status of the VTM is ``not_run.''
Returns 1 on success, 0 on failure.
start()
Initializes the Turing machine to begin executing instructions. It is
unnecessary to call this, as $M->step() will do so if required.
Returns 1 if the machine has all the necessary information to start, 0
otherwise.
reset()
Resets the status of the VTM to ``not_run.'' Call this after the VTM has been executing instructions, and wish to change some options of the VTM.
step()
Executes either a complete step or half step of a Turing machine,
whether or not half-step mode was set (see $M->half_step() above).
$M->step() returns 1 if an instruction was executed, 0 if there were
no instructions to execute or there were no instructions to execute.
position()
Returns the position, which is an integer, of the head in the tape. A position of 0 always refers to the first cell in the tape, even when an infinite tape grows to the left.
Calling this method before the machine is run does not make sense.
state()
Returns the current internal state of the machine.
Calling this method before the machine is run does not make sense.
offset()
Returns how far the tape grew to the left. With finite tapes, this
will always return 0, because finite tapes do not grow. See
$M->infinite_tape() above.
Calling this method before the machine is run does not make sense.
valid_state_name($state_name)
valid_state_name() will return 1 if $state_name is valid, 0 otherwise.
It is a class method.
valid_cell_value($cell)
Returns 1 if $cell is a valid cell value, 0 otherwise. It is a class method.
valid_tape($tape)
Returns 1 if the $tape is a valid tape, 0 otherwise. $tape must be a string. This is a class method.
Paul R. C. Ming <prcm@nmt.edu>
<http://www.nmt.edu/~prcm/turing/>
Please report bugs to the author with the conditions to reproduce the bug. The author also appreciates fixes for bugs.
vtm(1)
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.