PHP script to simulate a turing machine, which calculates an unary multiplication.

tm-multiply.php

<?php
/**
 * Turing Machine Simulator in PHP
 * Purposely built for unary multiplication with a two tape TM.
 * 
 * input format: 001000
 * the '1' seperates the first from the second integer
 *
 * result of the multiplication will be on the second tape.
 *
 * @author Simon Aebersold
 * @version 1.0
 */
error_reporting(E_ALL);
ini_set("display_startup_errors",1);
ini_set("display_errors",1);

class Tape {
	public $content = "";
	public $headPosition = 500;

	function __construct()
	{
		$this->content = str_pad("", 1000, "_");
	}

	// reads char where the head is
	public function getChar()
	{
		return $this->content[$this->headPosition];
	}

	// read on position X, although head is not there
	// only use for output!
	public function getCharForX($position)
	{
		return $this->content[$position];
	}

	// write char
	public function writeChar($char)
	{
		$this->content[$this->headPosition] = $char;
	}

	// move the head
	public function moveHead($direction)
	{
		switch ($direction) {
			case 'L':
				$this->headPosition--;
				break;
			case 'R':
				$this->headPosition++;
				break;
			case 'S':
				// don't move
				break;
		}
	}

	// move head left until it is on the first character
	public function moveHeadInitial()
	{
		while($this->getChar() != "_")
		{
			$this->moveHead("L");
		}
		$this->moveHead("R");
	}

	// output
	public function output()
	{
		// 15 chars left and right of the head
		for($i = $this->headPosition-15; $i <= $this->headPosition+15; $i++)
		{
			if($i == $this->headPosition)
			{
				echo "[".$this->getCharForX($i)."]";
			}
			else
			{
				echo $this->getCharForX($i);
			}
		}
		echo "\n";
	}
}

/* START OF SCRIPT */
$tape1 = new Tape;
$tape2 = new Tape;
$finalState = "q4";
$state = "q0";
$trash = false;
$counter = 0;

/* DEFINE RULESET */
$rules = array(
			"q0" => array(
				"0,_,R,_,_,S,q1",
				"1,_,R,_,_,S,q4",
			),
			"q1" => array(
				"0,0,R,_,_,S,q1",
				"1,1,R,_,_,S,q2"
			),
			"q2" => array(
				"0,0,R,_,0,R,q2",
				"_,_,L,_,_,S,q3",
			),
			"q3" => array(
				"0,0,L,_,_,S,q3",
				"1,1,L,_,_,S,q3",
				"_,_,R,_,_,S,q0",
			),
			"q4" => array(
			),									
);

// take input
$input = $argv[1];
if(!preg_match('~^[01]+$~', $input) || substr_count($input, "1") != 1)
	exit("Input not valid!");

// write input to the first tape
foreach(str_split($input) as $char)
{
	$tape1->moveHead("R");
	$tape1->writeChar($char);
}

// move head of tape1 to initial position
$tape1->moveHeadInitial();


// decide mode
echo "\nTuring-Machine\n";
echo "Would you like to use the step-mode, or run-mode?\n";
echo "\ntype 'run' or 'step': ";

// grab user input
$handle = fopen ("php://stdin","r");
$mode = fgets($handle);

switch (trim($mode)) {
	case 'run':
		$steps = false;
		echo "\nrun-mode chosen.";
		break;
	case 'step':
		$steps = true;
		echo "\nstep-mode chosen.";
		break;
	default:
		$steps = true;
		break;
}

// Output
echo "\n-------------------------------------------------\n";

echo "TM initialized. Current position:\n\n";
echo "tape 1:\t\t";
$tape1->output();

echo "tape 2:\t\t";
$tape2->output();

echo "\n-------------------------------------------------\n\n";

// while machine runs
while($state != $finalState && !$trash)
{
	$char = $tape1->getChar();
	$trash = true;
	$counter++;

	if($steps) echo "Step #".$counter.", State: ".$state."\n";

	foreach($rules[$state] as $rule)
	{
		$rulearr = explode(",", $rule);
		
		// if this rules applies
		if($char == $rulearr[0])
		{
			if($steps) echo "using rule: ".
					$rulearr[0]."/".$rulearr[1].
					", ".$rulearr[2].
					" | ".
					$rulearr[3]."/".$rulearr[4].
					", ".$rulearr[5].
					" | >".$rulearr[6].
				 "\n";

			$trash = false;

			// write to tape1
			$tape1->writeChar($rulearr[1]);
			$tape1->moveHead($rulearr[2]);

			// write to tape2
			$tape2->writeChar($rulearr[4]);
			$tape2->moveHead($rulearr[5]);

			// set new state
			$state = $rulearr[6];

			break;
		}
	} 

	if($steps) 
	{
		echo "tape 1:\t\t";
		$tape1->output();

		echo "tape 2:\t\t";
		$tape2->output();

		echo "\n";

		// user must press enter
		fgets(STDIN);
	}
}

// Output
echo "\n-------------------------------------------------\n";

echo "Machine halted. State: ".$state.". Total Steps: ".$counter."\n\n";
echo "tape 1:\t\t";
$tape1->output();

echo "tape 2:\t\t";
$tape2->output();

echo "\n-------------------------------------------------\n\n";

?>