Соотношения между классами примитивно рекурсивных, общерекурсивных и частично рекурсивных функций.

Определение 2. Функция f(x₁, x₂,…, x_n) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и m-оператора.

Определение 3. Функция f(x₁, x₂,…, x_n) называется общерекурсивной, если она частично рекурсивна и всюду определена.

Примерами общерекурсивных функций являются: f(x, y) = x + y, f(x, y) = x × y, f(x, y) = x + n.

1)l(х), 2)О(х), 3) I_n^m(x₁, x₂,…, x_n),

Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.

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

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

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

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

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

На этот вопрос теория алгоритмов в ряде случаев дает отрицательный ответ. Один из первых результатов такого типа получен американским математиком Чёрчем в 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) пусть В несамоприменима, тогда она не применима к В, что должно означать как раз, что В самоприменима. Полученное противоречие доказывает теорему.