Определение машины Тьюринга-Поста. Принцип Тьюринга- Поста.

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

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

Рассмотрим один из вариантов указанной машины.

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

1. Внешний алфавит, т.е. конечное множество символов А = {а₀, а₁, а₂,…, а_n}. В этом алфавите в виде слова кодируется та информация, которая подаётся в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово.

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

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

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

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

 

А0

а1

а2

а3

…

…

…

аn

а0

А0

q₀

 

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

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

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

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

В каждом такте работы машины она действует по функциональной схеме, которая имеет вид:

a_iq_{j Þ} a_v{п, л, н}q_s

Здесь a_i, a_v – буквы внешнего алфавита; q_j, q_s – состояния машины; п, л, н – символы сдвига.

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

1. Буква внешнего алфавита, на которую заменятся обозреваемая буква (a_v).

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

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

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

 

	a0	a1	a2
q1	a2 л q3	a1 п q2	a2 л q1
q2	a0 н q2	a2 н q1	a1 н q2
q3	a0 п q1	a1 п q4	a2 н q1
q4	a1 н q3	A0 п q4	a2 п q4

 

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