7.Распознающие машины Тьюринга и языки. Проблема распознавания языков.

Машина, которая за конечное время определит, является ли выражение корректным или нет(В первом случае машина закончит свою работу в состоянии YES, а во втором – в состоянии NO) называется распознающей. Распознать некоторый объект – значит определить, удовлетворяет ли он определенным условиям или нет. Задача распознавания в общем может быть неразрешимой. Например, нельзя построить распознаватель для выяснения вопроса о существовании рациональных корней произвольного диофантова уравнения. Использующие упрощенный набор правил машины называются автоматом.

Теорема. Всякий недетерминированный регулярный автомат можно реализовать с помощью эквивалентного детерминированного регулярного автомата.

8.Неразрешимость проблемы самоприменимости.

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

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

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

Следовательно, Х всегда в состоянии пройти через лабиринт и должен получить сертификат по формальным признакам. Однако, если Х получит сертификат, то при использовании Х-ом другого такого Х, он может не выбраться из лабиринта, поскольку сам по себе Х может не найти путь.

Следовательно, Х нельзя сертифицировать, хотя Х способен пройти через лабиринт.

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

Мы получили следующий результат.

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

Обозначим через перечисление всех областей сходимости машин Тьюринга с номерами y1, y2,…, yk, ….. соответственно.

Сформулируем проблему: можно ли для любого числа x выяснить, x ? Если бы такой алгоритм W был, то у него был бы некоторый геделев номер, скажем . Спросим S_ ? Если да, то W должен принять  по определению , что невозможно. Если нет, т.е. S_, то W сходится на , а это значит, по условию, что S_ - снова противоречие. Самопримени́мость в теории алгоритмов — свойство алгоритма успешно завершаться на данных, представляющих собой формальную запись этого же алгоритма.

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

Доказательство алгоритмической неразрешимости

Доказательство от противного. Допустим, что алгоритм, распознающий самоприменимость, существует. На основании тезиса Тьюринга существует и машина Тьюринга, реализующая этот алгоритм. Обозначим такую машину как A. На её ленту заносится каким-либо образом закодированная программа другой машины Тьюринга, а после работы занесённые данные перерабатываются в какое-то слово y, если исходная программа была самоприменима, или в слово n, если она была несамоприменима.

Вторым шагом немного модифицируем машину A так, чтобы она по-прежнему перерабатывала несамоприменимые программы в n, а на самоприменимых программах зацикливалась, то есть являлась неприменимой к ним. Сделать подобное преобразование очень легко — после записи слова y машина не заканчивает работу, а продолжает бесконечно записывать его на ленту. Обозначим эту машину как A1. Существование такой машины приводит к противоречию, потому что A1 не может быть ни самоприменимой, ни несамоприменимой. Действительно, если A1 самоприменима, то она применима к собственной записи. Но по построению машины A1 это свидетельствует как раз о том, что A1 несамоприменима. Если же A1 несамоприменима, то по построению она применима к собственной записи, так как она применима к любой записи несамоприменимой машины. Но это как раз означает, что A1 самоприменима. Исходя из этого делается вывод о невозможности построения машины A, поскольку тогда из неё легко можно было бы получить A1.