JiTA - Java interpreted Turing Automaton

Content of this page

What is a Turing Automaton?
What is JiTA
JiTA Specification
JiTA Example
JiTA Java API Classes
How to use the JiTA API
Related links
Contact

What is a Turing Automaton?

You can find a brief description of turing machines at Stanford Encyclopedia of Philosophy.

A Java simulation of a turing automaton. It's open structure allows it to be programmed by any programming language for turing automatons such as XTApL, just by implementing one Interface of the JiTA API.

JiTA Specification

Machine

A JiTA machine consists of the following data structures:

a non-empty finite set of states
a non-empty set of end-states, which is a partial set of the set of states
one initial-state, which has to be in the set of states and must not be in the set of end-states
a non-empty finite set for the work-alphabet
a non-empty set for the input-alphabet, which is a partial set of the work-alphabet
one blanc-symbol, which has to be a symbol of the work-alphabet and must not be a symbol of the input-alphabet
a non-empty finite input-list, which contains symbols of the input-alphabet or the blanc-symbol
the tape size, which has to be larger or equal to the length of the input-list
a non-empty finite set of transitions

Formaly spoken, a JiTA machine is a 9-tuple (set-of-states, set-of-end-states, initial-state, work-alphabet, input-alphabet, blanc-symbol, input-list, tape-size, transition-set).

States

At any time the automaton will be in one of the states defined in the set of states. At the beginning the automaton will start in the initial state. Reaching an end-state will cause the automaton to stop it's computation.

The set of states must contain at least two states, one initial-state and one end-state.

All states must have different names. Names of states must begin with a letter, which can be followed by digits, letters and the "_"-symbol.

Symbols

All symbols being stored on the tape during computation have to be symbols of the work-alphabet. Symbols being the initial content of the tape must be symbols of the input-alphabet. Exception to this is the blanc-symbol, which has to be a symbol of the work-alphabet and must not be a symbol of the input-alphabet.

Symbols consist only of one character. Possible characters for symbols are: 0-9 a-z A-Z ^ ! " $ % & ( ) ? # ' + - * / ~ _ . : , ; < > |

Tape

The tape consists of a linear list of registers. The length of this list is specified by the tape size. Every register can store exactly one symbol.

Although the size of the tape is not infinite, a JiTA machine is not a linear bounded automaton. Linear bounded automatons have tapes, whose sizes can not be larger than the length of the input-list. Though the size of a JiTA machine tape can be much larger than the length of it's input-list.

Input/Output

The machine starts computation with an input, which is specified by the input-list. Only symbols of the input-alphabet are allowed to be in the input-list. Exception to this is the blanc-symbol, which can also be part of the input-list. The blanc-symbol may be used for separating two or more inputs. The length of the input-list must not be larger than the tape size, but can be less.

If the length of the input-list is less than the tape size, so the symbols of the input-list will be stored in the registers in the center of the tape. The remainder of the registers will be filled with the blanc-symbol.

At the end of the computation the output will be the trimmed tape-content, which means that blanc-symbols in the first and last registers will be cut-off. The output is undefined, if the computation does not terminate or if it terminates with error. Besides the tape content, there will be notice of the end-state the automaton stopped in.

Reader/writer head

The machine has exactly one reader/writer head. At the beginning of the computation, this head is positioned at the first register which does not contain a blanc-symbol. The head can read the symbol stored in the register it is positioned at. It can also write a symbol to the register it is positioned at. Finally the head can move to the next register at left or right. The head can not move out of the bounds of the tape.

Transitions

Transitions are the rules the machine has to follow for making a step. In every situation there is either exactly one transition for this situation, or there is no transition for this situation. If there is no transition fitting in a situation, the computation will stop with an error. If there is a fitting transition, so the computation will continue.

The computation is deterministic, which means that in every situation there is either exactly one possible subsequent step, or there are no more possible steps.

A situation is specified by:

the current state the machine is in
the current symbol read by the reader/writer head

For every situation there can be one transition, which describes what to be done by the machine:

reader/writer head writes a symbol of the work-alphabet (which can be the same as before)
reader/writer head moves either one step left or right, or stays
the machine gets into a new state (which can be the same as before)

Formally spoken a transition is a 5-tuple (old-state, old-symbol, new-state, new-symbol, move-direction), where old-state and new-state are states of the set of states, old-symbol and new-symbol are symbols of the work-alphabet and move-direction is either left, right or none.

If the new state, the machine gets in by this step, is an end-state, so the computation will stop error-free. Otherwise the computation will continue and the machine can try to make further steps.

Configurations

At any time, the situation the machine is in can be described by a configuration. The configuration stores:

the current state the machine is in
the whole content of the tape
the current position of the reader/writer head

The configuration changes after every step (though the new configuration can (but should not) be equivalent to the one before). So the whole computation of the machine can be seen as a sequence of configurations.

JiTA Example

The following JiTA machine adds 1 to a binary number (in this case 00101):

set of states = {Z1, Z2, Z3, Ze}
set of end-states = {Ze}
initial-state = Z1
work-alphabet = {0,1,#}
input-alphabet = {0,1}
blanc-symbol = #
input-list = {0,0,1,0,1}
tape-size = 10
transitions = {(Z1, 0, Z1, 0, right), (Z1, 1, Z1, 1, right), (Z1, #, Z2, #, left ), (Z2, 0, Z3, 1, left ), (Z2, 1, Z2, 0, left ), (Z2, #, Ze, 1, none ), (Z3, 0, Z3, 0, left ), (Z3, 1, Z3, 1, left ), (Z3, #, Z3, #, right)}

Description:

The initial tape content is "###00101##". The machine begins in state 'Z1'. At the beginning the reader/writer head is positioned at the first '0'-symbol. During computation the reader/writer head first will continue going right, until it reaches the blanc-symbol. Reaching this blanc-symbol lets the machine get into state 'Z2'. Now it will continue going left and try to overwrite a '0'-symbol with the '1'-symbol. If this was successful, there is nothing more to do for the machine (it will get into state 'Z3'). If it was not possible (because of there was a '1'-symbol), the machine will overwrite this with the '0'-symbol. The machine will stay in state 'Z2' then, because he was not yet successfull with overwriting a '0'-symbol. This will repeat, until either it is succesfull or it reaches a blanc-symbol while being in state 'Z2'. In this case, it will overwrite the blanc-symbol with the '1'-symbol an get into the end-state 'Ze'. State 'Z3' means, that there is nothing more to do for the machine. It will only clean-up and try to position the reader/writer head on the first non blanc-symbol. At the end, the machine will stop with head on the first '0'-symbol and in state 'Ze'. The binary number will been incremented by one.