Основная гипотеза теории алгоритмов

Машина Тьюринга даёт один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: насколько общим является понятие машины Тьюринга? Можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным? Может ли всякий алгоритм задаваться таким образом?

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:

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

Эта гипотеза называется тезисом Тьюринга. Её нельзя доказать, т.к. она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга.

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

Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

Напомним также, что другие способы уточнения понятия алгоритма (понятие нормального алгоритма А.А.Маркова, понятие рекурсивного алгоритма (рекурсивной функции), введённого Чёрчем, Гёделем и Клини) оказались равносильными.

Этот факт является важным доводом в пользу сформулированной гипотезы.

Примеры алгоритмически неразрешимых массовых задач.

Неразрешимые алгоритмические проблемы

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

На этот вопрос теория алгоритмов в ряде случаев дает отрицательный ответ. Один из первых результатов такого типа получен американским математиком Чёрчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике.

1. Неразрешимость проблемы распознавания выводимости в математической логике.

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

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

Вопрос о логической выводимости предложения В из посылки А в избранном логическом исчислении является вопросом о существовании дедуктивной цепочки, ведущей от формулы А к формуле В.

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

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

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

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

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

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

Например, ранее встречающуюся конфигурацию

Q4 будем записывать в виде | q4|| • В связи с этим будем пользоваться следующей таблицей кодирования: Алфавит Буква Кодовая группа Примечания Буквы адресов л Один нуль между 1     н два нуля между 1     п три нуля между 1 Внешний алфавит а0 100001 4 нуля четное число нулей, большее двух     а1 10000001 6 нулей                                   an 10...01 2(n+2) нулей     Внутрен-ний алфавит q1 1000001 5 нулей нечетное число нулей, большее трех     q2 100000001 7 нулей         ..                   qm 10...01 2(n+1)+1 нулей     Подобную строчку из единиц и нулей, составленную для функциональной схемы или для отдельной конфигурации называют шифром функциональной схемы или широм конфигурации. Пусть теперь на ленте машины Тьюринга изображен ее же собственный шифр, записанный в алфавите машины. Возможны два случая: 1. Машина применима к своему шифру, т.е. она перерабатывает этот шифр и после конечного числа тактов останавливается. 2. Машина не применима к своему шифру, т.е. машина никогда не переходит в стоп-состояние. Таким образом, сами машины (их шифры) разбиваются на два класса: класс самоприменимых и класс несамоприменимых тьюринговых машин. Поэтому возникает следующая массовая проблема: проблема распозн ваемости самоприменимости. По любому заданному шифру установить, к какому классу относится машина, зашифрованная им: к классу самоприменимых или несамоприменимых? Теорема. Проблема распознавания самоприменимости алгоритмически не разрешима. Доказательство. Предположим противное. Пусть такая машина А существует. Тогда в А всякий самоприменимый шифр перерабатывается в какой-то символ s (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамоприменимый шифр - в другой символ tt (имеющий смысл отрицательного ответа на поставленный вопрос). В таком случае можно было построить и такую машину В, которая по-прежнему перерабатывает несамоприменимые шифры в s, в то время как к самоприменимым шифрам В уже не применима. Этого можно было добиться путем такого изменения схемы машины В, чтобы после появления символа а вместо появления стоп-состояния, машина начала бы неограниченно повторять этот же символ. Таким образом, В применима ко всякому несамоприменимому шифру (вырабатывается при этом символ t) и не применима к самоприменимым шифрам. Но это приводит к противоречию. Действительно: 1) пусть машина В самоприменима, тогда она применима к своему шифру В и перерабатывает его в символ t; но появление этого символа как раз и должно означать, что В несамоприменима; 2) пусть В несамоприменима, тогда она не применима к В, что должно означать как раз, что В самоприменима. Полученное противоречие доказывает теорему.