Java UTM

By Thayne Walker
[download]

[view a drawing of the FSM]

Explanation
Tape format example:
0x-00s01rn000-00s.......-#############1011

-States are encoded by a unique number of 0's. i.e. 00 is state 2 000 is state 3, etc.

-The state encoded to the left of the 'x' is the current state. You must put the start state there before running the program.

-The rules are coded in 5-tuples (separated by a '-' in front and back) on the tape as follows: First the in-state followed by an 's' followed by reading value (0,1,% where % stands for a space) followed by write value, followed by the move value (l,r) followed by an 'n' followed by the next-state or an 'e' which signifies the halt state.
-000s%1rn00-

-There can be any number of spaces (at least one) between the rules and the input, but no spaces anywhere else. For a TM that builds output to the left, leave yourself plenty of room on the left of your input.

-Potential problems: There will only be problems if your TM builds output to the left. There must always be one space at the end of the rules or the UTM will not run right.

-Also, upon finding the halt state, the UTM doesn't reset the start state for you, so if you want to rerun the program, you need to put in the right start state in front of the 'x'.

Algorithm
Precondition: The tape has a list of 5-tuples, start state, and input for the machine. (see documentaion for format explanation)

example input:
0x-00s10rn0-0s01ln00- 01

1. Read input and replace with an '@' symbol.
2. While parsing left until you get to the 'x'; put a marker 'p' on top of the 's' on states that have the right input in the rule.
3. Mark off 0's in the start state and 0's next to the 'p' marker until we have determined that they are the same length.
4. Once we have found the correct rule, mark the 'p' with a 'c'.
5. Read the output symbol, read the moving symbol and remember them (i.e. go to a specific state.)
6. Copy the 0's after the n to the spot in front of the 'x'.
7. Starting at the 'x', parse right and replace p's, c's, and marked off symbols to the original symbol...parse until you get to the '@' symbol.
8. Replace the '@' with the output, and move to the correct direction.
9. Start back at step 1.

Special case: If in step 6, you find the next state tuple has an 'e' instead of a series of zeros, you are at the halt state. At that point, get the output and the direction, then go to the '@' and print the output and halt.

VB.NET UTM

By Randy Whitelaw
[download]

[view a drawing of the FSM]

Explanation
This is a very easy to learn program for making Turing Machines.

-You can add as many rules as you would like. And you can have any state up to 3 characters long.

-Read and Write symbols can be anything that is 1 charcter long.
The defaut symbol is the star (*) and the blank symbol is pound (#).
Any other symbol is treated normally.

-Move can be either R for right or L for left.

-If the reset button is clicked the input is reloaded and the starting position is returned.
This is also the case if you change the input string.

-Saving the machine creates a .txt file which can be viewed with Notepad. This file is in the same format as Ecks Turing Machine (xTuringMachine), xTuringMachine file format 1.0. Remember, xTuringMachine (unless modified) can only handle states 0-24 and the symbols #$01xyz*, so if you use more than that it will not work on the xTuringMachine. However, any file you make using the xTuringMachine will work with mine.

Tape format example:
z0$01100#00$1010.......##########1011

-All machines are assumed to start in state 0.

-States are encoded by a unique number of 0's given by: 0^(n+1) where n is the state. i.e. 000 is state 2 by definition 0^(2+1)=000, state 0 is encoded as just 0 given 0^(0+1)=0.

-A z is placed at the start of the rules to indicate the start of the rule set. All rules are then defined by the current state given by 0's, then the symbol $ as a splitter then the read symbol (#,0,1,x,y), then the write symbol (#,0,1,x,y), then the move symbol (0=Left, 1=Right), and finally the next state given by 0's. Rules are seperated with the symbol #.

-Example: 00$011000 has the rule translation of current state is 1, read 0, write 1, move right, next state is 2.

-There can be any number of spaces (at least one) between the rules and the input. For a TM that builds output to the left, leave yourself plenty of room on the left of your input. By defaul there are 10 blank spaces between rules and input which should be plenty for most applications.

-You can enter your own machine onto the tape in 2 ways:
1. Directy on the tape following the above rules.
2. Create a machine the traditional way with the Turing Machine in normal mode. Save the machine. Switch to universal mode and then load your machine. The tape is automatically genearted with the rules and input all in the correct format,1 and the head position will be in the same position as your normal machine! This will also split your rule set and input by 10 blank spaces automatically.

-Also, upon finding the halt state, the UTM resets the start state for you, so if you want to rerun the program just click the run button again.

-This UTM will take any machine with up to 10 states (0-9) and 5 symbols (#,0,1,x,y).

-Issues: Just one that I'm aware of, the fact that the loaded machine on the tape can be HUGE so if you need to edit the tape the program may be a bit sluggish. To resolve this just switch to normal mode, load your file and make any change there. Save it, then reload it on the UTM.

-Note about UTM's: Be patient. It took just over 30000 rules executions just to do the binary addition of 1 and 1. Not very practical, but fun none-the-less.