§ 4. Вычислимые функции. Частично рекурсивные и общерекурсивные функции
Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров x1, х2, ..., хп, а искомым результатом также является целое число у. Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции у, зависящей от целочисленных значений аргументов x1, х2, ..., хп.
Определение 1. Функция g = f(x1, x2,..., хп) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.
Так как в этом определении алгоритм понимается в интуитивном смысле, то и понятие эффективно вычислимой функции является интуитивным.
Однако переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что те требования, которые предъявляются к алгоритму в его характерных чертах, выполняются для совокупности всех вычислимых функций, которая носит название совокупности рекурсивных функций.
Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определяемых в некоторой формальной системе. Черч в 1936 году пришел к тому же классу функций, исходя из других предпосылок. Здесь построение класса вычислимых функций строится следующим образом.
Выбираются простейшие функции
(оператор сдвига),
О(х) = 0 (оператор аннулирования),
(оператор проектирования).
Ясно, что все три простейшие функции всюду определены и интуитивно вычислимы.
Далее вводятся операции над функциями.
1. Суперпозиция функций.
Рассмотрим функции и функцию , функцию , определяемую равенством
.
Будем говорить, что функция получена из функций и f1, f2, ..., fm суперпозицией.
Если мы каким-либо образом умеем вычислять функции f1, f2, ..., fm , то функция может быть вычислена так: придадим переменным xv х2, ..., хп некоторые значения a1, а2, ..., ап. Вычисляя все , найдем . Вычисляя теперь найдем .
Ясно, что если все функции fl, f2, ..., fm и всюду определены, то функция всюду определена. Функция будет не всюду определенной, если хотя бы одна из функций fl, f2, ..., fm не всюду определена, или если можно найти такие значения аргументов а1, а2, ..., аn, что bi=fi(a1,a2,...,an), но (b1,b2,.,.,bm) не определено (i = 1,…, т).
Таким образом, если функции fl, f2, ..., fm, интуитивно вычислимы, то будет интуитивно вычислима и функция .
Отметим, что возможны случаи, когда не все функции f1, f2, ..., fm зависят от всех п аргументов х1, x2, ..., хп. В этих случаях для получения суперпозиции используются фиктивные аргументы и функции . Например, функция получается суперпозицией из функций и
.
Do'stlaringiz bilan baham: |