Войти
В теории вычислимости, в мю-оператора, оператора минимизации или неограниченных операторов поиска поисках наименьшего натурального числа с заданным свойством. Добавление μ-оператора к пяти примитивным рекурсивным операторам позволяет определить все вычислимые функции.
Предположим, что R ( y, x 1,..., x k ) - фиксированное ( k +1) -арное отношение на натуральных числах. Μ-оператор «µ y », в неограниченной или ограниченной форме, является «теоретико-числовой функцией», определяемой от натуральных чисел к натуральным числам. Однако «μ y » содержит предикат над натуральными числами, который возвращает истину, когда предикат удовлетворен, и ложь, когда это не так.
Ограниченная μ-оператор появляется ранее в Клини (1952) Глава IX примитивно рекурсивных функций, §45 Предикаты, главный фактор - представление, как:
Стивен Клини отмечает, что любое из шести ограничений неравенства на диапазон переменной y разрешено, т. Е. Y lt; z, y ≤ z, w lt; y lt; z, w lt; y ≤ z, w ≤ y lt; z и w ≤ y ≤ z. «Когда указанный диапазон не содержит y, такого что R ( y ) [является« истинным »], значение выражения « μ y »является кардинальным числом диапазона» (стр. 226); вот почему в приведенном выше определении появляется значение по умолчанию " z ". Как показано ниже, ограниченный μ-оператор «μ y y lt; z » определяется в терминах двух примитивно рекурсивных функций, называемых конечной суммой Σ и конечным произведением Π, функции предиката, которая «выполняет проверку», и представляющей функции, которая преобразует {t, f} на { 0, 1 }.
В главе XI §57 Общие рекурсивные функции Клини определяет неограниченный μ-оператор над переменной y следующим образом:
В этом случае сам R или его представляющая функция выдает 0, когда он удовлетворен (т. Е. Выдает истину ); затем функция возвращает число y. Для y не существует верхней границы, поэтому в его определении не фигурируют выражения неравенства.
Для данного R ( y ) неограниченный μ-оператор μ y R ( y ) (обратите внимание на отсутствие требований для «(E y )») является частичной функцией. Вместо этого Клини делает это как общую функцию (см. Стр. 317):
Полная версия неограниченного μ-оператора изучается в обратной математике высшего порядка ( Kohlenbach (2005)) в следующей форме:
где верхние индексы означают, что n - нулевой порядок, f - первый порядок, а μ - второй порядок. Эта аксиома дает начало системе большой пятерки ACA 0 в сочетании с обычной базовой теорией обратной математики высшего порядка.
(i) В контексте примитивных рекурсивных функций, где переменная поиска y μ-оператора ограничена, например y lt; z в формуле ниже, если предикат R является примитивно рекурсивным (Доказательство Клини №E, стр. 228), тогда
(ii) В контексте (общих) рекурсивных функций, где переменная поиска y не ограничена, но гарантированно существует для всех значений x i параметров полного рекурсивного предиката R,
тогда пять примитивных рекурсивных операторов плюс неограниченный, но полный µ-оператор дают начало тому, что Клини назвал «общими» рекурсивными функциями (т. е. полными функциями, определяемыми шестью операторами рекурсии).
(iii) В контексте частично рекурсивных функций : предположим, что отношение R выполняется тогда и только тогда, когда частично рекурсивная функция сходится к нулю. И предположим, что эта частично рекурсивная функция сходится (к чему-то, не обязательно к нулю) всякий раз, когда определено μ y R ( y, x 1,..., x k ) и y равно μ y R ( y, x 1,..., x k ) или меньше. Тогда функция μ y R ( y, x 1,..., x k ) также является частично рекурсивной функцией.
Оператор μ используется для характеристики вычислимых функций как рекурсивных функций μ.
В конструктивной математике оператор неограниченного поиска связан с принципом Маркова.
Ограниченная μ-оператор может быть выражен, а просто в терминах двух примитивно рекурсивных функций (далее «пруф»), которые также используется для определения СЛУЧАЯ функции-продукт-из-терминов Π и сумма-из-терминов Σ (ср Kleene #B стр. 224). (При необходимости подходит любая граница для переменной, например s ≤ t или t lt; z, или 5 lt; x lt;17 и т. Д.). Например:
Прежде чем мы продолжим, нам нужно ввести функцию ψ, называемую « представляющей функцией » предиката R. Функция ψ определяется от входов (t = «истина», f = «ложь») до выходов (0, 1) ( обратите внимание на порядок ! ). В этом случае вход в ψ. т.е. {t, f}. исходит из вывода R:
Клини показывает, что μ y y lt; z R ( y ) определяется следующим образом; мы видим, что функция произведения Π действует как логический оператор ИЛИ, а сумма Σ действует как логическое И, но производит {Σ ≠ 0, Σ = 0}, а не просто {1, 0}:
Уравнение проще, если рассмотреть его на примере, приведенном Клини. Он только что сделал записи для представляющей функции ψ (R ( y )). Он обозначил представляющие функции χ ( y ), а не ψ ( x, y ):
| y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 = г |
|---|---|---|---|---|---|---|---|---|
| χ ( у ) | 1 | 1 | 1 | 0 | 1 | 0 | 0 | |
| π ( y ) = Π s ≤ y χ ( s ) | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| σ ( y ) = Σ t lt; y π ( t ) | 1 | 2 | 3 | 3 | 3 | 3 | 3 | 3 |
| наименьшее y lt; z такое, что R ( y ) "истинно": φ ( y ) = μ y y lt; z R ( y ) | 3 |
Неограниченный μ-оператор - функция μ y - обычно определяется в текстах. Но читатель может задаться вопросом, почему неограниченный μ-оператор ищет функцию R ( x, y ), чтобы получить ноль, а не какое-то другое натуральное число.
Причина для нуля состоит в том, что неограниченный оператор μ y будет определен в терминах функции «продукт» Π, индекс y которой может «расти» по мере поиска μ-оператором. Как отмечено в приведенном выше примере, произведение Π x lt; y строки чисел ψ ( x, 0) *,..., * ψ ( x, y ) дает ноль всякий раз, когда один из его членов ψ ( x, i ) равно нулю:
если любой ψ ( x, i ) = 0, где 0≤ i ≤ s. Таким образом, Π действует как логическое И.
Функция μ y производит на «выходе» единственное натуральное число y = {0, 1, 2, 3,...}. Однако внутри оператора может появиться одна из пары «ситуаций»: (а) «теоретико-числовая функция» χ, которая производит одно натуральное число, или (б) «предикат» R, который дает либо {t = true, f = false}. (И в контексте частично рекурсивных функций Клини позже допускает третий результат: «μ = не определился».)
Клини разделяет свое определение неограниченного μ-оператора на две ситуации (a) и (b). Для ситуации (b), прежде чем предикат R ( x, y ) сможет служить в качестве арифметической в продукте Π, его выход {t, f} должен сначала "обработаться" его представляющей функцией χ, чтобы получить {0, 1}. А для ситуации (а), если нужно использовать одно определение, то теоретико-числовая функция χ должна давать ноль, чтобы «удовлетворить» µ-оператор. Урегулировав этот вопрос, он демонстрирует с помощью единственного «Доказательства III», что типы (a) или (b) вместе с пятью примитивными рекурсивными операторами дают (полные) рекурсивные функции с этим условием для полной функции :
Клини также допускает третью ситуацию (с), которая не требует демонстрации «для всех х у существует такое, что ф ( х, у ).» Он использует это в своем доказательстве того, что существует больше полных рекурсивных функций, чем можно перечислить ; cf сноска Общая демонстрация функций.
Доказательство Клини носит неформальный характер и использует пример, аналогичный первому, но сначала он приводит μ-оператор в другую форму, которая использует «произведение терминов» Π, действующее на функцию χ, которая дает натуральное число n, которое может - любое натуральное число и 0 в том случае, если проверка u-оператора "выполнена".
Это тонко. На первый взгляд кажется, что в уравнениях используется примитивная рекурсия. Но Клини не дал нам базового шага и шага индукции общего вида:
Чтобы увидеть, что происходит, мы сначала должны напомнить себе, что мы присвоили параметр (натуральное число) каждой переменной x i. Во-вторых, мы действительно видим, как работает оператор-преемник, повторяющий y (то есть y ' ). И, в-третьих, мы видим, что функция μ y y lt; z χ ( y, x ) просто порождает экземпляры χ ( y, x ), т.е. χ (0, x ), χ (1, x ),... до тех пор, пока экземпляр дает 0. В-четвертых, когда экземпляр χ ( n, x ) дает 0, средний член τ, то есть v = π ( x, y ' ), дает 0. Наконец, когда средний член v = 0, μ y y lt; z χ ( y ) выполняет строку (iii) и «выходит». Представление Клини уравнений (ii) и (iii) было изменено, чтобы показать, что линия (iii) представляет выход - выход осуществляется только тогда, когда поиск успешно находит y, удовлетворяющий χ ( y ), и средний продукт-член π ( x, y ' ) равно 0; затем оператор прекращает поиск с τ ( z ', 0, y ) = y.
Для примера Клини «... рассмотрим [s] любых фиксированных значений ( x i,..., x n ) и напишем [s] просто 'χ ( y )' вместо 'χ ( x i,..., x n ), y ) '":
| y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | и Т. Д. |
|---|---|---|---|---|---|---|---|---|---|
| χ ( у ) | 3 | 1 | 2 | 0 | 9 | 0 | 1 | 5 | ... |
| π ( y ) = Π s ≤ y χ ( s ) | 1 | 3 | 3 | 6 | 0 | 0 | 0 | 0 | ... |
| ↑ | |||||||||
| наименьшее y lt; z такое, что R ( y ) "истинно": φ ( y ) = μ y y lt; z R ( y ) | 3 |
Оба Минского (1967) с. 21 и Булос-Берджесс-Джеффри (2002) стр. 60-61 дают определения μ-оператора как абстрактной машины; см. сноску Альтернативные определения μ.
Следующая демонстрация следует за Минским без «особенности», упомянутой в сноске. Демонстрация будет использовать модель «преемника» счетной машины, тесно связанную с аксиомами Пеано и примитивными рекурсивными функциями. Модель состоит из (i) конечного автомата с ТАБЛИЦЕЙ инструкций и так называемого «регистра состояний», который мы переименуем в «Регистр инструкций» (IR), (ii) нескольких «регистров», каждый из которых может содержат только одно натуральное число и (iii) набор инструкций из четырех «команд», описанных в следующей таблице:
| Инструкция | Мнемонический | Действие в регистре (ах) "r" | Действие по реестру инструкций, IR |
|---|---|---|---|
| Регистр CLeaR | CLR (r) | 0 → г | [ИК] + 1 → ИК |
| Регистр INCrement | INC (r) | [г] + 1 → г | [ИК] + 1 → ИК |
| Перейти, если равно | JE (r 1, r 2, z) | никто | ЕСЛИ [r 1 ] = [r 2 ] ТО z → IR ELSE [IR] + 1 → IR |
| Остановка | ЧАС | никто | [ИК] → ИК |
Алгоритм для оператора минимизации μ y [φ ( x, y )], по сути, будет создавать последовательность экземпляров функции φ ( x, y ) по мере увеличения значения параметра y (натуральное число); процесс будет продолжаться (см. примечание † ниже) до тех пор, пока не произойдет совпадение между выходом функции φ ( x, y ) и некоторым заранее установленным числом (обычно 0). Таким образом, вычисление φ ( x, y ) требует вначале присвоения натурального числа каждой из его переменных x и присвоения "числа совпадений" (обычно 0) регистру " w ", а число (обычно 0) для регистрации y.
Далее мы предполагаем, что регистр инструкций (IR) встречает «подпрограмму» μ y с номером инструкции « n ». Его первым действием будет установка числа в специальный регистр « w » - «пример» числа, которое функция φ ( x, y ) должна произвести, прежде чем алгоритм сможет завершить работу (классически это число ноль, но см. сноска об использовании чисел, отличных от нуля). Следующим действием алгоритма по команде « n +1» будет очистка регистра « y » - « y » будет действовать как «повышающий счетчик», который начинается с 0. Затем по команде « n +2» алгоритм вычисляет его функция φ ( x, y ) - мы предполагаем, что это требует j инструкций для выполнения - и в конце ее вычисления φ ( x, y) помещает свой вывод в регистр "φ". В инструкции ( n + j +3) rd алгоритм сравнивает число в регистре " w " (например, 0) с числом в регистре "φ" - если они совпадают, алгоритм завершился успешно и уходит через exit ; в противном случае это увеличивает содержимое « у » зарегистрировать и петлю назад с этим новым у-значением для пробной функции ф ( х, у ) снова.
| ИК | Инструкция | Действие по регистрации | Действие по регистру инструкций IR | |
|---|---|---|---|---|
| п | μ y [φ ( x, y )]: | CLR (w) | 0 → ш | [ИК] + 1 → ИК |
| п +1 | CLR ( г ) | 0 → y | [ИК] + 1 → ИК | |
| п +2 | петля: | ф ( х, у ) | φ ([ x ], [ y ]) → φ | [ИК] + j + 1 → ИК |
| п + j +3 | JE (φ, w, выход) | никто | СЛУЧАЙ: {IF [φ] = [ w ] THEN выход → IR ELSE [IR] + 1 → IR} | |
| п + j +4 | INC ( г ) | [ y ] + 1 → y | [ИК] + 1 → ИК | |
| п + j +5 | JE (0, 0, цикл) | Безусловный прыжок | СЛУЧАЙ: {IF [r 0 ] = [r 0 ] THEN цикл → IR ELSE цикл → IR} | |
| п + j +6 | выход: | и Т. Д. |
Что является обязательным, если функция должна быть полной функцией, - это демонстрация каким-либо другим методом (например, индукцией ), что для каждой без исключения комбинации значений ее параметров x i некоторое натуральное число y будет удовлетворять μ-оператору, так что алгоритм что означает, что расчет может завершиться:
Пример того, что это означает на практике, см. В примерах рекурсивных функций mu - даже простейший алгоритм усеченного вычитания « x - y = d » может дать в неопределенных случаях, когда x lt; y, (1) без завершения, (2) без чисел (т.е. что-то не так с форматом, поэтому доходность не считается натуральным числом) или (3) обман: неправильные числа в правильном формате. «Правильный» алгоритм вычитания требует внимательного отношения ко всем «случаям».
Но даже когда было показано, что алгоритм дает ожидаемый результат в экземплярах {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, мы остались с неприятным чувством, пока мы не можем изобрести «убедительное доказательство», что случаи ( х, у ) = ( п, т ) все дали ожидаемые результаты. На точку зрения Клини: достаточно ли убедительна наша «демонстрация» (то есть алгоритм, который является нашей демонстрацией), чтобы считаться эффективной ?
Неограниченный μ-оператор определен Минским (1967), с. 210, но со специфическим недостатком: оператор не даст t = 0, если его предикат (тест IF-THEN-ELSE) удовлетворен; скорее это дает t = 2. В версии Минского счетчик - « t », а функция φ ( t, x ) помещает его номер в регистр φ. В обычном регистре определения μ регистр w будет содержать 0, но Мински отмечает, что он может содержать любое число k. Набор инструкций Мински эквивалентен следующему, где "JNE" = Перейти к z, если не равно:
| ИК | Инструкция | Действие по регистрации | Действие по реестру инструкций, IR | |
|---|---|---|---|---|
| п | μ y φ ( x ): | CLR ( w ) | 0 → ш | [ИК] + 1 → ИК |
| п + 1 | CLR ( т ) | 0 → т | [ИК] + 1 → ИК | |
| п +2 | петля: | ф ( у, х ) | φ ([ t ], [ x ]) → φ | [ИК] + j + 1 → ИК |
| п + j +3 | INC ( т ) | [ t ] + 1 → t | [ИК] + 1 → ИК | |
| п + j +4 | JNE (φ, w, цикл) | никто | СЛУЧАЙ: {ЕСЛИ [φ] ≠ [ w ] ТО "выход" → IR ELSE [IR] + 1 → IR} | |
| п + j +5 | INC ( т ) | [ t ] + 1 → t | [ИК] + 1 → ИК | |
| п + j +6 | выход: | и Т. Д. |
Неограниченный μ-оператор также определен Булосом-Берджессом-Джеффри (2002) с. 60-61 для счетчика с набором команд, эквивалентным следующему:
В этой версии счетчик «y» называется «r2», а функция f ( x, r2) помещает его номер в регистр «r3». Возможно, причина, по которой Булос-Берджесс-Джеффри очищает r3, заключается в том, чтобы облегчить безусловный переход в петлю ; это часто делается с помощью специального регистра «0», который содержит «0»:
| ИК | Инструкция | Действие по регистрации | Действие по реестру инструкций, IR | |
|---|---|---|---|---|
| п | μ r 2 [f ( x, r 2 )]: | CLR ( r 2 ) | 0 → r 2 | [ИК] + 1 → ИК |
| п +1 | петля: | f ( y, x ) | f ([ t ], [ x ]) → r 3 | [ИК] + j + 1 → ИК |
| п +2 | JZ ( r 3, выход) | никто | IF [ r 3 ] = 0 THEN выход → IR ELSE [IR] + 1 → IR | |
| п + j +3 | CLR ( r 3 ) | 0 → r 3 | [ИК] + 1 → ИК | |
| п + j +4 | INC ( r 2 ) | [ r 2 ] + 1 → r 2 | [ИК] + 1 → ИК | |
| п + j +5 | JZ ( r 3, петля) | СЛУЧАЙ: {IF [ r 3 ] = 0 THEN loop → IR ELSE [IR] + 1 → IR} | ||
| п + j +6 | выход: | и Т. Д. |
