Turing Machines

Turing Machines

A Turing machine is a computational model where symbols on an infinite tape can be changed based on a table of rules.

This activity allows a simple Turing machine to be defined using a series of rules and then run shoing how the symbols on the tape are updated step by step

The Tape

The tape is made up of a number of squares each containing a symbol

  • Theoretically, the tape is infinite
  • In this activity the tape is limited to maximum of 16 squares
  • The first and last squares always take the blank symbol

Tape Head

The tape head is positioned over one square at a time

  • A tape head starting point must be specified
  • The rules specify whether the tape moves left or right after updating the symbol at the current position
  • If the tape head goes off the tape, the machine stops

States

At each stage the Turing machine is in one of a number of predefined states

  • There much always be a halting state that determines when the machine stops running
  • Up to ten other states can be defined in this activity
  • The activity allows the name of each state to be defined
  • Rule definitions require the current state
  • The rule may change the current state

Symbols

Each square on the tape either contains a symbol from a predefined alphabet is blank

  • In this activity, an alphabet of up to six symbols can be defined
  • The ▢ character is used to represent a blank square
  • Rule definitions require the current symbol
  • The rule may change the symbols contained in the current square; the one over which the tape head is positioned

Rules

A rules is defined for each state (excluding the halting state) and each symbols

  • Each rule determines
    • Which symbols to place in the current square
    • The new state
    • Whether the tape head should move to the left or the right
  • In this activity, rules are displayed using the δ symbol
  • The rule input requires the current state and input character
  • The rule output required the new symbol, state and subsequent direction of movement
Example

δ(S1, 0) = (S2, 1, L)

In state 1, if the character in the current square is 0, then it is replaced by 1, the state changes to state 2 and the tape head moves left

Setup

Enter the number of symbols:

(Excludes the space value ▢)

Enter the number of states:

(Excludes the halting state)

Enter the tape length:

Examples

There are a number of example programs which can be loaded in to illustrate how Turing machines can be written and run using this application.

Add One

Adds 1 to the specified number.

  • The machine is initially in state R
  • The tape head moves right until it find a ▢
  • It then enters state F and the tape head moves left
  • The symbol 1 is changed to 0 and the tape head moves left
  • The symbol 0 is changed to 1. The halting state is entered and the machine stops

Odd Parity

Adds 0 or 1 to the number to made the parity odd

  • The machine is initially in state L
  • The tape head moves left until it find a ▢
  • It then enters state E and the tape head moves right
  • If the current symbol is 0, the tape head moves right
  • If the current symbol is 1, the state changes between O and E and the tape head moves right
  • When the symbol ▢ is found, it is replaced with 0 if the state is O and 1 if the state is E. The halting state is entered and the machine stops

One's Complement'

Finds the one's complement of a number by switching 0 to 1 and 1 to 0.

  • The machine is initially in state R
  • The tape head moves right until it find a ▢
  • It then enters state F and the tape head moves left
  • The symbol 1 is changed to 0 and the tape head moves left
  • The symbol 0 is changed to 1 and the tape head moves left
  • When the symbol ▢ is found the halting state is entered and the machine stops

Two's Complement

Finds the two's complement of a number; the negative respresentation

  • The machine is initially in state R
  • The tape head moves right until it find a ▢
  • It then enters state K and the tape head moves left
  • If the current symbol is 0, the tape head moves left
  • If the current symbol is 1, the state is changed to F and the tape head moves left
  • The symbol 1 is changed to 0 and the tape head moves left
  • The symbol 0 is changed to 1 and the tape head moves left
  • When the symbol ▢ is found the halting state is entered and the machine stops

Shift Letters Right

Moves a string made up of the symbols X, Y and Z, one place to the right

  • The machine is initially in state L
  • The tape head moves left until it find a ▢
  • It then enters state B and the tape head moves right
  • In state B symbols X, Y and Z are changed to ▢, the state is changed to the one matching the symbol and the tape head moves right
  • In states X, Y and Z, the symbols X, Y and Z are changed to match the state value, the state is changed to the one matching the symbol and the tape head moves right
  • In states X, Y and Z, the symbol ▢ is changed to match the state value, the halting state is entered and the machine stops

Copy

Makes a copy of a string made up of the symbols X, Y and Z

Reflect

Makes a reflection of a string made up of the symbols 0 and 1