Теоретически закрытые и теоретически открытые задачи.

Введение понятия машины Тьюринга уточняет понятие алгоритма и указыва­ет путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальной информации (исходному слову алфавита). Та же ситуация повторяется относительно некоторых задач, для решения ко­торых не удается создать машины Тьюринга. Один из первых результатов такого типа получен Черчем в 1936 г. Он касается проблемы распознавания выводимости в математической логике.

1. Аксиоматический метод в математике заключается в том, что все теоремы данной теории получаются посредством формально-логического вывода из нескольких аксиом, принимаемых в данной теории без доказательств. Например, в математической логике описывается специальный язык фор­мул, позволяющий любое предложение математической теории записать в виде вполне определенной формулы, а процесс логического вывода из посылки Л следствия В может быть представлен в виде процесса фор­мальных преобразований исходной формулы. Это достигается путем ис­пользования логического исчисления, в котором указана система допус­тимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой, сколь угодно сложный формально-логический вывод.

Вопрос о логической выводимости следствия В из посылки Л является вопросом о существовании дедуктивной цепочки, ведущей от формулы А к формуле В. В связи с этим возникает проблема распознавания выводи­мости: существует ли для двух формул А и В дедуктивная цепочка, ве­дущая от А к В или нет. Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых А и В. Черчем эта проблема была решена отрицательно.

Теорема 5.8 (теорема Черча). Проблема распознавания выводимости алгоритмически неразрешима.

2. Проблема распознавания самоприменимости — вторая проблема, положи­тельное решение которой не найдено до сих пор. Ее суть заключается в следующем. Программу машины Тьюринга можно закодировать каким- либо определенным шифром. На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины. Здесь как и в случае обычной программы возможны два случая:

· машина применима к своему шифру, т. е. она перерабатывает этот шифр и после конечного числа тактов останавливается;

· машина неприменима к своему шифру, т. е. машина никогда не пере­ходит в стоп-состояние.

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

Теорема 5.9. Проблема распознавания самопрнмеинмостн алгоритми­чески неразрешима.

3. Проблема эквивалентности слов для ассоциативных исчислений.

Рассмотрим некоторый алфавит A = {a, b, c,...} и множество слов в этом алфавите. Будем рассматривать преобразования одних слов в другие с по­мощью некоторых допустимых подстановок α→β, где α и β — два слова в том же алфавите A. Если слово γ содержит α как подслово, на­пример α₁αα₂α₃α, то возможны следующие подстановки: α₁βα₂α₃α, α₁αα₂α₃β, α₁βα₂α₃β.

Ассоциативным исчислением называется совокупность всех слов в неко­тором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Для задания ассоциативного исчисления достаточно задать соответствующий алфавит и систему подстановок.

Если слово R может быть преобразовано в слово S путем однократного применения определенной подстановки, то R и S называются смежными словами. Последовательность слов R₁,R₂,...,R_n-1,R_n таких, что все пары слов R_i,R_i+1, i = 1,2,...,n-1 являются смежными, называется дедуктив­ной цепочкой, ведущей от слова R_i к слову R _n. Если существует цепочка, ведущая от слова R к слову S, то R и S называются эквивалентными: R~S.

Для каждого ассоциативного исчисления возникает своя специальная про­блема эквивалентности слов: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет.

Теорема 5.10. Проблема эквивалентности слов в любом ассоциатив­ном исчислении алгоритмически неразрешима.

Эта проблема решена лишь в некоторых ассоциативных исчислениях спе­циального вида.