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

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

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

Машина Тьюринга – это математическая модель идеализированной (примитивной) цифровой вычислительной машины.

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

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

Множество А называют внешним алфавитом машины. Один символ из А называется пустым или «пробелом» - . Ячейка ленты, в которой записан символ , называется пустой.

Машина работает во времени, которое считается дискретным. В каждый момент времен головка находится над определенной ячейкой ленты и считывает символ.

лента памяти: a_i Є A

а_к

Головка (чтение, запись, перемещение)

УУ (программа)

Рис 1. Машина Тьюринга

В каждый момент времени t_i лента содержит конечное число клеток. Лента потенциально бесконечна, т.е. к ней как справа, так и слева могут быть добавлены новые ячейки.

Головка может остаться на той же клетке (Н-состояние), сдвинуться на одну клетку вправо (П), сдвинуться на одну клетку влево (Л) (Если сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка).

Машина обладает внутренней памятью – некоторое конечное множество состояний Q = {q₀, q₁, … q_k}

q₀ – заключительное состояние

q₁ – начальное состояние

Движение головки зависит от считываемого символа и внутреннего состояния машины.

Устройство управления в каждый момент времени t:

изменяет считываемый символ a_i на a_j .

передвигает головку в одном из направлений Н, Л, П.

изменяет внутреннее состояние машины q_i на новое q_j, в котором будет машина в момент t + 1

Такое действие УУ называют командой, и она записывается:

q_ia_i a_j Dq_j, где D Є {Н, Л, П}

Выполнение одной команды называется шагом.

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

В начальный момент времени конфигурация такова:

1. на ленте, состоящей из некоторого числа ячеек (рис. 2) записаны символы внешнего алфавита А;

2. головка находится над первой слева клеткой ленты.

3. внутреннее состояние машины q₁.

Будем считать машину Тьюринга заданной, если известна ее программа.

Рис.2 Начальная конфигурация машины Тьюринга

Зная программу и задав начальную конфигурацию, полностью определяем работу машины над словом. Будем считать, что машинное слово M получается из машинного слова М с помощью машины Т, и записывать M_i  ^TM, если существует последовательность преобразований M_i^TM_i+1, i=0,1,…,k-1, для которой M₀=M, M_k=M.

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

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

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

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