7
1. МАШИНА ТЬЮРИНГА
§ 1. Математическая модель машины Тьюринга
Идея создания машины Тьюринга, предложенная английским мате-
матиком А. Тьюрингом в тридцатых годах XX века, связана с его попыт-
кой дать точное математическое определение понятия алгоритма.
Машина Тьюринга (МТ) – это математическая модель идеализиро-
ванной цифровой вычислительной машины.
Машина Тьюринга является таким же математическим объектом, как
функция, производная, интеграл, группа и т. д. Так же как и другие мате-
матические понятия, понятие машины Тьюринга отражает объективную
реальность, моделирует некие реальные процессы.
Для описания алгоритма МТ удобно представлять некоторое устрой-
ство, состоящее из четырех частей: ленты, считывающей головки, устрой-
ства управления и внутренней памяти.
1. Лента предполагается потенциально бесконечной, разбитой на
ячейки (равные клетки). При необходимости к первой или последней клет-
ке, в которой находятся символы пристраивается пустая клетка. Машина
работает во времени, которое считается дискретным, и его моменты зану-
мерованы 1, 2, 3, … . В каждый момент лента содержит конечное число
клеток. В клетки в дискретный момент времени может быть записан толь-
ко один символ (буква) из внешнего алфавита
= {L,
121
,...,,
-n
aaa },
. Пустая ячейка обозначается символом L, а сам символ L называется
пустым, при этом остальные символы называются непустыми. В этом ал-
фавите
в виде слова (конечного упорядоченного набора символов) ко-
дируется та информация, которая подается в МТ. Машина «перерабатыва-
ет» информацию, поданную в виде слова, в новое слово.
2. Считывающая головка (некоторый считывающий элемент) пере-
мещается вдоль ленты так, что в каждый момент времени она обозревает