Syntax

Consider the following example, the definition for a Turing machine that accepts all binary strings that are palindromic:

# This is a definition of a Turing Machine that accepts binary strings that are palindromes
' '
A*
    'X' 'X' < A
    'Y' 'Y' < A
    '0' 'X' > B
    '1' 'Y' > F
    ' ' ' ' > G
B                   # Starting with 0
    '0' '0' > B
    '1' '1' > B
    ' ' ' ' < C
    'X' 'X' < C
    'Y' 'Y' < C
F                   # Starting with 1
    '0' '0' > F
    '1' '1' > F
    ' ' ' ' < E
    'X' 'X' < E
    'Y' 'Y' < E
C
    '0' 'X' < D
    'X' 'X' < D
E
    '1' 'Y' < D
    'Y' 'Y' < D
D
    '0' '0' < D
    '1' '1' < D
    ' ' ' ' > A
    'X' 'X' > A
    'Y' 'Y' > A
G.
    'X' '0' > G
    'Y' '1' > G

Comments

Alan supports single line comments with #.

# This is a definition of a Turing Machine that accepts binary strings that are palindromes

Symbol

The first parsed line of a definition must be the blank character surrounded by single quotes.

' '

The program throws an error if multiple symbols are set as the blank symbol.

The program infers the rest of the symbols from the transitions.

State

A state is a valid identifier.

• States that are followed by a * are set as the start state.

  A*
  

  Only one state can be set as the start state.

• States that are followed by a . are set as an end state.

  G.
  

  Note that the state S can be set as both the start state and an end state in the following ways:

  • S.*
  • S*.

Transition

Syntactically, transitions immediately follow a state.

A*
    'X' 'X' < A
    'Y' 'Y' < A
    '0' 'X' > B
    '1' 'Y' > F
    ' ' ' ' > G

They are defined as : 'currentSymbol' 'nextSymbol' direction 'nextState'.

Note that the directions < & > correspond to left & right moves along the tape.

Note that the tape head points to currentSymbol which is changed to nextSymbol prior to moving.