Оператор построения по первому нулю

Этот оператор называют обычно оператором наименьшего числа, а в некоторых книгах — оператором минимизации; Этот оператор по за­данной функции, зависящей от n +1 аргументов, строит новую функцию от n аргументов. Исчезающий аргумент является вспомогательным и ис­пользуется при выполнении оператора. Обозначают оператор построения по первому нулю буквой μ, его применение обозначают строкой вида f:: = μ [ f₁;(x) ], где x — исчезающий аргумент. С помощью оператора построения по первому нулю получают функцию f, значения которой определяются при выполне­нии сопутствующего ей алгоритма, который гласит: «Придавать вспомога­тельному аргументу последовательные значения, начиная с 0, до тех пор, пока не окажется, что функция f стала (в первый раз) равной нулю. Полу­ченное значение вспомогательного аргумента принять за значение опреде­ляемой функции, соответствующее тем значениям основных аргументов, при которых осуществлялся описанный процесс».

Другими словами, пусть дана функция f(x₁,x₂,…,x_n). Выберем одну из переменных х_к и назовем её у. Получим f(x₁,x₂,…,x_k-1,y,x_k+1…,x_n)=f( x ,y).

Пусть задано уравнение f( x ,y) = 0. Найдем корень этого уравнения относительно у при фиксированном значении х. Возможны три ситуации:

1. Нет ни одного корня для натурального значения у,

2. Существует один корень при натуральному;

3. Существует более чем один корень при натуральному. По смыслу задачи нужно найти наименьший или первый корень. В первом случае это невозможно, следовательно, минимизация не определена. Для по­иска минимального корня используем следующий простой алгоритм.

1. выбираем y =0;

2. проверяем равны ли нулю значения функции f при заданном у. Если рав­ны, то у - первый корень и выходим из алгоритма. Если у≠ 0, то перехо­дим к следующему пункту;

3. увеличиваем у на единицу, у=у+ 1;

4. возвращаемся к пункту 2).

Если функция имеет конечный корень среди натуральных чисел, то алгоритм обязательно даст результат. Если корней несколько, то обязательно будет найден самый меньший среди натуральных корней. Пользуясь данным алго­ритмом поиска корня, можно построить функцию g(x₁,x₂,…,x_k-1,x_k+1…,x_n). Запишем алгоритм построения функции g.

1) фиксируем значение переменных x₁,x₂,…,x_n;

2) строим некую функцию f, к которой будет добавлена переменная х_к;

3) определяем, имеет ли относительно этой переменной функция/натураль­ный корень. Если корней нет, то при данных значениях функция g не оп­ределена. Если корни есть, то находим минимальный корень у. Этот ко­рень и есть искомое значение функции g, g=y.

Подобный алгоритм определяет некоторую функцию, которая при од­них значениях аргумента определена, а при других значениях не опреде­лена.

Функция, полученная по приведенному выше алгоритму, обозначается

g(x₁,x₂,…,x_k-1,x_k+1…,x_n)= μ [ f(x₁,x₂,…,x_k-1,x_k+1…,x_n);y ].

Построим μ [ f(x,y);y ] для f(x,y) = x-y+1. Очевидно, что данная функция равна нулю при

у = х- 1, следовательно g(x) = х -1, при этом функция g не определена при х=0. То есть, μ [ f(x,y) = х-у+ 1, у ] =х- 1.

Заметим, что базовые функции и функции, получаемые при помощи опе­раторов подстановки и рекурсии, но без применения оператора построения по первому нулю, определены (имеют значения) для любых значений аргументов. Иначе обстоит дело с функциями, полученными при помощи оператора построения по первому нулю. Для некоторых комбинаций значе­ний аргументов (даже для очень многих) они могут быть не определены, потому что исходная функция не принимает нулевых значений.

Для примера в качестве f₁ возьмем базовую функцию ψ_2,1(x,y).

f=μ [ ψ_2,1(x,y),(x) ]. Оператор для данной функции определен только в одной (.) x=0: ψ_2,1(0,y)=0.

f=μ [ ψ_2,1(x,y),(y) ], здесь ψ_2,1(x,0)=x.

Итак, рекурсивными называются базовые функции и любые функции, получаемые из них с помощью конечного числа операторов подстановки, рекурсии и построения по первому нулю. При этом функции, получаемые без использования оператора построения по первому нулю, называются примитивно рекурсивными. Это наиболее простые из рекурсивных функ­ций. Примитивно рекурсивные функции, вместе с теми рекурсивными функциями, которые невозможно получить, не прибегая к оператору по­строения по первому нулю, но которые определены для любых значений ар­гументов, называют общерекурсивными. Рекурсивные функции, которые определены не для всех возможных значений аргументов, называют час­тично рекурсивными. Построенная нами выше функция р(х) является час­тично рекурсивной.

Сформулируем правило минимизации.

Если функция получена с помощью минимизации рекурсивной функ­ции, то она частично рекурсивна, если функция получена с помощью оператора минимизации из частично рекурсивной функции, то она так же частично рекурсивна.

Можно доказать, что функция, полученная из частично рекурсивных функций с помощью операций суперпозиции и примитивной рекурсии яв­ляется частично рекурсивной.

Изучая рекурсивные и частично рекурсивные функции, можно сформу­лировать ещё один тезис.

Тезис Черча: Любая всюду определенная вычислимая числовая функ­ция является общерекурсивной. И, наоборот, если всюду определенная числовая функция не является общерекурсивной, то она невычислима.

Перенося тезис Черча на алгоритмы, сопутствующие рекурсивным функ­циям, мы можем высказать для них следующую гипотезу.

Основной тезис.

Каков бы ни был алгоритм, перерабатывающий наборы целых не­отрицательных чисел в целые неотрицательные числа, существует алгоритм, сопутствующий рекурсивной функции, который ему экви­валентен.

Тезис Клини: Любая вычислимая, но не всюду определенная числовая функция является частично рекурсивной. Если частично определенная чи­словая функция не является частично рекурсивной, то она невычислима.

Интересную форму этой гипотезе, вернее интересное ее обобщение, сделали советские ученые А. Н. Колмогоров и В. А. Успенский. Предполо­жим, что нам задан некоторый алгоритм в интуитивном смысле. На практи­ке всегда удается найти способ нумерации его допустимых исходных дан­ных, а также другой способ нумерации даваемых им результатов. Соответст­вие номеров исходных данных номерам результатов, устанавливаемое нашим алгоритмом (в интуитивном смысле), всегда совпадает с соответствием между значениями аргумента и значениями некоторой рекурсивной функ­ции от одного независимого переменного. Это значит, что выполнение ал­горитма в определенном смысле эквивалентно вычислению значения рекурсивной функции. Это значит, кроме того, что невозможность рекурсивной функции означает и невозможность алгоритма (так как для каждого алго­ритма должна быть рекурсивная функция, а ее-то в данном случае и нет).

Заметим, что тезис Черча и следующие из него остальные гипотезы не имеют доказательства и принципиально не могут быть доказаны, так как в них речь идет об алгоритмах в интуитивном смысле, не являющихся математическими объектами.

Дата добавления: 2015-07-11