Теорема о параметризации - Рекурсивные функции

Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать функцией от k (которая, как мы помним, называется степенной), функцией от x (показательной функцией), либо двуместной функцией от k и x. Переменные, входящие в выражение, но не объявленные явно в качестве аргументов определяемой функции в математике называют Параметрами этой функции.

Для явного разделения аргументов и параметров в математике обычно применяют т. н. - нотацию А. Черча, выписывая аргументы после символа ; по умолчанию, все остальные имена переменных, входящие в определение, - имена параметров определяемой функции. Так, например, k xK - степенная, а x xK - показательная функция.

Понятно, чтопараметрические определения определяют в реальности классы функций, полученных при разных значениях параметров (так, например, при разных значениях k мы получим различные показательные функции - 1K , 2K , 3K и т. д.)

В программировании схожий смысл имеют Глобальные переменные программы (процедуры) - это переменные, входящие в текст программы, но не определяемые явно в ней самой; при этом предполагается, что смысл таких переменных определяется внешним, по отношению к программе контекстом. Так, например, при определении FD-программ мы, вообще говоря, не предполагали, что значения входящих в программу переменных обязательно инициализированы вводом (оператором start) или оператором присваивания. Текст P такой программы мы можем рассматривать как параметрическое определение, задающие класс программ P(x1,x2,...,xN) в зависимости от конкретных значений параметров x1 ,x2 ,...,xN.

Пусть, для простоты, AnyProgram='start(x, y);Rest' - некоторая программа с двумя входными переменными x и y, с некоторым геделевым номером е, вычисляющая, соответственно некоторую двухместную функцию E(x, y). Пусть, далее, AssignX - программа, присваивающая некоторое значениепеременной x, AssignX='x:=O(x);x:=s(x);...x:=s(x)'. Очевидно, функция f1(x), выдающая по значению x код программы P2 - вычислима ( в нашей нумерации f1(x)=c1*I=1,x p(i)C2 , для некоторых констант с1,с2 - кодов операторов x:=O(x) и x:=s(x), соответственно).

Геделев номер программы P, P='start(y);AssignX;Rest' , которая имеет уже одну входную переменную y, - некоторая вычислимая функция s от аргументов e и x. По построению, для каждых значений e и x программа P, для каждого входа y, вычисляет то же значение, что и исходная программа AnyProgram. Такимобразом, мы доказывает важный и часто используемый в теории алгоритмов результат:

Похожие статьи




Теорема о параметризации - Рекурсивные функции

Предыдущая | Следующая