# Turing machines

(2.5 hours to learn)

## Summary

Turing machines are a simple theoretical model of computation involving a head which reads and writes symbols on a tape. Despite its simplicity, if the Church-Turing Thesis is true, then anything which can be computed, can be computed by a Turing machine. They are a fundamental construct in reasoning about the limits of computation.

## Context

-this concept has no prerequisites-

## Goals

- Define a Turing machine

- Be able to write Turing machines to solve simple problems

- Be aware of universal Turing machines

- Be aware of the Church-Turing thesis

## Core resources (read/watch one of the following)

## -Free-

→ Coursera: Automata

An introductory course on automata and the theory of computation.

Location:
Lecture "Turing machines"

Other notes:

- Click on "Preview" to see the lecture videos.

## -Paid-

→ Introduction to the Theory of Computation

An undergraduate textbook on automata and the theory of computation.

- Section 3.1, "Turing machines," pages 137-147
- Section 3.3, "The definition of algorithm," pages 154-159

→ Automata Theory, Languages, and Computation

An undergraduate textbook on automata and the theory of computation.

- Section 8.2, "The Turing machine," pages 324-335
- Section 8.3, "Programming techniques for Turing machines," pages 337-343

Other notes:

- Read Section 8.1, "Problems that computers cannot solve," for some motivation.

## See also

-No Additional Notes-