ОПРЕДЕЛЕНИЕ. Функции, получаемые из простейших с помощью конечного числа применений операций суперпозиции, примитивной рекурсии и минимизации

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

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

8.3. ТЕЗИС ЧЁРЧА

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

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

Класс всех интуитивно вычислимых числовых функций

совпадает с классом частично-рекурсивных функций

Приведенное утверждение носит название тезиса Чёрча, по имени сформулировавшего этот тезис американского математика.

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

О справедливости тезиса Чёрча свидетельствуют следующие имеющиеся факты:

1)для всякой конкретной числовой функции удается построить её рекурсивное определение;

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