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

Тезис Черча нельзя доказать, т.к. он связывает нестрогое математическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции. Но в поддержку этого тезиса впоследствии другими авторами были приведены очень веские доводы.

В 1936 году Тьюрингом был определен еще один класс интуитивно вычислимых функций и сформулирован тезис Тьюринга, эквивалентный тезису Черча. В результате попыток разложить интуитивно известные вычислительные процедуры на элементарные операции построена математическая модель, называемая машиной Тьюринга. Повторение элементарных операций, определенных в этой машине, достаточно для проведения любого возможного вычисления. От человека-исполнителя эта машина отличается двумя особенностями:

Ø она не ошибается, т.е. она без всяких отклонений выполняет правила, установленные для ее работы;

Ø она снабжена потенциально бесконечной памятью. Это значит, что хотя в каждый момент количество накопленной информации конечно, для этого нет никакой верхней грани. В качестве накопителя рассматривается бесконечная лента.

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

Рис. 3.1.

Машина Тьюринга включает:

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

1. Внутренний алфавит Q = . Иногда символы C, P, E отсутствуют. Символы q₀, q₁, …, q_m выражают конечное число состояний машины, причем q₁ – начальное состояние, q₀ – стоп-состояние.

1. Бесконечную в обе стороны ленту, представляющую память машины. Эта память разбита на клетки. В каждую клетку может быть записана только одна буква. a₀ – пустая клетка, она всегда может появиться при движении вправо или влево, если закончится слово исходной информации a₀a₁a₂…a_n.

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

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

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

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

и a_i – буква на ленте, обозреваемая управляющей головкой на данном такте, q_j – текущее состояние машины на данном (в общем случае не i -м и не j -м) такте.

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

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

2. Адрес внешней памяти и дополнительные действия для выполнения на следующем такте R, L, C, P или E.

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

Существует несколько способов представления набора правил преобразования, т.е. работа машины Тьюринга может быть описана следующим образом:

ü системой правил (команд), имеющих вид ; (3.4)

ü таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении строки и столбца записана тройка символов Б либо блок-схема, которую будем называть диаграммой переходов;

ü диаграммой (графом) переходов.

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

Таблица 3.1

Состояния	Символы внешнего алфавита
		...
			...
			...
...	...	...	...	...
			...

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

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

Диаграмма переходов – это граф, вершинам которого соответствуют состояния машины Тьюринга, а ребрам – команды (рис. 3.2).

Рис. 3.2.

В диаграмме переходов состояниям соответствуют вершины, а правилу вида (3.4) – ребро, ведущее из в , на котором написано . Условие однозначности требует, чтобы для любого j и любого в системе команд имелась только одна команда, аналогичная (3.4), с левой частью . Состояние в левых частях команд не встречается На диаграмме переходов это выражается условием, что из каждой вершины, кроме , выходит ровно m ребер (m – число символов в алфавите ленты), причем на всех ребрах, выходящих из одной вершины, левые части различны, а в вершине нет выходящих ребер. В дальнейшем будем опускать символы и , если .

Рассмотрим теперь, как выполняются основные требования к алгоритмам в построенной алгоритмической модели – машине Тьюринга.

Данные машины Тьюринга – это слова в алфавите ленты.

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

Детерминированность машины определяется тем, что для любого внутреннего состояния и символа однозначно заданы:

a) следующие состояния ;

b) символ , который нужно записать вместо в ту же ячейку (стирание символа будем понимать как запись символа );

c) направление сдвига головки , обозначаемое одним из трех символов: L (влево), R (вправо), C (на месте).

Элементарные шаги машины – это считывание и запись символов, сдвиг на ячейку влево или вправо, а также переход управляющего устройства в следующее состояние.

Результатом работы машины Тьюринга является слово на ленте после остановки машины.

Возможность выбора в качестве начальной системы любого слова в алфавите ленты обеспечивает массовость машины Тьюринга.

Таким образом, построенная машина Тьюринга – конкретная алгоритмическая модель, претендующая на право формализации понятия «алгоритм».

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

Пример 1. Конфигурация с внутренним состоянием , в которой на ленте записано abcde, а головка обозревает d, запишется как abcq_ide.

						qi
...			a	b	c	d	e			...	Δ

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

Стандартной заключительной конфигурацией назовем конфигурацию вида .

Ко всякой не заключительной конфигурации K машины Тьюринга применима ровно одна команда вида (3.4), которая переводит конфигурацию в . Обозначим это . Если для и существует последовательность конфигураций такая, что , то обозначим это .

Пример 2. Пусть в системе команд машины Тьюринга имеются команды и , тогда и, следовательно,

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

Пример 3. Машина с алфавитом , состояниями и системой команд при любой начальной конфигурации будет работать бесконечно, заполняя единицами всю ленту вправо от начальной точки. Δ

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

Запись на ленте словарного вектора назовем правильной, если она имеет вид либо , где * – символ-разделитель, .

Пусть f – функция, отображающая множество векторов над в себя. Машина Тьюринга вычисляет функцию f, если:

1) для любых векторов V, W, таких, что f(V)=W, , где V^*, W^* – правильные записи V и W соответственно;

2) для любого вектора V, такого, что f(V) не определено, машина Тьюринга, запущенная в стандартной начальной конфигурации , работает бесконечно.

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

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

Пример 4. Сложение. Во введенном раннее представлении чисел сложить числа a и b – это значит слово переработать в слово , т.е. удалить разделитель * и сдвинуть одно из слагаемых, скажем первое, к другому. Это осуществляет машина Тьюринга с четырьмя состояниями и следующей системой команд (первая команда введена для случая, когда a=0 и исходное слово имеет вид ):

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

Рис. 3.3. Диаграмма переходов машины Т₊

Пример 5. Копирование слова, т.е. переработка слова в . Для чисел эту задачу решает машина Тьюринга Т_коп с системой команд, представленной в табл. 3.2.

Таблица 3.2

			*
				–
			–	–
		–

При первом проходе в состоянии ставится маркер (символ *) справа от исходного числа . Далее при каждом проходе исходного числа машина Т_коп заменяет левую единицу числа нулем и пишет (в состоянии ) одну единицу справа от в ближайшую пустую клетку. Таким образом, копия строится за a проходов. После записи очередной единицы машина переходит в состояние , которое передвигает головку влево до ближайшего нуля, после чего машина переходит в , и цикл повторяется. Он прерывается, когда обнаруживает на ленте не единицу, а маркер, тогда головка возвращается влево в свое исходное положение, заменяя по дороге все нули единицами. Диаграмма переходов Т_коп дана на рис. 3.4.

Рис. 3.4. Диаграмма переходов машины Т_коп

На этой диаграмме, а также на последующих, приняты следующие сокращения:

1) если в ведут два ребра с одинаковой правой частью, то они объединяются в одно ребро, на котором левые части записаны через запятую;

2) если символ на ленте не изменяется, то он в правой части команды не пишется.

Отметим, что на петле использованы одновременно два сокращения.

Поиск по сайту: