Turing Machine’s, because I’m really that bored…

In the absence of anything to do other than research my 3rd year project, exercise, and void my wallet in the Steam sales, here is the result of 5 hours work. You can see the whole project on GitHub.

The engine runs off an input consisting of 5-tuples. That is, lines that fit the form…

(state_id, expected_val, print_val, move_cmd, next_state)

There is also an optional line (which must be first in the file if it is not to be ignored) which consists of an unbroken string of B’s, 0’s, and 1’s. This line, if found, will set the initial value of the tape.

Here is a simple turing machine which generates an infinite string of 0 space 1 space 0 space 1…. Since this program expects a blank tape one isn’t defined.

One really good thing about this little project is having stumbled upon a great little Java Project calls JArgs, which is a Argument Parser for better dealing with Command Line Arguments. God knows why such a system is not built into the JDK in the first place.

This has allowed me to make a really neat way of running the program. You can define a file via the -f flag or pipe a file in via standard input. Thus both java TuringMachine -f .\resources\Simple.tur -t 100 and java TuringMachine < .\resources\Simple.tur -t 100

The -z flag is quite important as for some turing machines we need to imagine that the default value for an infinitely long tape is a blank cell, and for some that it is a 0. As an example, the Busy Beaver Turing Machine imagines a 0 filled tape.

For turing machines where we know the value of the tape is only relevant during a certain state, such as an adder, we can limit tape printing to that state only using the -p flag.

The -q flag stops all but the final output being displayed. This is good for when you know a program will run for a long time and eventually end. However if you do not know whether the Turing Machine will halt it is inadvisable to use this flag.

Finally the -t flag allows you to slow the execution of the Machine down so it is easier to view. It simply puts a thread sleep in after each instruction of the millisecond length given.

Here is an implementation of a 3-State Busy Beaver. This Machine would need to be run with the -z flag set as it assumes a 0 filled tape. Edit, additionally given that the Busy Beaver outputs to the tape both to the left and right of the start position it may be useful to pad the tape with default value on either side of the head. We can do this with the -d flag.

Finally here is a Binary Adder. It counts upwards indefinitely from the value in the initial tape. For a machine like this we would use the -p flag to denote that we only want to print the tape in state 1.

Tags Turing Machine