# VTM.pm -- a Perl module that implements a Turing machine
# Copyright (C) 2000-2001 Paul R. C. Ming
# 
# 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.
# 

=head1 NAME

Virtual Turing Machine (VTM)


=head1 SYNOPSIS

 $M = new VTM();
 $M->tape("_1_");
 $M->blank("_");
 $M->start_state("start");
 $M->set_instruction("start", "1", "start", "_", 1);
 $M->step();


=head1 DESCRIPTION

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!)


=head1 METHODS

All the interactions with the VTM is handled through methods.  This
means you do NOT look inside the internal structure.  Got it?

=cut




package VTM;
use strict;

# Statuses for the Virtual Turing Machines
$VTM::_NOT_RUN       = 0x01;
$VTM::_EXECUTING     = 0x02;
$VTM::_HALTED        = 0x04;
$VTM::_INFINITE_LOOP = 0x08;

$VTM::_STATE_REGEX     = '[-A-Za-z0-9_=<>\+\*\/]+';
$VTM::_CELL_REGEX      = '[-A-Za-z0-9_+\/\\.!\@\$%^&\*\(\)\[\]\{\}\|"`~\<\>';
$VTM::_CELL_REGEX      .= "=']";
$VTM::_SEPARATOR_REGEX = '(?:\s+|\s*,\s*)';
$VTM::_MOVEMENT_REGEX  = '[RLrl+-]';
$VTM::_PARSE_REGEX     = "\\s*($VTM::_STATE_REGEX)$VTM::_SEPARATOR_REGEX($VTM::_CELL_REGEX)$VTM::_SEPARATOR_REGEX($VTM::_STATE_REGEX)$VTM::_SEPARATOR_REGEX($VTM::_CELL_REGEX)$VTM::_SEPARATOR_REGEX($VTM::_MOVEMENT_REGEX)\\s*(?:\#.*)?";
# Yes, that was ugly.

$VTM::_LEFT  = -1;
$VTM::_RIGHT = 1;


=item new()

Creates a new instance.  This method does not accept any arguments.

=cut

# Run of the mill new.
sub new {
    my $class = shift;
    my $self = {
	'rh_instructions' => {},  # Instruction set goes here
	'status'    => $VTM::_NOT_RUN,
	'rl_tape'   => [],     # The tape of the VTM.
	'infinite_tape' => 1,  # By default, the tape is infinite.
	'offset'   => 0,       # Offset of the tape to represent infinite tapes
	                       # (how far it grew to the left).
	'position' => 0,       # Position of the machine's head on the tape.
	'current'  => "",      # Current state.
	'blank'    => "-",     # Blank character for the tape.
	'half_step' => 0,      # Half step mode (see half_step() for details).
	'start_state' => "",   # The starting state of the machine.
	'steps'    => 0,       # Number of steps executed so far.
	'infinite_loop_check' => 1,  # By default, detect infinite loops.
	'rh_encountered' => {},  # The set of tape/position/machine states that
	                         # have already been encountered.  This is
	                         # used to detect infinite loops.
	'error_msg' => "",     # Error message for setting instructions.
    };
    bless($self, $class);
    return $self;
}




=item $M->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.).

=cut

sub is_not_run {
    my $self = shift;
    return $self->{'status'} & $VTM::_NOT_RUN ? 1 : 0;
}




=item $M->is_halted()

Returns 1 if the machine is halted after executing, 0 otherwise.

=cut

sub is_halted {
    my $self = shift;
    return $self->{'status'} & $VTM::_HALTED ? 1 : 0;
}




=item $M->is_in_infinite_loop()

Returns 1 if the machine is in a detectable infinite loop, 0 otherwise.

=cut

sub is_in_infinite_loop {
    my $self = shift;
    return $self->{'status'} & $VTM::_INFINITE_LOOP ? 1 : 0;
}




=item $M->is_executing()

Returns 1 if the machine is currently executing, 0 otherwise.

=cut

sub is_executing {
    my $self = shift;
    return $self->{'status'} & $VTM::_EXECUTING ? 1 : 0;
}




=item $M->error_msg()

Methods that return errors will set an error message.  This method
will return that error message.

=cut

sub error_msg {
    my $self = shift;
    return $self->{'error_msg'};
}




=item $M->blank($blank_char)

=item $M->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.

=item $M->blank()

Without an argument, $M->blank() returns the machine's blank
character.  If no blank character is set, an empty string is returned.

=cut

sub blank {
    my $self = shift;
    if (@_) {
	my $ch = shift;
	# $ch cannot be the empty string
	if ($ch !~ /^(.)/) {
	    return $self->{'blank'};
	}
	else {
	    $self->{'blank'} = $1;
	}
    }
    return $self->{'blank'};
}




=item $M->tape($tape_string)

=item $M->tape(@tape)

=item $M->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).

=item $M->tape()

Without an argument, tape() returns the machine's current tape as a
list.

=cut

sub tape {
    my $self = shift;
    if (@_ == 0) {
	return @{$self->{'rl_tape'}};
    }

    # If we get here, @_ != 0 and we want to set the tape
    unless ($self->is_not_run()) {
	$self->{'error_msg'} = "Status must be not run to set the tape";
	return 0;
    }

    if (@_ == 1) {
	my $tape = shift;
	if (ref($tape) =~ /^ARRAY/) {
	    foreach $_ (@$tape) {
		unless (&VTM::valid_cell_value($_)) {
		    $self->{'error_msg'} = "Contains invalid cell value: $_";
		    return 0;
		}
	    }
	    @{$self->{'rl_tape'}} = @$tape;
	}
	else {
	    @{$self->{'rl_tape'}} = split(//, $tape);
	}
	return 1;
    }
    elsif (@_ > 1) {
	foreach $_ (@_) {
	    unless (&VTM::valid_cell_value($_)) {
		$self->{'error_msg'} = "Contains invalid cell value: $_";
		return 0;
	    }
	}
	@{$self->{'rl_tape'}} = @_;
	return 1;
    }
}




=item $M->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.

=item $M->start_state()

Returns the starting state of the machine.  If there is no start
state, an empty string is returned.

=cut

sub start_state {
    my $self  = shift;

    if (@_) {
	unless ($self->is_not_run()) {
	    $self->{'error_msg'} = ("Status must be not run to set the"
				    . " start state");
	    return $self->{'start_state'};
	}
	my $state = shift;
	$self->{'start_state'} = $state if (&VTM::valid_state_name($state));
    }
    return $self->{'start_state'};
}




=item $M->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.

=item $M->infinite_tape()

Without an argument, $M->infinite_tape() returns 1 if it the machine
is simulating infinite tapes, 0 otherwise.

=cut

sub infinite_tape {
    my $self = shift;
    if (@_) {
	unless ($self->is_not_run()) {
	    $self->{'error_msg'} = ("Status must be not run to set infinite"
				    . " tape mode");
	    return $self->{'infinite_tape'};
	}
	if ($_[0]) {
	    $self->{'infinite_tape'} = 1;
	}
	else {
	    $self->{'infinite_tape'} = 0;
	}
    }
    return $self->{'infinite_tape'};
}




=item $M->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.

=item

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.

=item

You can only set infinite loop checking when the VTM's status is
"not_run."

=item $M->infinite_loop_check()

Without an argument, returns 1 if infinite loop checking is on, 0
otherwise.

=cut

sub infinite_loop_check {
    my $self = shift;
    if (@_) {
	unless ($self->is_not_run()) {
	    $self->{'error_msg'} = ("Status must be not run to set infinite"
				    . " loop checking");
	    return $self->{'infinite_loop_check'};
	}
	if ($_[0]) {
	    $self->{'infinite_loop_check'} = 1;
	}
	else {
	    $self->{'infinite_loop_check'} = 0;
	}
    }
    return $self->{'infinite_loop_check'};
}






=item $M->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.

=item

You can only set the half-step mode when the VTM's status is
"not_run."

=item $M->half_step()

Without an argument, $M->half_step() will return 1 if half-step mode
is on, 0 otherwise.

=cut

sub half_step {
    my $self = shift;
    if (@_) {
	unless ($self->is_not_run()) {
	    $self->{'error_msg'} = ("Status must be not run to set half-step"
				    . " mode");
	    return $self->{'half_step'};
	}
	if ($_[0]) {
	    $self->{'half_step'} = 1;
	}
	else {
	    $self->{'half_step'} = 0;
	}
    }
    return $self->{'half_step'};
}





=item $M->set_instruction($i_state, $r_cell, $f_state, $w_cell, $movement)

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".

=item

$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.

=item

Returns 1 if successful, 2 if successful but the instruction already
existed, or 0 if unsuccessful.

=cut

sub set_instruction {
    my $self = shift;
    my ($i_state, $r, $f_state, $w, $m) = @_;
    my $ret_val;
    unless (&VTM::valid_state_name($i_state)) {
        $self->{'error_msg'} = "Invalid state name: $i_state";
        return 0;
    }
    unless (&VTM::valid_state_name($f_state)) {
        $self->{'error_msg'} = "Invalid state name: $f_state";
        return 0;
    }
    unless (&VTM::valid_cell_value($r)) {
        $self->{'error_msg'} = "Invalid cell value: $r";
        return 0;
    }
    unless (&VTM::valid_cell_value($w)) {
        $self->{'error_msg'} = "Invalid cell value: $w";
        return 0;
    }
    unless ($m == $VTM::_LEFT || $m == $VTM::_RIGHT) {
        $self->{'error_msg'} = "Invalid movement: $m";
        return 0;
    }

    # Does this instruction pair (initial state, read) already exist?
    if (exists($self->{'rh_instructions'}{$i_state})
        && exists($self->{'rh_instructions'}{$i_state}{$r}))
    {
	$self->{'error_msg'} = "Instruction ($i_state, $r) already exists";
	$ret_val = 2;
    }
    else {
	$ret_val = 1;
    }

    $self->{'rh_instructions'}->{$i_state}{$r}{'final_state'} = $f_state;
    $self->{'rh_instructions'}->{$i_state}{$r}{'write'} = $w;
    $self->{'rh_instructions'}->{$i_state}{$r}{'movement'} = $m;
    return $ret_val;
}




=item $M->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."

=item

Returns 1 if successful, 2 if successful but the instruction already
existed, or 0 if unsuccessful.

=cut

sub parse_instruction {
    my $self = shift;
    my $line = shift;
    my ($i_state, $r, $f_state, $w, $m);

    unless ($self->is_not_run()) {
	$self->{'error_msg'} = "Status must be not run to set instructions";
	return 0;
    }

    # Ignore comments and blank lines.
    return 1 if ($line =~ /^\s*$/ || $line =~ /^\s*\#/);

    if ($line =~ /^$VTM::_PARSE_REGEX$/o) {
	$i_state = $1;
	$r       = $2;
	$f_state = $3;
	$w       = $4;
	if ($5 =~ /[Ll-]/) {
	    $m = $VTM::_LEFT;
	}
	else {
	    $m = $VTM::_RIGHT;
	}
	return $self->set_instruction($i_state, $r, $f_state, $w, $m);
    }
    else {
	$self->{'error_msg'} = "Syntax error";
	return 0;
    }
}




=item $M->delete_instruction($initial_state, $read_cell)

Deletes the given instruction from the Turing machine.  You cannot
delete instructions unless the status of the VTM is "not_run."

=item

Returns 1 on success, 0 on failure.

=cut

sub delete_instruction {
    my $self = shift;
    my ($state, $cell) = @_;

    unless ($self->is_not_run()) {
	$self->{'error_msg'} = ("Status must be not run to delete"
				. " instructions.");
	return 0;
    }

    if (exists($self->{'rh_instructions'}{$state}{$cell})) {
	delete($self->{'rh_instructions'}{$state}{$cell});
	return 1;
    }
    else {
	$self->{'error_msg'} = "Instruction ($state, $cell, ...) not found";
	return 0;
    }
}




=item $M->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.

=cut

# start()
# Sets up the Turing machine (i.e. the state and the position of the head on
# the tape, and clears the encountered set).
sub start {
    my $self = shift;
    my $rl_tape = $self->{'rl_tape'};
    my $ra_p = \$self->{'position'};

    unless ($self->is_not_run()) {
	$self->{'error_msg'} = "Status must be not run to start";
	return 0;
    }
    unless (@$rl_tape) {
	$self->{'error_msg'} = "Can't start without a tape";
	return 0;
    }
    unless ($self->{'start_state'} ne "") {
	$self->{'error_msg'} = "Can't start without starting state";
	return 0;
    }
    unless ($self->{'blank'} ne "") {
	$self->{'error_msg'} = "Can't start without blank character";
	return 0;
    }

    $self->{'current'} = $self->{'start_state'};

    # The position should be the leftmost nonblank cell, or the middle of the
    # tape if the tape only has blank cells.
    for ($$ra_p = 0; 
	 $$ra_p < @$rl_tape && $$rl_tape[$$ra_p] eq $self->{'blank'}; 
	 $$ra_p++) 
    { }
    if ($$ra_p == @$rl_tape) {    # Couldn't find a nonblank cell.
	$$ra_p = int(@$rl_tape / 2);
    }

    $self->{'offset'}         = 0;
    $self->{'steps'}          = 0;
    $self->{'rh_encountered'} = {};
    $self->{'status'}         = $VTM::_EXECUTING;
    return 1;
}




=item $M->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.

=cut

# reset()
# Resets the status to NOT_RUN.  Call this after stopping the machine.
sub reset {
    my $self = shift;
    $self->{'status'} = $VTM::_NOT_RUN;
    return 1;
}




=item $M->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.

=cut

# step()
# Executes a single step of the Turing machine.
sub step {
    my $self = shift;
    my $total_state;                     # For checking infinite loops
    my $blank = $self->{'blank'};        # Less typing.
    my $ra_c;                            # Ref to cell in the tape
    my $ra_p = \$self->{'position'};     # Ref to position
    my $ra_s = \$self->{'current'};      # Ref to current state
    my $rl_tape = $self->{'rl_tape'};    # Ref to tape array
    my $tape_grew_l = 0;                 # Flag for tape growth to the left
    my $tape_grew_r = 0;                 # Flag for tape growth to the right
    my $i;

    $ra_c = \$self->{'rl_tape'}[$$ra_p];

    # We may need to call start.
    if ($self->is_not_run()) {
	return $self->start();
    }

    # If $self->{'steps'} is an integer, then we are at the beginning of a
    # full step.
    if ($self->{'steps'} == int($self->{'steps'})) {
	# Check to see if there is an instruction for this state and cell.
	unless (exists($self->{'rh_instructions'}{$$ra_s})
		&& exists($self->{'rh_instructions'}{$$ra_s}{$$ra_c}))
	{
	    $self->{'status'} = $VTM::_HALTED;
	    return 0;
	}
	# Gotta save these values.
	my $s = $$ra_s;    # Current state
	my $c = $$ra_c;    # Current cell

	# Execute the first half of the instruction
	$$ra_s = $self->{'rh_instructions'}{$s}{$c}{'final_state'};
	$$ra_c = $self->{'rh_instructions'}{$s}{$c}{'write'};

	# Save the movement (in case we need it for half-step mode, and the 
	# second call to step() will lose it).
	$self->{'to_move'} = $self->{'rh_instructions'}{$s}{$c}{'movement'};

	# Increment our steps.
	if ($self->{'half_step'}) {
	    $self->{'steps'} += .5;
	    return 1;
	}
    }
    
    # If we're not in half-step mode or we're in the second half-step of a
    # full step.
    if (!$self->{'half_step'} || $self->{'steps'} != int($self->{'steps'})) {
	# Execute the second half of the instruction
	$$ra_p += $self->{'to_move'};
	$self->{'steps'} = int($self->{'steps'} + 1);
    }

    # Are we at the end of the tape?
    if ($$ra_p < 0 || $$ra_p >= @$rl_tape) {
	if ($self->{'infinite_tape'}) {
	    if ($$ra_p < 0) {
		$$ra_p = 0;
		unshift(@$rl_tape, $blank);
		$self->{'offset'}++;
		$tape_grew_l = 1;
	    }
	    else {
		push(@$rl_tape, $blank);
		$tape_grew_r = 1;
	    }
	}
	else {    # $self->{'infinite_tape'} == 0
	    $self->_add_status($VTM::_HALTED);
	    return 1;
	}
    }


    # No point in checking for infinite loops if we've already detected one.
    # (Unless, of course, we got out of the infinite loop.)
    if (!$self->{'infinite_loop_check'}
	|| $self->is_in_infinite_loop()) 
    {
	return 1;
    }
    # Infinite loop check for finite tapes.
    elsif (!$self->{'infinite_tape'}) {
	# Detection of infinite loops via checking for previously encountered
	# "total states."
	$total_state = "$$ra_p $$ra_s " . join("", @$rl_tape);
	if (exists($self->{'rh_encountered'}{$total_state})) {
	    $self->_add_status($VTM::_INFINITE_LOOP);
	}
	else {
	    $self->{'rh_encountered'}{$total_state} = "";
	}
	return 1;
    }
    # Infinite loop check for infinite tapes.
    else {
	# This tests if we are going to be stuck in a single state the moves
	# to the left when it encounters blanks, and all we are going to get 
	# are blanks.
	if ($tape_grew_l 
	    && ($self->{'rh_instructions'}{$$ra_s}{$blank}{'movement'} 
		== $VTM::_LEFT)
	    && $self->{'rh_instructions'}{$$ra_s}{$blank}{'final_state'} 
	        eq $$ra_s)
	{
	    $self->_add_status($VTM::_INFINITE_LOOP);
	    return 1;
	}

	# This tests if we are going to be stuck in a single state the moves
	# to the right when it encounters blanks, and all we are going to get 
	# are blanks.
	if ($tape_grew_r
	    && ($self->{'rh_instructions'}{$$ra_s}{$blank}{'movement'} 
		==  $VTM::_RIGHT)
	    && $self->{'rh_instructions'}{$$ra_s}{$blank}{'final_state'} 
	        eq $$ra_s)
	{
	    $self->_add_status($VTM::_INFINITE_LOOP);
	    return 1;
	}

	$total_state = "$$ra_p $$ra_s ";
	# Find leftmost nonblank cell.
	for ($i = 0; $i < @$rl_tape && $$rl_tape[$i] eq $blank; $i++) 
	{ }
	my $start_slice = $$ra_p < $i ? $$ra_p : $i;

	# Find rightmost nonblank cell.
	for ($i = @$rl_tape - 1; $i > 0 && $$rl_tape[$i] eq $blank; $i--)
	{ }
	my $end_slice = $$ra_p > $i ? $$ra_p : $i;

	$total_state .= join("", @$rl_tape[$start_slice .. $end_slice]);
	if (exists($self->{'rh_encountered'}{$total_state})) {
	    $self->_add_status($VTM::_INFINITE_LOOP);
	}
	else {
	    $self->{'rh_encountered'}{$total_state} = "";
	}
	return 1;
    }
}




=item $M->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.

=item

Calling this method before the machine is run does not make sense.

=cut

# Returns the position of the head.
sub position {
    my $self = shift;
    return $self->{'position'};
}




=item $M->state()

Returns the current internal state of the machine.

=item

Calling this method before the machine is run does not make sense.

=cut

# Returns the current state.
sub state {
    my $self = shift;
    return $self->{'current'};
}




=item $M->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.

=item

Calling this method before the machine is run does not make sense.

=cut

# Returns the current offset.
sub offset {
    my $self = shift;
    return $self->{'offset'};
}




# Private method: _add_status($STATUS)
# Adds $STATUS to the machine's status and returns the new status.
sub _add_status {
    my $self = shift;
    my $add_status = shift;
    $self->{'status'} |= $add_status;
    return $self->{'status'};
}




=item valid_state_name($state_name)

valid_state_name() will return 1 if $state_name is valid, 0 otherwise.
It is a class method.

=cut

# Class method: valid_state_name($state_name)
# Returns 1 if $state_name is valid, 0 otherwise   
sub valid_state_name {
    my $state = shift;
    return 1 if $state =~ /^$VTM::_STATE_REGEX$/;
    return 0;
}




=item valid_cell_value($cell)

Returns 1 if $cell is a valid cell value, 0 otherwise.  It is a class
method.

=cut

# Class method: valid_cell_value($cell_value)
# Returns 1 if $cell_value is valid, 0 otherwise.
sub valid_cell_value {
    my $cell = shift;
    return 1 if $cell =~ /^$VTM::_CELL_REGEX$/;
    return 0;
}




=item valid_tape($tape)

Returns 1 if the $tape is a valid tape, 0 otherwise.  $tape must be a
string.  This is a class method.

=cut

# Class method: valid_tape($tape)
# Returns 1 if $cell_value is valid, 0 otherwise.
sub valid_tape {
    my $tape = shift;
    return 1 if $tape =~ /^$VTM::_CELL_REGEX+$/;
    return 0;
}




1;





=head1 AUTHOR

Paul R. C. Ming E<lt>prcm@nmt.eduE<gt>

E<lt>http://www.nmt.edu/~prcm/turing/E<gt>


=head1 REPORTING BUGS

Please report bugs to the author with the conditions to reproduce the
bug.  The author also appreciates fixes for bugs.


=head1 SEE ALSO

L<vtm(1)>


=head1 COPYRIGHT

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.

=cut
