Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 7 стр.

                          1. МАШИНА ТЬЮРИНГА

              § 1. Математическая модель машины Тьюринга

     Идея создания машины Тьюринга, предложенная английским мате-
матиком А. Тьюрингом в тридцатых годах XX века, связана с его попыт-
кой дать точное математическое определение понятия алгоритма.
     Машина Тьюринга (МТ) – это математическая модель идеализиро-
ванной цифровой вычислительной машины.
     Машина Тьюринга является таким же математическим объектом, как
функция, производная, интеграл, группа и т. д. Так же как и другие мате-
матические понятия, понятие машины Тьюринга отражает объективную
реальность, моделирует некие реальные процессы.
     Для описания алгоритма МТ удобно представлять некоторое устрой-
ство, состоящее из четырех частей: ленты, считывающей головки, устрой-
ства управления и внутренней памяти.
     1. Лента предполагается потенциально бесконечной, разбитой на
ячейки (равные клетки). При необходимости к первой или последней клет-
ке, в которой находятся символы пристраивается пустая клетка. Машина
работает во времени, которое считается дискретным, и его моменты зану-
мерованы 1, 2, 3, … . В каждый момент лента содержит конечное число
клеток. В клетки в дискретный момент времени может быть записан толь-
ко один символ (буква) из внешнего алфавита A = {�, a1 , a 2 ,..., a n �1 },

n � 2 . Пустая ячейка обозначается символом �, а сам символ � называется
пустым, при этом остальные символы называются непустыми. В этом ал-
фавите A в виде слова (конечного упорядоченного набора символов) ко-
дируется та информация, которая подается в МТ. Машина «перерабатыва-
ет» информацию, поданную в виде слова, в новое слово.
     2. Считывающая головка (некоторый считывающий элемент) пере-
мещается вдоль ленты так, что в каждый момент времени она обозревает
                                     7