ФЭНДОМ


Машина Тьюринга - это головка для считывания/записи по бесконечной ленте.

Машина

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

Для ее работы необходимо задать 2 алфавита: символов A={a0, a1, a2...am} и состояний машины Q={q0, q1, q2...qp}, причем q0принимается за пассивное состояние, q1 за начальное, а a0-это пустая ячейка.

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

Программу для м. Т. можно представить в виде матрицы:

a0 a1 ... al ... am
q1
q2
...
qj al{Л,П,Н}qm
...
qp

т.е. сначала мы записываем действие с ячейкой (написать что-то, не трогать ничего), потом передвижение по ленте, а потом состояние, в которое машина перейдет.


Если в машине Тьюринга T, которая кодируется, δ(i, a) = ( j, b, D), то подблок, соответствующий состоянию i и входному символу a, будет содержать j единиц, за которыми следует символ D ∈{L, R}, а за ним b ∈ {0, 1}. Если δ(i, a) не определено, то соответствующий подблок будет содержать единственный

нуль.


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

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


Даны описание алгоритмаи его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.

Рассмотрим множествоS алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множествоS лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел(N,X), и:

  • останавливается и возвращает 1, если алгоритм с номеромN не останавливается, получив на входX
  • не останавливается в противном случае (если алгоритм с номеромN останавливается, получив на входX).

Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?

Теорема. Анализатор не существует.

Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход числоN, передает пару аргументов(N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не остановливается алгоритм с номеромN, получив на вход числоN. ПустьK - это порядковый номер Диагонализатора в множествеS. Запустим Диагонализатор, передав ему это числоK. Диагонализатор остановится в том и только том случае, если алгоритм с номеромK (то есть, он сам) не останавливается, получив на вход числоK (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.

Материалы сообщества доступны в соответствии с условиями лицензии CC-BY-SA , если не указано иное.