Теорема о параметризации - Рекурсивные функции
Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение 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. Такимобразом, мы доказывает важный и часто используемый в теории алгоритмов результат:
Похожие статьи
-
Теорема об универсальной функции - Рекурсивные функции
Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...
-
Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции
Если А - эффективное множество, то Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn...
-
Теорема о параметризации., Универсальные функции - Рекурсивные функции
Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст...
-
Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...
-
Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции
Вместо предисловия . Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и...
-
Синтаксис и семантика. Теорема Райса - Рекурсивные функции
Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....
-
Перечислимость. - Рекурсивные функции
В предыдущем упражнении мы показали, что операции алгебры логики не выводят за пределы разрешимых предикатов. Но полный язык математической логики, как...
-
Ответ: y=f(kx) получается из Графика функции f(x) сжатием его вдоль оси ох в k раз, если k>1 и растяжением в 1 деленную на k раз, если k>0 но меньше 1....
-
Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций
Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....
-
ФУНКЦИИ, Основные понятия - Свойства функций
Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...
-
Теорема Клини о нормальной форме - Рекурсивные функции
Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e,...
-
Неразрешимость - методы доказательства, Диагонализация - Рекурсивные функции
Основными методами при доказательстве теорем о не существовании алгоритмовявляются - прямой метод Диагонализации, восходящий к "диагональному"...
-
Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...
-
Неразрешимость - Рекурсивные функции
Сейчас же займемся более важной задачей - определением принципиальных границ вычислимости. Если теоремы о параметризации, универсальнойфункциии...
-
Кодирование программ - Рекурсивные функции
(Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...
-
Сложение, вычитание, умножение комплексных чисел в алгебраической форме производят по правилам соответствующих действий над многочленами. Четность и...
-
Сводимость - Рекурсивные функции
Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде...
-
Выбор математической формы функции при моделировании зависимости выпуска продукции от производственных факторов Постановка проблемы. Одним из важнейших...
-
Пусть u = f(x, y) - функция, определенная в области w. Рассмотрим точку М(х, у) О w и некоторое направление l, определяемое направляющими косинусами Cosa...
-
Q(x) - соответствует площади боковой поверхности данного тела от точки А до точки х. Q(x)>х€[a, x]. Q (x+?x)>х€[a, x+?x], тогда ?Q=Q...
-
Уравнение динамики теплообменника: Передаточные функции объекта получим по его уравнению динамики. Для этого запишем уравнение по заданному каналу. Затем...
-
Односторонние пределы, Пределы на бесконечности - Свойства функций
В определении предела функции предполагалось, что произвольным образом. Если при вычислении предела функции при считать, что, то получают Односторонний...
-
Теоремы Ферма, Ролля, Лагранжа и Коши
Введение В данном реферате рассматриваются теоремы Ферма, Ролля, Лагранжа и Коши. "Теорема - высказывание, нравственность которого установлена при помощи...
-
Методы построения функций принадлежности нечетких множеств - Нечеткая логика
В приведенных выше примерах использованы прямые методы, когда эксперт или просто задает для любого x?E значение ?A(x), или определяет функцию...
-
ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...
-
Ответ: 2) 3) 4) Знаки значений тригонометрических функций Ответ: Sin cos tg*ctg Таблица значений Ответ: Формулы сложения Ответ1 Формулы двойного...
-
Пусть Dl, r() соответственно левые (правые) границы интервалов I, отвечающих на криволинейной трапеции ОИО значениям 0< < 1. Тогда интересующая нас...
-
Ответ: Функция f называется четной если для любого х из ее области определения f(-x)=f(x) График четной функции симметричен относительно оси ординат....
-
Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...
-
Интегральная и дифференциальная функции распределения - Основы научных исследований
Наиболее общей формой задания распределения случайных величин является Интегральная функция распределения . Она определяет вероятность того, что...
-
Ответ: Функция f ставит в соответствие числу х число у, а функция g числу у число z. Говорят что h есть сложная функция составленная из функций g и f, и...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
Теорема Пенлеве - Условия Фукса и теорема Пенлеве
Все приведенные выше исследования велись в предположении, что мы изучаем поведение интеграла в области изменения z, при котором w(z) принимает вполне...
-
Аппроксимация функции предпочтения ЛПР нейронными сетями имеет в работе ту особенность, что процесс обучения нейронных сетей происходит в условиях малой...
-
Пусть - вектор параметров задачи (вектор варьируемых параметров), где - n-мерное арифметическое пространство (пространство параметров). Множеством...
-
ОБОСНОВАНИЕ ВИДА И РАСЧЕТ ПАРАМЕТРОВ АНАЛИТИЧЕСКОЙ ФУНКЦИИ - Основы прогнозирования
На практике при выборе аналитической функции рекомендуется подбирать функцию с таким расчетом, чтобы ее конструктивные элементы, коэффициенты и константы...
-
Пусть функция определена в промежутке Х (рис.1). Исходя из некоторого значения независимой переменной, придадим ему приращение, не выводящее его из...
-
Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...
-
Для того, чтобы узнать, на сколько максимум может увеличится ВРП Краснодарского края, не хватает оптимального значения капитала. Для этого построим...
Теорема о параметризации - Рекурсивные функции