PS Computational Complexity

Problem 2.8.8 (TGZ)
Tex-file and PS-file for problem 2.8.8 'Computational Complexity, Christos H. Papadimitriou, 1994, Addison-Wesley'.

Shell-Script (TEX2PS)
Shell-Script (TEX2GR)
Shell-Script (GR2TEX)
Use 'chmod u+x tex2ps' to set the execution permission for this file.
The current directory will be the working directory for this shell-script!

example 'tex2ps problem2.8.8.'

This will remove all working files of previous runs. Then 'latex' will be called twice (to get cross-references right). Dvips will create a Post-Script-File from the dvi-output of latex. And finally 'ghostview' will show you the result.

Turing Machine Simulator (DOS)
One string turing machine simulator (with source code).

'turing mode transition-function-file input'
mode can be one of the following [ STEP | RUN[n] | FILE | END ]

STEP	to run the turing machine step-by-step.
RUN[n]	to let the turing machine run automaticly with a delay of n ms between each step.
FILE	to redirect the output to an file.
END	will show only the number of steps the turing machine needed to reach the halting state and the end-string.

The format of the transition-function-file is very simply.
as rs ns ws m
as rs ns...

as	the actual state, a string (max. length 15 characters).
rs	the read symbol, one character.
ns	the next state, a string (max. length 15 characters).
ws	the written symbol, one charater.
m	the movement, '<', '-' or '>'.

the input could be a filename or a string.

Special symbols, ...:

'^'	triangle (it is not necessary to begin the input-string with a triangle)
'_'	space (it is not necessary to end the input-string with a space)
's'	starting state
'h'	halting state

Last modified: Mon Mar 9 09:41:34 MET 1998 by Claus REICHEL