**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.** **