§4.2. Машина Тьюринга

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

Определение.

Машиной Тьюринга называется частичное отображение

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

один из символов 0, 1. Считывающая головка машины обозревает в каждый момент времени одну из ячеек и за один такт, сменяющий два последовательных момента времени, может перемещаться влево или вправо. Машина Тьюринга в каждый момент времени находится в одном из состояний а в следующий момент времени переходит в другое состояние или остаётся в том же. Кроме того, машина может изменять символ, стоящий в обозреваемой ячейке. Все эти преобразования – изменение состояния, информация на ленте, направление движения полностью определяются отображением А именно, если то в случае, когда машина находится в состоянии а на обозреваемой в данный момент ячейке написан символ машина должна записать в эту ячейку вместо перейти в состояние и сдвинуться на одну ячейку влево.

В случае, когда

те же действия будут сопровождаться сдвигом вправо. Например, равенство

означает, что, находясь в состоянии

и обозревая ячейку, в которой написан символ 1, машина должна сохранить в этой ячейке символ 1, сдвинуться вправо и перейти в состояние

Если же

не определено, то машина, находясь в состоянии

и обозревая ячейку с символом

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

Замечания. 1. Существуют различные модификации машины Тьюринга (машина Поста, машина Минского и т.д.). Некоторые модификации предусматривают на ленте не символы 0 или 1, а буквы некоторого конечного алфавита В некоторых определениях разрешается не только сдвиг головки машины влево или вправо, но и оставление на прежней позиции. Однако, различные модификации машины Тьюринга эквивалентны между собой в том смысле, что классы функций, вычислимых на этих машинах, совпадают.

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

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

Опишем составление программы. Для каждого равенства вида

где

номера состояний,

направление движения, а

символы на ленте, запишем строку

и назовём её командой. Совокупность всех команд – это и есть программа. Если

не определено, то в программе нет ни одной команды, начинающейся с

Кроме того, для любых

в программе есть не более одной команды, начинающейся с

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

Алгоритм действий можно записать словами:

1-й шаг: пройти первый массив единиц, найти массив из нулей, идущий после него и заменить первый нуль единицей;

2-й шаг: идти через массив нулей, заменяя их единицами, до тех пор, пока не появится второй массив единиц;

3-й шаг: пройти второй массив единиц и остановиться в его конце.

Машина Тьюринга, реализующая этот алгоритм, имеет следующую программу:

	1-й шаг
	2-й шаг
	3-й шаг

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

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

(массивы из единиц имеют длины 1, 2, 3, ...), а эта последовательность периодической не является.

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

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

Таким образом, если, например, то мы должны иметь

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

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

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

Машина Тьюринга была придумана Аланом Тьюрингом и описана в его статье в 1936 г. Конечно, она уступает современным вычислительным машинам в удобстве использования для решения конкретных задач. Тем не менее она сыграла большую роль в создании вычислительной техники. К настоящему времени она сохранила своё теоретическое значение для решения вопроса об алгоритмической разрешимости задач. Решение типовых задач

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

а) б)

Решение. а) Фактически надо, имея следующую ситуацию на ленте

уничтожить все единицы, кроме первой. Пусть состояние, в котором машина ищет крайнюю правую единицу, попутно стирая все единицы, начиная со второй, движение влево до оставшейся единицы.

Программа машины выглядит так:

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

Программа машины выглядит так:

	находим последнюю единицу в первом массиве из единиц и стираем её, если она не единственная
	то же делаем со вторым массивом из единиц
	возвращаемся к крайней левой единице
	заменяем промежуточные нули единицами
	стираем последние две единицы и останавливаемся у крайней левой единицы

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

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