Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Операция минимизации (-ператор).
|
|
Пусть задана некоторая функция f(x, y}. Зафиксируем значение х и выясним, при каком у f(x, y) = 0.
Более сложной задачей является отыскание для данной функции f(x, у) и фиксированного х наименьшего из тех значений у, при которых функция f(x, у) = 0. Так как результат решения задачи зависит от x, то наименьшее значение у, при котором функция f(x, у) = 0 есть функция x. Принято обозначение
(Читается: «наименьшее у такое, что f(x, y) = 0 *.)
Аналогично определяется функция многих переменных:
(x1, x2, …., xn)= y[f(x, y)]
Переход от функции f (x1, x2, …xn, y) к функции
(x1, x2, …., xn) принято называть применением
-оператора.
Для вычисления функции можно предложить следующий алгоритм:
1. Вычислим f (x1, x2, …xn, 0) Если это значение f равно нулю, то полагаем (x1, x2, …., xn) = 0. Если f (x1, x2, …xn, 0) 0, то переходим к следующему шагу.
2. Вычислим f (x1, x2, …xn, 1) Если f (x1, x2, …xn, 0) 0,
то полагаем (x1, x2, …., xn) = 1. Если же f (x1, x2, …xn, 0) 0, то переходим к следующему шагу. И т.д.
Если окажется, что для всех у функция f (x1, x2, …xn, y) 0, то функцию (x1, x2, …., xn) в этом случае считают неопределенной. Но возможно, что существует такое у0, что f (x1, x2, …xn, y0) 0 и, значит, есть и наименьшее y, при котором f(x1, x2, …xn, y) = 0; и в то же время может случиться, что при некотором z(0 < z < у0) значение функции f (x1, x2, …xn, z) не определено. Очевидно, что в этом случае процесс вычисления наименьшего y, при котором f (x1, x2, …xn, y) = 0 не дойдет до у0. И здесь функцию (x1, x2, …., xn) считают неопределенной.
Пример. Рассмотрим функцию f(x, y) =x - у, которая может быть получена с помощью оператора минимизации
f(x, y)= z (x+y=x)= z[ 
+ 
= 
]
Вычислим, например, f(7, 2), то есть значение функции
при у = 2, х = 7. Для этого положим у = 2 и будем придавать х последовательно значения:
Z = 0, 2 + 0 = 2 7,
Z = 1, 2 + 1 = 3 7,
Z = 2, 2 + 2 = 4 7,
Z = 3, 2 + 3 = 5 7,
Z = 4, 2 + 4 = 6 7,
Z = 5, 2 + 5 = 7 = 7,
Таким образом, f(7, 2) = 5.
Определение 2. Функция f (x1, x2, …xn) называется частично рекурсивной, если она может быть получена в конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и -оператора.
Определение 3. Функция f (x1, x2, …xn) называется общерекурсивной, если она частично рекурсивна и всюду определена.
Примерами общерекурсивных функций являются функции:
1. (x)
2. (x)
3. 
4. f(x, y) = x + у
5. f(x, y) = x * у
6. f(x, y) = x + n
Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.
Этот тезис нельзя доказать, т.к. он связывает нестрогое математическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции.
Но этот тезис может быть опровергнут, если построить пример функции интуитивно вычислимой, но не являющейся частично рекурсивной.