Turingol: A Language for Turing Machines

Discussions of Turing computability often use a rather crude high level language to specify the actions of complex Turing Machines. This paper is a report on the design of a Turing Machine language and the implementation of a compiler for this language. The classical Turing Machine is a device equipped with a two way infinite tape divided into squares. The machine can read or write characters from a finite alphabet on the tape in the square which is currently being scanned and it can move the scanning position to the left or right. The machine has a finite set of internal states. At any time, the action of the machine is determined by the character on the square under the read/write head and by the current state of the machine