Examples of Turing Machines: Loops, Halts, and Rewriting

By

Home / Examples of Turing Machines: Loops, Halts, and Rewriting

Turing Machine, image by Ludger Humbert

Alan Turing devised the theoretical Turing Machine: Image by Ludger Humbert

A Turing machine, or TM, is a theoretical model devised by Alan Turing to explore the limits of rule-based math. The model has a finite number of rules, states and symbols, and an infinite tape with cells, each of which can contain a single symbol. The TM can either read the current cell, rewrite it, move to the next cell on the left or right, or transition to a new state.

The description of any Turing Machine consists of a list or table of 4-tuples, including the state number, one input symbol that it can read and accept while in this state, the next state to which it should transition, and the action it should take: either the symbol it must rewrite into the current cell, or the direction in which to move.

The following are examples of simple Turing machines:

A Turing Machine that Either Reads to the End, or Loops Forever

This Turing machine just reads and goes in the indicated direction until it encounters an ‘H’ to direct it to halt. It has two states and four instructions. The tape has three values: {‘L’, ‘R’ and ‘H’} which stand for left, right, and halt.

  • *State #0 is the halt state
  • *If State #1 reads ‘L’, then stay in state #1 and go left one cell.
  • *If State #1 reads ‘R’, then stay in state #1 and go right one cell.
  • *If State #1 reads ‘H’, then change to state #0 and remain at this cell.

Of course, the above machine could also enter an infinite loop and not halt at all. Encountering “…RRRLLL…” would force the machine to shift between the middle “RL” positions forever.

Since the tape is infinitely long, the machine would also fail to halt if it encounters an infinite string of either ‘L’s or ‘R’s.

Any Turing machine, such as the one above, that cannot rewrite cells is less powerful than the classic version, and is called a “finite state machine.” A finite state machine can recognize a short repeated pattern if it was programmed with enough unique states. However, a full Turing machine could recognize the pattern in a string of any finite length consisting of any arbitrary number of ‘1’s followed by exactly the same number of ‘2’s.

Leave a Comment