Машинная математика. Машина Тьюринга

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

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

1) Машина Тьюринга не может ошибаться.

2) Машина Тьюринга имеет потенциально бесконечную память.

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

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

2) Внутренний алфавит состоит

- из множества символов { , ,…, }, которое определяет состояния машины Тьюринга;

- символов: - вправо, - влево, - на месте.
Символы называются операторами сдвига. Начальное состояние машины Тьюринга обозначается символом . Конечное состояние – символом .

3) Внешняя память, состоит из бесконечной в обе стороны ленты.

Память состоит из регистров, в каждый из которых

можно вписать одну букву алфавита. Принято, что в

пустом регистре по умолчанию находится символ .

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

В зависимости от того, какой была начальная информация, возможны два случая:

1) после обработки информации машина переходит в состояние (иначе говорят - машина применима к начальной информации);

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

н

где – буквы внешнего алфавита; - состояния машины; - операторы сдвига.

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

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

Пусть на ленте записано число

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

После выполнения команды на ленте появится следующая информация

На следующем такте после выполнения команды

После выполнения команды машина переходит в состояние и завершает работу с получением результата 834.

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

		+
		-

Пусть исходная информация на ленте представлена так

В состоянии устраняется самая правая единица и машина переходит в состояние . В состоянии управляющая головка перемещается, не изменяя состояния регистров, до тех пор, пока не будет достигнут символ . Символ заменяется на и машина переходит в конечное состояние .

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

		/	-
	-
	-		-

В состоянии устраняется самая правая единица и машина переходит в состояние , при котором управляющая головка, не меняя содержимого регистров, достигает самую крайнюю левую позицию, то есть . В следующем такте машина переходит в новое состояние , при котором устраняется самая правая единица, затем

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

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

Дата добавления: 2015-06-27