Введение понятия машины Тьюринга уточняет понятие алгоритма и указывает путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальной информации (исходному слову алфавита). Та же ситуация повторяется относительно некоторых задач, для решения которых не удается создать машины Тьюринга. Один из первых результатов такого типа получен Черчем в 1936 г. Он касается проблемы распознавания выводимости в математической логике.
1. Аксиоматический метод в математике заключается в том, что все теоремы данной теории получаются посредством формально-логического вывода из нескольких аксиом, принимаемых в данной теории без доказательств. Например, в математической логике описывается специальный язык формул, позволяющий любое предложение математической теории записать в виде вполне определенной формулы, а процесс логического вывода из посылки Л следствия В может быть представлен в виде процесса формальных преобразований исходной формулы. Это достигается путем использования логического исчисления, в котором указана система допустимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой, сколь угодно сложный формально-логический вывод.
Вопрос о логической выводимости следствия В из посылки Л является вопросом о существовании дедуктивной цепочки, ведущей от формулы А к формуле В . В связи с этим возникает проблема распознавания выводимости: существует ли для двух формул А и В дедуктивная цепочка, ведущая от А к В или нет. Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых А и В . Черчем эта проблема была решена отрицательно.
Теорема 5.8 (теорема Черча). Проблема распознавания выводимости алгоритмически неразрешима.
2. Проблема распознавания самоприменимости — вторая проблема, положительное решение которой не найдено до сих пор. Ее суть заключается в следующем. Программу машины Тьюринга можно закодировать каким- либо определенным шифром. На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины. Здесь как и в случае обычной программы возможны два случая:
- машина применима к своему шифру, т. е. она перерабатывает этот шифр и после конечного числа тактов останавливается;
- машина неприменима к своему шифру, т. е. машина никогда не переходит в стоп-состояние.
Таким образом, сами машины (или их шифры) разбиваются на два класса: самоприменимых и несамоприменимых тыоринговых машин. Проблема заключается в следующем: как по любому заданному шифру установить, к какому классу относится машина, зашифрованная им, к классу самоприменимых или несамоприменимых.
Теорема 5.9. Проблема распознавания самопрнмеинмостн алгоритмически неразрешима.
3. Проблема эквивалентности слов для ассоциативных исчислений.
Рассмотрим некоторый алфавит A = {a, b, c,…} и множество слов в этом алфавите. Будем рассматривать преобразования одних слов в другие с помощью некоторых допустимых подстановок ??, где ? и ? — два слова в том же алфавите A . Если слово ? содержит ? как подслово, например ?1??2?3?,то возможны следующие подстановки: ?1??2?3?, ?1??2?3?, ?1??2?3?.
Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Для задания ассоциативного исчисления достаточно задать соответствующий алфавит и систему подстановок.
Если слово R может быть преобразовано в слово S путем однократного применения определенной подстановки, то R и S называются смежными словами. Последовательность слов R1,R2,…,Rn-1,Rn таких, что все пары слов Ri,Ri+1, i = 1,2,…,n-1 являются смежными, называется дедуктивной цепочкой, ведущей от слова Ri к слову Rn. Если существует цепочка, ведущая от слова R к слову S, то R и S называются эквивалентными: R~S.
Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет.
Теорема 5.10. Проблема эквивалентности слов в любом ассоциативном исчислении алгоритмически неразрешима.
Эта проблема решена лишь в некоторых ассоциативных исчислениях специального вида.
Статьи к прочтению:
Семён Слепаков и Марина Кравец: Разговор мужа с женой
Похожие статьи:
-
Решение задачи: Задача 76 (необязательная).При внимательном прочтении второго утверждения становится понятно, что все листья дерева Т должны быть…
-
Решение задач 90—102 из учебника
Задача 90 (необязательная). Стратегии решения таких задач подробно описаны в комментарии к задаче 44. Задача 91 (необязательная).Задача на повторение…