Вычислимые функции. Частично рекурсивные и общерекурсивные функции 9po-32k Смирнов Кирилл

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

Определение Определение 1. Функция g = f(x 1, x 2,..., х п ) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения. Так как в этом определении алгоритм понимается в интуитивном смысле, то и понятие эффективно вычислимой функции является интуитивным. Однако переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что те требования, которые предъявляются к алгоритму в его характерных чертах, выполняются для совокупности всех вычислимых функций, которая носит название совокупности рекурсивных функций. Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определяемых в некоторой формальной системе. Черч в 1936 году пришел к тому же классу функций, исходя из других предпосылок. Здесь построение класса вычислимых функций строится следующим образом.

Суперпозиция функций

Суперпозиция функций.