Introduction to Turing Machines

From Wikiversity
Jump to navigation Jump to search

This is a lesson in 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 explanation.

Objective[edit]

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[edit]

Google made a small online game which 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 what the interface of the game is, it will help your understanding of the contents below.

Contents[edit]

A statue of Alan Turing, the groundbreaking computer scientist who first conceived of the Turing machine.

Turing machines are theoretical constructs, first described and then expanded upon by their namesake Alan Turing. 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 analyse 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. For a more thorough understanding, students should consult information about Automata Theory.

What is a Turing Machine?[edit]

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, which is written to it by the head, and which modified the current state of the machine.

There are a finite number of symbols that the head can read or write. Any cells to which the head did not write previously is considered to hold the blank symbol, often designated as . This means that 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 , is the state in which the Turing machine is in at the beginning of execution.

What Different Types of Turing Machines are There?[edit]

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?[edit]

Automata are often used to represent Turing machines. This is a deterministic Turing machine which 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 , and only holding that state until moving onto the next state, . In determinism we would be able to predict without any doubt that the head would move from state to state . A Turing machine does not have to even halt, or stop execution, in order for it to be considered deterministic.

What is a Non-deterministic Turing Machine?[edit]

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, . 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 a sort of tree fashion 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 and then hold both state as one of the branches and state as another branch.

Quiz[edit]