Рассмотрим функцию f(x, y) = х - у, которая может быть получена с помощью оператора минимизации:
Вычислим, например, f(7,2,), т.е. значение функции при у = 2 и х = 7. Положим у = 2, а х будем придавать последовательные значения:
Таким образом, найдено значение функции f(7,2) = 5.
Введем определение:
Частичная функция f(х1,...,хп) называется частично рекурсивной,если ее можно получить конечным числом операций суперпозиции, примитивной рекурсии и минимизации, исходя лишь из простейших функций S1, 0n и Imn.
Класс частично рекурсивных функций шире класса примитивно рекурсивных функций, т.к. все примитивно рекурсивные функции являются всюду определенными, а среди частично рекурсивных функций встречаются функции не всюду определенные, а также нигде не определенные.
Понятие частично рекурсивной функции является одним из главных понятий теории алгоритмов. Значение его состоит в следующем. С одной стороны, каждая стандартно заданная частично рекурсивная функция вычислима путем некоторой процедуры механического характера, отвечающей интуитивному представлению об алгоритмах. С другой стороны, какие бы классы точно очерченных алгоритмов ни строились, во всех случаях неизменно оказывалось, что вычислимые посредством них числовые функции являлись частично рекурсивными. Поэтому общепринятой является научная гипотеза, формулируемая как тезис Черча: