2018 | OriginalPaper | Chapter

# 10. Turing Machine

Published in:
The Discrete Math Workbook

## Abstract

In order to formalize the concept of an algorithm, Turing suggested a mathematical model of a computing machine. Turing machine is an abstract-computing device consisting of a tape, a reading and printing head and a control device.

Let us consider some elements of a Turing machine in more detail.

1. Tape is divided into similar cells and is supposed to be unlimited on both sides. In other words, the number of cells in each certain moment of time is finite, but when necessary their number can be increased.

2. Reading and writing head moves along the tape and at each moment of time observes one cell of the tape. At this moment, the head reads the content of this cell and writes into it some symbol from the alphabet \(\Sigma \).

3. Control device at each moment of time is in some state \(q_i\); the set of all states \(Q=\{q_0, q_1, \dots , q_n\}\), \(n\geqslant 1\), is called the internal alphabet. Among all \(q_i\), \({0\leqslant i\leqslant n}\), initial and final states are distinguished. It is usually assumed that there exists one initial state, \(q_1\), and one final state, \(q_0\).

The Turing machine is not the only way to formalize the concept of an algorithm. Similar approaches are known, leading to equivalent results, among which we should mention the Post machine and the Markov normal algorithm.