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

Для формального определения алгоритма математиками Тьюрингом (1936 г.) и независимо от него Постом (1937 г.) были предложены абстрактные вычислительные конструкции, которые позже были названы «машинами».

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

А={а о,а 1,…а m } – алфавит входных символов, где а о - пустая ячейка; Q= {q о,q 1,…q n } – алфавит состояний, где q о - конечное состояние, q 1 - начальное состояние.

Система команд МТ Ч итать содержимое ячейки С тирать и записывать символы в ячейку П еремещаться вправо(П), влево(Л), стоять неподвижно(Н) П ерейти в новое состояние

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

а0а0 а1а1 …аiаi …аmаm q0q0 q1q1 … qjqj Л а k П q p Н … qnqn Если в текущей ячейке – а i, то записать в неё а k, переместиться (Л, П или Н), затем перейти в новое состояние q p

Построить МТ, которая прибавляет 1 к натуральному десятичному числу на ленте. В начальный момент – головка напротив младшего разряда справа. q 1 – состояние изменения цифры Пример а0а0 012…89 q1q1 1Нq01Нq0 1Нq01Нq0 2Нq02Нq0 3Нq03Нq0 9Нq09Нq0 0Лq10Лq1

– всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Тезис Тьюринга

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