Problem Solving: Turing Machines

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 1 - ⇑ Theory of computation ⇑

← Halting problem Turing Machine


From the Specification : Turing Machine and the Universal Machine.

The abstract model of the Turing Machine and the Universal Machine..

Recap[edit | edit source]

Before attempting to study Turing Machines you should ensure you are familiar with Finite State machines from the AS Computing specification and the few additional FSM concepts added to the A2 course.

Definition[edit | edit source]

Turing machines provide a general or formal model of computation and can be used to determine whether or not a task is computable.
OR
A formal model of computation that consists of a finite state machine (FSM) that controls one or more tapes, where at least one tape is of unbounded length (ie infinitely long).

Universal Turing Machine[edit | edit source]

A universal Turing machine (UTM) is a Turing machine that can execute other Turing machines by simulating the behaviour of any Turing machine. If a sequence is computable then a UTM will be able to execute it. A UTM behaves as an interpreter which is just what a PC does when it runs a Java applet or Flash script.

Rather than each individual process within a single machine, the UTM takes two inputs:

  • A description of all the individual Turing machines required to perform the calculations
  • All the inputs required for the calculations


Principle of Universality: A universal machine is a machine capable of simulating any other machine.

Examples of mechanical Turing Machines[edit | edit source]

Simulations[edit | edit source]

  • Turing Kara has some excellent instructions to help you get to grips with the basic operations of a turing machine

Example Questions[edit | edit source]

Exercise: Turing Machines

What is a Turing machine?

Answer:


A Finite State Machine that operates one or more tapes where at least one tape is infinitely long

Revision[edit | edit source]