2.19 Понятие алгоритма. Описание машины тьюринга
Для решения ряда однотипных задач иногда целесообразно использовать чисто механические вычислительные процессы. Описание таких процессов называют алгоритмами.
Интуитивно: алгоритм – это некоторое формальное предписание, действуя согласно которому, можно получить решение задачи. Примеры алгоритмов:
- Нахождение наибольшего общего делителя двух натуральных чисел.
- Извлечение корня квадратного из рационального числа с заданной точностью.
- Вычисление ранга матрицы, и так далее.
Перечисленные алгоритмы имеют ряд общих черт, которые естественно считать присущими любому алгоритму:
Дискретность. Решение задачи разбивается на этапы, каждый из которых прост и локален.
Детерминированность. После выполнения очередного этапа однозначно определено, что сделать на следующем этапе.
Направленность. Должно быть указано, что считать результатом применения алгоритма.
Массовость. Алгоритм служит для решения целого класса однотипных задач.
Конечность. Для решения задачи выполняется конечная последовательность шагов алгоритма.
Тезис Тьюринга Всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Определение. Машиной Тьюринга (м-т) называется тройка 
, где 
—внешний алфавит, обычно 
; 
—внутренний алфавит, элементами которого являются состояния управляющего устройства, 
—заключительное состояние, 
—начальное состояние; 
—программа, состоящая из команд вида: 
, где 
—один из символов: 
(налево), 
(направо), 
(на месте), 
, 
.
Имеется бесконечная в обе стороны лента, разбитая на ячейки. В начальный момент в конечном числе ячеек записаны символы из 
, в остальных ячейках записан пустой символ, обозначаемый через 
. Машина Тьюринга имеет головку, которая в любой момент времени обозревает некоторую ячейку, и управляющее устройство, которое может находиться в одном из состояний 
.
Шаг работы м-т. Если м-т имеет состояние 
, в обозреваемой ячейке записан символ 
, то выполняется команда , м-т переходит в состояние 
, в ячейке на место , записывается 
и головка сдвигается влево, вправо или остается на месте в зависимости от символа .
В начальный момент м-т находится в состоянии , останавливается м-т, если перейдет в одно из заключительных состояний либо при отсутствии команды, которую можно выполнить.
Конфигурацией (машинным словом) называется слово 
, где 
— слово на ленте левее головки, 
— слово правее головки, включая символ под головкой.
Говорят, что м-т 
применима к слову , если , начав работу на слове , машина остановится через конечное число шагов; если в результате получится слово 
, то пишут 
. Если 
не остановится, то она не применима к слову .