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

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

Простейшие функции:

1) оператор сдвига ;

2) оператор аннулирования ;

3) оператор проектирования если

Простейшие функции всюду определены и интуитивно вычислимы.

Даны функции Функция называется суперпозицией функций Если функции интуитивно вычислимы, то и функция интуитивно вычислима.

Даны функции Построим с помощью этих функций новую функцию a , то есть по всегда можно найти значение Говорят, что функция получена из функций и по схеме примитивной рекурсии. Есть функции и интуитивно вычислимы, то и функция интуитивно вычислима.

Дана функция Рассмотрим функцию , равную наименьшему значению переменной y, при котором . Переход от функции к функции называют применением - оператора.

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

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

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