Universal Turing Machine in Forth

by Theresa Fröschl and Maximilian Irro

This is a project for the course Stackbasierte Sprachen (2014W) (german for "stack-based languages") at TU Wien. The repository is available on GitHub.

We amined to write a Universal Turing Machine using the language Forth. We developed our program for the Gforth interpreter. If used with other Forth interpreters there might be issues (we never tested).

Name explanation

We call our program Universal Forth Machine (UFM), a wordplay between "Universal Turing Machine", being written in Forth, and Forth being a stack machine.

Usage

ufm.forth /path/to/machine /path/to/tape

Machine specification format

We provide some example machines in machines/ and tapes to test them in tapes/. The basic file format looks like this:

start-state
state-term1 label
state1
sym-read sym-write next-state tape-ptr-move
sym-read sym-write next-state tape ptr-move
state-term2 otherlabel
state-term3 yetanotherlabel
state2
sym-read sym-write next-state tape-ptr-move
sym-read sym-write next-state tape ptr-move

The first line has to be the start-state. All following lines are state descriptions. A term-state (terminal state) is followbed by a label which is a string that will be the output of UFM if the machine terminates in this state. A line containing just a state token starts the definition of a regular state. All following lines until a new state or state-term line are the edge dedinitions for this state. An edge line has to consist of:

1. sym-read: the symbol read on the tape. If the machine is in the currently defined state, and this symbol is read, the machine will execute the following actions of this line. Think of it as the edge label when picturing the turing machine as a graph.
2. sym-write: the symbol to write onto the current tape position.
3. next-state: the next state the turing (state-)machine goes to.
4. tape-ptr-move: the direction the tape pointer (tape-ptr) moves. It can go one step to the left (-1) or right (1), or just stay (0) at its current position.

Note that all tokens except the label for terminal states support literals only! They will all be converted into numbers. So no strings allowed here.

Special stack feature

The state transition of the machine is done in a loop calling the transition word. This is a word that will be dynamically compiled at runtime just before it's first execution. Therefore the code of transition is not hardcoded in the program file, but will be generated by a special compilation word [compile-transition] which is compile-only and immediate. It will compile Forth code into transition based on the input machine specification file. Have a look at the colon definition of transition in the source code, and at runtime using see transition

Structure of transition word

The code structure of transition (which will be compiled depending on the machine-file) looks like this for the machines/increment.machine:

: transition ( cur-state sym-read -- next-state flag )
	over 1 =
	IF     cr 4546001056 16 type 4545995737 9 type cr 2drop 0 EXIT
	THEN
	over 0 =
	IF     dup 1 =
		IF     2drop 1 tape-write 0 tape-ptr-move-right -1 EXIT
		THEN
		dup 0 =
		IF     2drop 1 tape-write 1 tape-ptr-move-stay -1 EXIT
		THEN
	THEN ; ok

The over <some-literal> = if sequences will check for the state the machine is currently occupying. The dup <some-literal> = if parts then check the current symbol on the tape. With this mechanism it is decided which action the machine will perform next.

Resources

Program:

• ufm.forth

Machines:

• increment.machine -- increment the amount of 1-symbols on the tape by one (at the right edge).
• multi3.machine -- check if tape content holds a multiple of 3 1-symbols.
• palindrom.machine -- check if tape content is a palindrom. Border markers are 11 (left) and 33 (right).

Tapes:

• increment.tape
• multi3-yes.tape -- multi3.machine should recognize a multiple of 3 1-symbols.
• multi3-no.tape -- multi3.machine should not recognize a multiple of 3 1-symbols
• palindrom-ok.tape -- palindrom.machine should accept a palindrom
• palindrom-nok.tape -- palindrom.machine should not accept a palindrom