Introduction to Turing Machines

This is a lesson in the course, Introduction to Computer Science, which is a part of The School of Computer Science.

Instructions for this lesson: Read the text and try to understand it. If something is not clear, follow the links for an explanation.

Objective

The concept of Turing machines is one of the founding principles of modern computing. Although somewhat complicated for first-time learners, Turing machines (along with several other models) are vital for representing the underlying logic behind all computers. This lesson will give a brief overview of the subject.

Be able to answer these questions:

What is a Turing machine?
What types of Turing machines are there?

Required Work

Google made a small online game that illustrates Turing Machines in a fun and interesting way. Try out this Google Doodle and see if you can solve some of the puzzles. Pay attention to the interface of the game; it will help your understanding of the contents below.

Turing machines are theoretical constructs, first described and then expanded upon by their namesake, British mathematician Alan Turing. It is believed that anything that can be computed can be computed by a Turing machine. These machines can be represented through diagrams and formulas but due to physical limitations can never be built. Various forms of Turing machines have been adapted to analyze complexity among other things. Turing machines are types of finite state machines.

Determinism and Non-Determinism are vital concepts for understanding the functioning of Turing machines. Therefore, this page will provide a brief overview of these subjects.

What is a Turing Machine?

An artist's depiction of a Turing machine.

A Turing machine is an abstract concept used to describe a type of machine that, given an indefinite amount of space and time, can be adapted to calculate anything, such as the digits of π or even a whole universe.

A simple Turing machine consists of a tape of a theoretically infinite size consisting of cells, or sections on the tape. Each cell holds on it a symbol. The singular active cell in a Turing machine is referred to as the head. The head traverses across the cells in the tape, and can be in a certain set of possible states, which represent instructions that the machine will follow given on the contents of the head. Every Turing machine has a finite number of states.

There are a finite number of symbols that the head can read or write. Any cells to which the head did not write previously are considered to hold the blank symbol, often designated as $b$ . Because the tape is of a theoretically infinite size, at any point during the execution of the Turing machine, there is an infinite amount of blank symbols on the tape.

The initial state, designated by $q_{0}$ , is the state in which the Turing machine is at the beginning of execution.

What Different Types of Turing Machines are There?

There are many different types of Turing machines that are often used to describe certain kinds of execution. The two that are most often used are deterministic and non-deterministic Turing machines.

What is a Deterministic Turing Machine?

Automata are often used to represent Turing machines. This is a deterministic Turing machine that calculates the two's complement of some binary input.

A deterministic Turing machine is one that uses the concept of determinism to calculate a solution to a problem.

Determinism is the concept of being only in one state at a given time and determining what the next state will be from that state. In simpler terms, determinism would be being in state $q_{0}$ , and only holding that state until moving on to the next state, $q_{1}$ . In determinism, we would be able to predict without any doubt that the head would move from state $q_{0}$ to state $q_{1}$ . A Turing machine does not have to halt, or stop execution, in order for it to be considered deterministic.

What is a Non-deterministic Turing Machine?

A non-deterministic Turing machine is one that uses the concept of non-determinism to calculate a solution to a problem.

A non-deterministic Turing Machine differs from a deterministic Turing Machine in the sense that a non-deterministic Turing Machine can have several possible states to which it can transition from any given state, $q_{i}$ . One way to think of it would be to think that, given the possibility of choosing from several subsequent states, the non-deterministic Turing machine guesses the next iteration that will bring it to a ‘yes’ answer. Put a different way, the non-deterministic Turing machine branches out into holding many states at the same time in an until one of the many paths leads it to a ‘yes’ answer. In perspective, a non-deterministic Turing machine may, for instance, be in state $q_{0}$ and then hold both state $q_{1_{1}}$ as one of the branches and state $q_{1_{2}}$ as another branch.

Quiz

Try this quiz on the Turing machine.

Introduction to Computer Science

Basics of computer architecture →