#!/usr/bin/perl --
# Universal Turing machine implementation, released under ISC/BSD license:
# Copyright (c) 2009, Alex Stangl <alex@stangl.us>
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
#
# This implementation, initially written on 01/22/2009 is an attempt to
# write a shortest possible implementation of a Universal Turing machine,
# which takes 5n + 1 command-line integer arguments, first of which is
# maximum number of steps to run, and then each 5-tuple consists of
# (input state, input symbol, output state, output symbol, direction)
# see http://www.mathrix.org/experimentalAIT/TuringMachine.html for full
# rules and other details. Compromises were made with coding style and
# error handling, to shorten the source code.

#@A is shorthand alias for ARGV, $i is index of current tuple in cmdline args, $s is current state, $c current symbol,
# $d direction, @l is tape to the left of the head and @r is tape to right of the head, both indexed from left to right
@A=@ARGV;
$i=$s=1;

# run machine
$i = $s-$A[$i] | $c-$A[1+$i]
    # non-matching tuple; advance to next cmdline tuple
    ? $i + 5
    # matching tuple; load state, symbol, and direction from rule, update tape, increment step count, and reset tuple index
    : (($s,$c,$d)=@A[2+$i..4+$i], $c = $d < 0 ? (unshift(@r,$c), pop@l): $d > 0 ? (push (@l, $c),shift @r):$c, $step++, 1)
while ($s && $step < $A[0]);

# output 2 if machine has not halted or contents of tape if it has. In either case, follow on next line with # of steps executed.
$"="";
print $s ? "2" : "@l$c@r", "\n$step\n"