Repository files navigation

Anaccept state seeking multitape non deterministic Turing machine simulator allows you to write and execute any Turing machine program with respect toSyntax and with no constraints on the amount of tapes used. In non deterministic cases it usesBreadth-first search to find a path to a halting state, preferably a halt-accept state.

To obtain a copy of the simulator just download the.jar file or compile the project yourself.

• Java 8

To open the simulator:

java -jar "path to .jar"

Syntax inspired byAnthony Morphett.

Any program must follow the structure:

<current state> <character read> <character written> <direction to move> <state to transition into>

Use_ to represent spaces, and* instead of a character read to mean any character, or instead of a character written/direction to mean no change. Refer toExamples folder to clarify.

This simulator needs a program and a certain amount of tapes. The number of tapes depends on the program.When opened the simulator shows a GUI where you will be working.

1. Transitions: the highlighted symbol indicates the head of a tape;

2. Program;

3. Controls:

   • Steps: how many transitions have been executed until current moment;
   • Run: executes the program;
   • Run at full speed: runs as fast as your computer allows;
   • Step: executes one transition;
   • Pause/Resume: pauses/resumes the execution;
   • Set: initiates the tapes and machine;
   • Copy output: copies the text of the output in the Tapes section.

4. Tapes: put one in each line;

5. Pre-execution controls:

   • Decision Sequence: shows the decisions made my machine until current moment; is used in non-deterministic cases. Will automatically fill itself when a transition is executed. Explanation on how to use it is inA Closer Look At Decision Sequence;
   • Clear: clearsDecision Sequence;
   • Pick every step: in non deterministic cases the machine will offer you to pick any possible transition you like;
   • Open: opens a program from your computer;
   • Save: saves the program written inProgram area to your computer.

6. Syntax: syntax to follow on creation of a program;

7. Log: illustrates all executed transitions until current moment.

1. Load one of the programs on your computer or write your own in theProgram area.
2. Enter your tapes in the area under the Controls. They will be written in theTapes area and the heads will be highlighted. Enter the sequence in theDecision Sequence field if needed. ClickSet to initialise the machine.
3. Click onRun to start the Turing machine and run it until it halts (if ever). Click onPause/Resume to interrupt the Turing machine while it is running. Alternatively, clickStep to run a single step of the Turing machine.
4. ClickSet to restore the Turing machine to its initial state so it can be run again.

Assuming that you know what anon deterministic Turing machine is and have read aboutBreadth-first search, clarification on whatDecision Sequence is and how to use it follows:

• When the Turing machine halts the decision sequence's content will be a string of numbers which explains the path in a tree from the initiation to the halting state;
• If not yet in halting state, the decision sequence will keep updating showing the path followed until current moment;

It is possible to transform a non deterministic problem into a deterministic one using the decision sequence.Before initiating the machine you should type in the path you want the machine to take. It will follow it strictly and will perform every transition mentioned (if such exists).

It ispossible to add values to the decision sequence in following cases:

1. Before initiating the tapes and the machine.
2. Every time machine stops executing previous given sequence.

It isnot possible to add values to the decision sequence in following cases:

1. An initial sequence wasn't given.
2. An initial sequence was given, but the machine didn't finish its execution yet.
3. An initial sequence was given, the machine finished executing it and stopped not reaching any halt state and you didn't add any values before running again.

For the sake of a simple example let's use a not well formed non deterministic program and a single tape011 with its head on0.Program:

0 0 a r 0  0 0 b r 1  1 0 a r 1  1 1 a r 1  1 _ _ * halt

As the last transition leads to a halting state the execution finishes and the final decision sequence is2111.

Let's use the example above.

• If you use2111 as initial input in decision sequence, the machine will halt within 4 transitions because this sequence will take it to a halting state.
• If you, for example, use211 as initial input, the machine will stop after those 3 transitions and you can add values to it before running it again.
• If you, for example, use3 as initial input, the machine will abort because there are only 2 possible transitions for state0 and head0.
• If you, for example, use2 as initial input and after machine stops you don't add any values to it and just run, the machine will run normally finishing in 4 transitions and decision sequence2111.