Машины Тьюринга

Если для решения некоторой массовой проблемы известен.алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма, Автоматизм, необходимый при реализации алгоритма естественно приводит к мысли о передаче функции человека, реализующего алгоритм, машине. Идею такой машины предложили в тридцатые годы американский математик Э. Пост и английский математик А. Тьюринг.

Рассмотрим один из вариантов указанной машины, которая носит название машины Тьюринга.

Устройство машины Тьюринга включает в себя:

1. Внешний алфавит, то есть конечное множество

символов А = { a ₁, a ₂,.,., a _n } * В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово.

2. Внутренний алфавит машины, состоящий из символов q₁, q₂,.,., q_m,

п, л, н. Символы q₁, q₂,.,., q_m
выражают конечное число состояний машины. Для лю­бой машины число состояний фиксировано. Два состояния имеют особое назначение: q₁ - начальное состояние ма­шины, q₀ — заключительное состояние (стоп-состояние). Символы п, л, н - это символы сдвига (вправо, влево, на месте).

3. Бесконечная в обе стороны лента (внешняя память машины). Она разбита на клетки. В каждую клетку может быть записана только одна буква. Пустую
клетку будем обозначать символом a ₀.

Управляющая головка. Она передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т.е. воспринимать символ. В одном такте работы
машины управляющая головка может сдвигаться только на одну клетку (вправо, влево) или оставаться на месте.

Каждое сведение, хранящееся на ленте, изображает­ся конечным набором символов (букв) внешнего алфави­та, отличного от а₀. К началу работы машины на ленту

подается на­чальное сведение (начальная ин­формация). В этом случае управляю­щая головка, как правило, находится у крайнего левого знака с ука­занием начального состояния q_l (рис. 1) (начальная конфигурация). Работа машины складывается из тактов, по ходу которых происходит преобразование начальной ин­формации в промежуточные информации.

Рис 1.

В качестве начальной информации на ленту можно подать любую конечную систему знаков внешнего алфавита (любое слово в этом алфавите), расставленную произ­вольным образом по ячейкам. Но в зависимости от того, какая была подана начальная информация, возможны два случая:

1. После конечного числа тактов машина останавли­вается (переходит в стоп-состояние a ₀), и при этом на ленте оказывается изображенной информация В. В та­ком случае говорят, что машина применима к началь­ной информации А и перерабатывает ее в результирую­щую информацию В.

2. Машина никогда не останавливается (не переходит в стоп-состояние). В таком случае говорят, что машина не применима к начальной информации А.

a _i a _j 

Здесь a _v a _j — буквы внешнего алфавита; g_i q_s — состояния машины; п, л, н — символы сдвига.

В зависимости от того, какая буква на ленте обозре­вается управляющей головкой (в нашей записи а_i) и в каком состоянии (в нашей записи q_i) находится машина, в данном такте вырабатывается команда, состоящая из трех элементов:

2) Адрес внешней памяти для следующего такта

3) Следующее состояние машины (q_s).

Совокупность всех команд образует программу ма­шины Тьюринга. Программа представляется в виде двумерной таблицы и называется Тьюринговой функциональной схемой.

Пример такой схемы изображен на рис. 2 (машина Тьюринга 1).

Рис.2

Ясно, что работа машины Тьюринга полностью определяется ее программой. Иными словами, две машины Тьюринга с общей функциональной схемой неразличи­мы, и различные машины Тьюринга имеют различные программы.

Для простоты изображения различных конфигураций машины Тьюринга будем в дальнейшем записывать ин­формацию в виде слова, не изображая ленты и ее раз­бивки на клетки, а вместо изображения управляющей головки и состояния машины записывать только состо­яние машины.

Рассмотрим, как работает машина Тьюринга, задан­ная функциональной схемой 1.

Пример 1. Пусть начальная конфигурация имеет вид: