TPL - The T Programming Language

__________________________________________________

Review: The Formal Definition of a Turing Machine:

A (PDA) is a 7-tuple

, where

• is a finite set called the states,

• is a finite set called the input alphabet,

• is a finite set called the tape alphabet, where and .

• is the start state, is the accept state,

  and is the reject state.

• is the transition function.

__________________________________________________

The TPL Grammar is:

0 1 .... 8 9

L R

Q

Qaccept Qreject

//read the letter Q followed by one or more digits or "accept", or "reject."

//We will use the "" to denote a "transition state."

S

//We will use the "" to denote an "input symbol."

X

//We will use the "" to denote a "tape symbol".

(,,,,)

//We will use the "" to denote a "transition".

A TPL Program consists of:

1. A finite set of transition states, including Q0 ,Qaccept, and Qreject .

2. A finite set of tape symbols , including

3. The directions L and R.

4. A finite set of transitions statisfying the Turing Machine transition function condition with respect to 1. and 2. .

____________________________________________________________________--

Note That:

• All TPL Programs can be written using the 21 symbols

  0 1 .... 8 9Q Qaccept Qreject S X ( ,) L R

• The Validity of a TPL Program can be decided.

  1. States, tape_symbols, and transitions can be checked by a DFA.

  2. That the transitions provide a transition function can be checked by a search on all pairs.

One Can :

• One can model any Turing Machine with a TPL Program.

• Implement a TPL interpreter, hence emulate any Turing Machine, in any general purpose programming language.

• Construct a "Universal Turing Machine" that is a TPL interpreter. Again, note that the UTM only has to recognize 21 input symbols.