Goto Chapter: Top 1 2 3 4 5 6 7 Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

1 Introduction
 1.1 What are Turing machines
 1.2 Example
 1.3 Definitions

  1.3-1 IsTuringDirection
  1.3-2 IsTuringLeft
  1.3-3 IsTuringRight
  1.3-4 IsTuringMachine
  1.3-5 IsTuringProgram
  1.3-6 IsTuringState
  1.3-7 IsTuringHaltState
  1.3-8 IsTuringSymbol
  1.3-9 IsTuringBlank
  1.3-10 IsTuringTape
  1.3-11 IsTuringObject

1 Introduction

turing is a GAP package that simulates Turing machines.

1.1 What are Turing machines

A Turing machine is an abstract computing device dreamed up by Alan Turing

It consist of a Tape, a Program and a current State.

The current State and the Symbol read from the Tape are used to 6.2-1 an action to perform.

1.2 Example

Below there is a session that demonstrated the Turing machine that increments a unary number.

gap> LoadPackage("turing");;
gap> program := TmProgram(TmState(1));
<program empty>
gap> TmAddRule(program, TmState(1), TmSymbol('I'), TmState(1), TmSymbol('I'), TmRight());
gap> TmAddRule(program, TmState(1), TmBlank()    , TmState(2), TmSymbol('I'), TmLeft());
gap> TmAddRule(program, TmState(2), TmSymbol('I'), TmState(2), TmSymbol('I'), TmLeft());
gap> TmAddRule(program, TmState(2), TmBlank()    , TmHalt(1) , TmBlank()    , TmRight());
gap> tape := TmTape();
<tape empty>
gap> TmTapeWrite(tape, TmSymbol('I'));
gap> machine := TmMachine(tape, program);
<machine q1 <tape |__[I]__|>>
gap> TmRun(machine);
gap> machine;
<machine h1 <tape |__[I]I_|>>

1.3 Definitions

1.3-1 IsTuringDirection
‣ IsTuringDirection( arg )( category )

Returns: true or false

the category of all direcitons.

1.3-2 IsTuringLeft
‣ IsTuringLeft( arg )( category )

Returns: true or false

the category of the direction left.

1.3-3 IsTuringRight
‣ IsTuringRight( arg )( category )

Returns: true or false

the category of the direction right.

1.3-4 IsTuringMachine
‣ IsTuringMachine( arg )( category )

Returns: true or false

the category of turing machines.

1.3-5 IsTuringProgram
‣ IsTuringProgram( arg )( category )

Returns: true or false

Determines if an object is a turing program.

1.3-6 IsTuringState
‣ IsTuringState( arg )( category )

Returns: true or false

determines if arg is a turing state.

1.3-7 IsTuringHaltState
‣ IsTuringHaltState( arg )( category )

Returns: true or false

determines if arg is a turing halting state.

1.3-8 IsTuringSymbol
‣ IsTuringSymbol( arg )( category )

Returns: true or false

the category of all turing symbols.

1.3-9 IsTuringBlank
‣ IsTuringBlank( arg )( category )

Returns: true or false

the category of all turing blank symbols.

1.3-10 IsTuringTape
‣ IsTuringTape( arg )( category )

Returns: true or false

Determines if arg is a turing tape.

The next definitions are global.

1.3-11 IsTuringObject
‣ IsTuringObject( arg )( category )

Returns: true or false

Determines if arg is a turing object.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 Ind

generated by GAPDoc2HTML