[MathJax on]

6 Program

A turing program is the means with which a turing Machine determines which action to perform when in a certain Stateand reading a certain Symbol.

It determines this by looking up the rule that corresponds with the combined state and symbol key.

gap> LoadPackage("turing");;
gap> program := TmProgram(TmState(1));
<program empty>
gap> TmAddRule(program, TmState(1), TmBlank(), TmHalt(1), TmSymbol('I'), TmLeft());
gap> program;
<program with 1 rule>

6.1 Constructor

6.1-1 TmProgram

Returns: a turing program.

This retuns a turing program that can be used in a Machine. The progam will start in state startingState.

6.2 Rules

6.2-1 TmAddRule

Returns: nothing

Adds a rule to the program

The rule to be added tells that a turing Machine that is in state currentState and reads symbol symbolRead from the tape will transition to the state futureState, writes symbol symbolToWrite to the tape and move the tape head to the direction direction.

6.2-2 TmLookup

Returns: a record containing the rule

Looks up a rule from a program, with currentState and symbolRead as key.

The record has keys state, symbol and move. The state key determines the next state of the turing machine, the symbol key determines what symbol to write to the turing machines tape and the move key determines which direction the head moves in.

gap> LoadPackage("turing");;
gap> program := TmProgram(TmState(1));
<program empty>
gap> TmAddRule(program, TmState(1), TmBlank(), TmHalt(1), TmSymbol('I'), TmLeft());
gap> action := TmLookup(program, TmState(1), TmBlank());;
gap> action.state;
h1
gap> action.symbol;
<symbol 'I'>
gap> action.move;
<direction left>

6.3 Start State

6.3-1 TmStartState

Returns: the start state

returns the start state of this program.

gap> LoadPackage("turing");;
gap> program := TmProgram(TmState(1));;
gap> TmStartState(program);
q1

generated by GAPDoc2HTML