23 Частично и общерекурсивные функции.

Функция рекурсивна, если есть эффективная процедура для ее вычисления. Процедура эффективна , если она выполняется по механическим правилам.

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

Совокупность числовых функций совпадающая с совокупность. Всех вычислимых функций – совокупность рекурсивных функций.

Функция является обще-рекурсивной, если она определена посредством ряда уравнений некоторого типа. Затруднение вызвано тем, что просмотр такого выбора уравнений обычно не убеждает нас в том, что эти уравнения “определяют” какую-либо функцию вообще. Когда говорится “функция”, обычно понимается под этим “правило, которое каждому значению (или набору из п значений, если мы имеем функцию n переменных) ставит в соответствие результирующее значение”. Но в общем случае система уравнений не всегда дает определенное значение. Т.о. вполне допустимой является ситуация, когда для некоторых точек (или даже для всех!!) значение функции не определено – считается что в этих точках сама функция не определена. Это явление весьма характерно. Поэтому, делая предположение, что система уравнений действительно определяет обще-рекурсивную функцию, нужно всегда проявлять осторожность. Мы обычно требуем дополнительного доказательства этого положения, например, в виде индуктивного доказательства того, что для каждого значения аргумента вычисление завершается выдачей единственного значения. Вследствие этого будем обычно говорить о частично-рекурсивной функции. Когда мы говорим о частично-рекурсивной функции (или, короче, частичной функции) F(x), то понимаем, что может не существовать значения, определенного для некоторого (или даже любого!) значения х. Если F(x) оказывается определенной для всех значений х, то мы называем ее обще-рекурсивной функцией или, короче, общей функцией. Конечно, любая обще-рекурсивная функция также может считаться частично-рекурсивной.

Тезис Черча в узком смысле: Класс рекурсивных функций тождественен классу всюду определенных вычислимых функций.

Тезис Черча в узком смысле Всякая вычислимая функция с аргументами и значениями является частичнорекурсивной.

Тезис Черча-Клини: Все частичные функции вычислимые посредством алгоритма являются частично-рекурсивными.

Частично-рекурсивная функция это класс числовых функций, который строится при помощи следующих операторов , элементарных арифметических функций

Λ(х)=х+1 оператор ствига

O(x1, x2, xN )=0 оператор онулирования

=(x1, x2, xN)= xM 1<=m<=n оператор проэктирования

Вопрос 24

В 1936 г Черч сформулировал гипотезу под названием Тезисы Черча.

Тезис Черча в широком смысле:

Класс рекурсивных функций тождественен классу всюду определенных вычислительных функций. (Понятие вычислимой функции точно не определяется поэтому доказать тезис Черча нельзя).

Тезис Черча в узком смысле:

Всякая вычислительная функция с натуральным аргументом и значениями является частично-рекурсивной.

Тезис Черча-Клини:

Все частичные функции, вычисляемые посредством алгоритма, являются частично рекурсивными.

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