μ оператор

В теории вычислимости , в мю-оператора , оператора минимизации или неограниченных операторов поиска поисках наименьшего натурального числа с заданным свойством. Добавление μ-оператора к пяти примитивным рекурсивным операторам позволяет определить все вычислимые функции .

Определение [ править ]

Предположим, что R ( y , x ₁ , ..., x _k ) - фиксированное ( k +1) -арное отношение на натуральных числах . Μ-оператор «µ y », в неограниченной или ограниченной форме, является «теоретико-числовой функцией», определяемой от натуральных чисел к натуральным числам. Однако «μ y » содержит предикат над натуральными числами, который возвращает истину, когда предикат удовлетворен, и ложь, когда это не так.

Ограниченная μ-оператор появляется ранее в Клини (1952) Глава IX примитивно рекурсивных функций, §45 Предикаты, главный фактор - представление , как:

« » (стр. 225)${\ displaystyle \ mu y_ {y <z} R (y). \ \ {\ mbox {Наименьшее}} \ y <z \ {\ mbox {такое, что}} \ R (y), \ {\ mbox { if}} \ (\ exists y) _ {y <z} R (y); \ {\ mbox {else}}, \ z.}$

Стивен Клини отмечает, что любое из шести ограничений неравенства на диапазон переменной y разрешено, то есть y < z , y ≤ z , w < y < z , w < y ≤ z , w ≤ y < z и w ≤ y ≤ z . "Когда указанный диапазон не содержит y, такого что R ( y ) [является" истинным "], значение" μ y "«выражение - это кардинальное число диапазона» (стр. 226); вот почему в приведенном выше определении появляется значение по умолчанию " z ". Как показано ниже, ограниченный μ-оператор «μ y _{y < z} » определяется в терминах двух примитивных рекурсивных функций, называемых конечной суммой Σ и конечным произведением Π, функции-предиката, которая «выполняет проверку», и представляющей функции, которая преобразует от {t, f} до { 0 , 1 }.

В главе XI §57 Общие рекурсивные функции Клини определяет неограниченный μ-оператор над переменной y следующим образом:

" " (стр. 279, где " " означает "существует y такое, что ...")${\ displaystyle (\ существует y) \ mu yR (y) = \ {{\ mbox {наименьшее (натуральное число)}} \ y \ {\ mbox {такое, что}} \ R (y) \}}$${\displaystyle (\exists y)}$

В этом случае сам R или его представляющая функция выдает 0, когда он удовлетворен (т. Е. Выдает истину ); функция затем возвращает число y . Для y не существует верхней границы , поэтому в его определении не фигурируют выражения неравенства.

Для данного R ( y ) неограниченный μ-оператор μ y R ( y ) (обратите внимание на отсутствие требования для «(E y )») является частичной функцией . Клини делает это как полную функцию (см. Стр. 317):

${\displaystyle \varepsilon yR(x,y)={\begin{cases}{\text{the least }}y{\text{ such that }}R(x,y),&{\text{if }}(Ey)R(x,y)\\0,&{\text{otherwise}}.\end{cases}}}$

Полная версия неограниченного μ-оператора изучается в обратной математике высшего порядка ( Kohlenbach (2005) ) в следующей форме:

${\displaystyle (\exists \mu ^{2})(\forall f^{1}){\big (}(\exists n^{0})(f(n)=0)\rightarrow f(\mu (f))=0{\big )},}$

где верхние индексы означают, что n - нулевой порядок, f - первый порядок, а μ - второй порядок. Эта аксиома дает начало системе большой пятерки ACA _{0 в} сочетании с обычной базовой теорией обратной математики высшего порядка.

Свойства [ править ]

(i) В контексте примитивных рекурсивных функций , где переменная поиска y μ-оператора ограничена, например y < z в формуле ниже, если предикат R является примитивно рекурсивным (Доказательство Клини №E, стр. 228), тогда

μ y _{y < z} R ( y , x ₁ , ..., x _n ) - примитивно рекурсивная функция.

(ii) В контексте (общих) рекурсивных функций , где переменная поиска y не ограничена, но гарантированно существует для всех значений x _i параметров полного рекурсивного предиката R,

( x ₁ ), ..., ( x _n ) (Ey) R ( y , x _i , ..., x _n ) влечет, что μ y R ( y , x _i , ..., x _n ) является полная рекурсивная функция .

Здесь ( x _i ) означает «для всех x _i », а E y означает «существует по крайней мере одно значение y такое, что ...» (см. Kleene (1952), стр. 279.)

тогда пять примитивных рекурсивных операторов плюс неограниченный, но полный µ-оператор дают начало тому, что Клини назвал «общими» рекурсивными функциями (т. е. полными функциями, определяемыми шестью операторами рекурсии).

(iii) В контексте частично рекурсивных функций : предположим, что отношение R выполняется тогда и только тогда, когда частично рекурсивная функция сходится к нулю. И предположим, что эта частично рекурсивная функция сходится (к чему-то, не обязательно к нулю) всякий раз, когда определено μ y R ( y , x ₁ , ..., x _k ) и y равно μ y R ( y , x ₁ , ... , x _k ) или меньше. Тогда функция μ y R ( y , x ₁ , ..., x _k) также является частично рекурсивной функцией.

Оператор μ используется для характеристики вычислимых функций как рекурсивных функций μ .

В конструктивной математике оператор неограниченного поиска связан с принципом Маркова .

Примеры [ править ]

Пример 1. Ограниченный μ-оператор - это примитивная рекурсивная функция [ править ]

Далее x представляет собой строку x _i , ..., x _n .

Ограниченная μ-оператор может быть выражен , а просто в терминах двух примитивно рекурсивных функций (далее «пруф») , которые также используется для определения СЛУЧАЯ функции-продукт-из-терминов Π и сумма-из-терминов Σ (ср Kleene #B стр. 224). (При необходимости подходит любая граница для переменной, например s ≤ t или t < z , или 5 < x <17 и т. Д.). Например:

• Π _{s ≤ t} f _s ( x , s ) = f ₀ ( x , 0) × f ₁ ( x , 1) × ... × f _t ( x , t )
• Σ _{t < z} g _t ( x , t ) = g ₀ ( x , 0) + g ₁ ( x , 1) + ... + g _z-1 ( x , z -1)

Прежде чем продолжить, нам нужно ввести функцию ψ, называемую « представляющей функцией » предиката R. Функция ψ определяется от входов (t = «истина», f = «ложь») до выходов (0, 1) ( обратите внимание на порядок ! ). В этом случае вход в ψ. т.е. {t, f}. исходит из вывода R:

• ψ (R = t) = 0
• ψ (R = f) = 1

Клини показывает, что μ y _{y < z} R ( y ) определяется следующим образом; мы видим, что функция произведения Π действует как логический оператор ИЛИ, а сумма Σ действует как логическое И, но производит {Σ ≠ 0, Σ = 0}, а не просто {1, 0}:

μ y _{y < z} R ( y ) = Σ _{t < z} Π _{s ≤ t} ψ (R ( x , t , s )) =

[ψ ( x , 0, 0)] +

[ψ ( x , 1, 0) × ψ ( x , 1, 1)] +

[ψ ( x , 2, 0) × ψ ( x , 2, 1) × ψ ( x , 2, 2)] +

... +

[ψ ( x , z -1, 0) × ψ ( x , z -1, 1) × ψ ( x , z -1, 2) ×. . . × ψ ( x , z -1, z -1)]

Обратите внимание, что Σ на самом деле является примитивной рекурсией с базой Σ ( x , 0) = 0 и шагом индукции Σ ( x , y +1) = Σ ( x , y ) + Π ( x , y ). Произведение Π также является примитивной рекурсией с базовым шагом Π ( x , 0) = ψ ( x , 0) и шагом индукции Π ( x , y +1) = Π ( x , y ) × ψ ( x , y +1). ) .

Уравнение проще, если рассмотреть его на примере, приведенном Клини. Он просто сделал записи для представляющей функции ψ (R ( y )). Он обозначил представляющие функции χ ( y ), а не ψ ( x , y ):

Пример 2: неограниченный μ-оператор не является примитивно-рекурсивным [ править ]

Неограниченный μ-оператор - функция μ y - обычно определяется в текстах. Но читатель может задаться вопросом, почему неограниченный μ-оператор ищет функцию R ( x , y ), чтобы дать ноль , а не какое-то другое натуральное число.

В сноске Мински разрешает своему оператору завершить работу, когда внутренняя функция производит совпадение с параметром « k »; этот пример также полезен, потому что он показывает формат другого автора:

«Для μ _t [φ ( t ) = k ]» (стр. 210)

Причина для нуля заключается в том, что неограниченный оператор μ y будет определен в терминах функции «продукт» Π, индекс y которой может «расти» по мере поиска μ-оператором. Как отмечалось в приведенном выше примере, произведение Π _{x < y} строки чисел ψ ( x , 0) *, ..., * ψ ( x , y ) дает ноль всякий раз, когда один из его членов ψ ( x , i ) равно нулю:

Π _{s < y} = ψ ( x , 0) *, ..., * ψ ( x , y ) = 0

если любой ψ ( x , i ) = 0, где 0≤ i ≤ s . Таким образом, Π действует как логическое И.

Функция μ y производит на «выходе» единственное натуральное число y = {0, 1, 2, 3, ...}. Однако внутри оператора может появиться одна из пары «ситуаций»: (а) «теоретико-числовая функция» χ, производящая единственное натуральное число, или (б) «предикат» R, производящий либо {t = true, f = false}. (И в контексте частично рекурсивных функций Клини позже допускает третий результат: «μ = не определился». ^[1] )

Клини разделяет свое определение неограниченного μ-оператора на две ситуации (a) и (b). Для ситуации (b), прежде чем предикат R ( x , y ) сможет служить арифметической емкостью в продукте, его выход {t, f} должен сначала "обработаться" его представляющей функцией χ, чтобы получить {0, 1}. А для ситуации (а), если нужно использовать одно определение, то теоретико-числовая функция χ должна давать ноль, чтобы «удовлетворить» µ-оператор. Решив этот вопрос, он демонстрирует с помощью единственного «Доказательства III», что типы (a) или (b) вместе с пятью примитивными рекурсивными операторами дают (полные) рекурсивные функции с этим условием для полной функции :

Для всех параметров х , должна быть предоставлена демонстрация , чтобы показать , что у существует, удовлетворяющие условия (а) μ у ψ ( х , у ) или (б) М у R ( х , у ).

Клини также допускает третью ситуацию (с) , которая не требует демонстрации «для всех х у существует такое , что ф ( х , у ).» Он использует это в своем доказательстве того, что существует больше полных рекурсивных функций, чем можно перечислить ; cf сноска Общая демонстрация функций .

Доказательство Клини носит неформальный характер и использует пример, аналогичный первому, но сначала он приводит μ-оператор в другую форму, которая использует «произведение терминов» Π, действующее на функцию χ, которая дает натуральное число n , которое может - любое натуральное число и 0 в том случае, если проверка u-оператора "выполнена".

Определение переделано с помощью Π-функции:

μ y _{y < z} χ ( y ) =

• (i): π ( x , y ) = _{s < y} χ ( x , s )
• (ii): φ ( x ) = τ (π ( x , y ), π ( x , y ' ), y )
• (iii): τ ( z ' , 0, y ) = y ; τ ( u , v , w ) не определено при u = 0 или v > 0.

Это тонко. На первый взгляд кажется, что в уравнениях используется примитивная рекурсия. Но Клини не дал нам базового шага и шага индукции общего вида:

• базовый шаг: φ (0, x ) = φ ( x )
• шаг индукции: φ (0, x ) = ψ (y, φ (0, x ), x )

Чтобы увидеть, что происходит, мы сначала должны напомнить себе, что мы присвоили параметр (натуральное число) каждой переменной x _i . Во-вторых, мы действительно видим, как работает оператор-преемник, повторяющий y (то есть y ' ). И, в-третьих, мы видим, что функция μ y _{y < z} χ ( y , x ) просто порождает экземпляры χ ( y , x ), т.е. χ (0, x ), χ (1, x ), ... до тех пор, пока экземпляр дает 0. В-четвертых, когда экземпляр χ ( n , x ) дает 0, он вызывает средний член τ, то есть v = π ( x , y '), чтобы получить 0. Наконец, когда средний член v = 0, μ y _{y < z} χ ( y ) выполняет строку (iii) и «завершается». Представление Клини уравнений (ii) и (iii) было изменено, чтобы показать, что линия (iii) представляет собой выход - выход осуществляется только тогда, когда поиск успешно находит y, удовлетворяющий χ ( y ), и средний продукт-член π ( x , y ' ) равно 0; затем оператор прекращает поиск с τ ( z ' , 0, y ) = y .

τ (π ( x , y ), π ( x , y ' ), y ), то есть:

• τ (π ( x , 0), π ( x , 1), 0),
• τ (π ( x , 1), π ( x , 2), 1)
• τ (π ( x , 2), π ( x , 3), 2)
• τ (π ( x , 3), π ( x , 4), 3)
• ... пока совпадение не произойдет при y = n, а затем:
• τ ( z ' , 0, y ) = τ ( z' , 0, n ) = n и поиск μ-оператора завершен.

Для примера Клини «... рассмотрим [s] любых фиксированных значений ( x _i , ..., x _n ) и напишем [s] просто 'χ ( y )' вместо 'χ ( x _i , ..., x _n ), y ) '":

Пример 3: Определение неограниченного μ-оператора в терминах абстрактной машины [ править ]

Оба Минского (1967) с. 21 и Булос-Берджесс-Джеффри (2002) стр. 60-61 дают определения μ-оператора как абстрактной машины; см. сноску Альтернативные определения μ .

Следующая демонстрация следует за Минским без «особенности», упомянутой в сноске. Демонстрация будет использовать модель «преемника» счетной машины, тесно связанную с аксиомами Пеано и примитивными рекурсивными функциями . Модель состоит из (i) конечного автомата с ТАБЛИЦЕЙ инструкций и так называемого «регистра состояний», который мы переименуем в «Регистр инструкций» (IR), (ii) нескольких «регистров», каждый из которых может содержат только одно натуральное число и (iii) набор инструкций из четырех «команд», описанных в следующей таблице:

Далее символ «[r]» означает «содержимое», а «→ r» указывает действие по отношению к регистру r.

Алгоритм для оператора минимизации μ y [φ ( x , y )], по сути, будет создавать последовательность экземпляров функции φ ( x , y ) по мере увеличения значения параметра y (натуральное число); процесс будет продолжаться (см. Примечание † ниже) до тех пор, пока не произойдет совпадение между выходом функции φ ( x , y ) и некоторым заранее установленным числом (обычно 0). Таким образом, вычисление φ ( x , y ) требует вначале присвоения натурального числа каждой из его переменных x и присвоения "числа совпадений" (обычно 0) регистру " w"."и число (обычно 0) для регистрации y .

Примечание †: неограниченный μ-оператор будет продолжать этот процесс попытки сопоставления до бесконечности или до тех пор, пока не произойдет совпадение. Таким образом, регистр « y » должен быть неограниченным - он должен иметь возможность «удерживать» число произвольного размера. В отличие от «реальной» компьютерной модели, абстрактные машинные модели позволяют это. В случае ограниченного μ-оператора ограниченный снизу μ-оператор будет начинаться с содержания y, установленного на число, отличное от нуля. Ограниченный сверху µ-оператор потребует дополнительного регистра «ub», чтобы содержать число, которое представляет верхнюю границу, плюс дополнительную операцию сравнения; алгоритм может предусматривать как нижнюю, так и верхнюю границы.

Далее мы предполагаем, что регистр инструкций (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 ; в противном случае это увеличивает содержимое « у » зарегистрировать и петлю назад с этим новым у-значением для пробной функции ф ( х , у ) снова.

См. Также [ править ]

• Маккарти формализм

Сноски [ править ]

Общая демонстрация функций [ править ]

Что является обязательным, если функция должна быть полной функцией, - это демонстрация каким-либо другим методом (например, индукцией ), что для каждой и каждой комбинации значений ее параметров x _i некоторое натуральное число y будет удовлетворять μ-оператору, так что алгоритм что означает, что расчет может завершиться:

«... мы всегда должны бояться предполагать, что система уравнений действительно определяет общерекурсивную (то есть полную) функцию. Обычно нам требуются вспомогательные доказательства для этого, например, в форме индуктивного доказательства того, что для каждого значения аргумента вычисление завершается уникальным значением. " (Минский (1967) с.186)

«Другими словами, мы не должны утверждать, что функция эффективно вычислима на том основании, что она была показана как общая (то есть полная) рекурсивная, если только демонстрация того, что она является общей рекурсивной, не эффективна». (Kleene (1952) p. .319)

Пример того, что это означает на практике, см. В примерах рекурсивных функций mu - даже простейший алгоритм усеченного вычитания « x - y = d » может дать для неопределенных случаев, когда x < y , (1) без завершения, (2 ) без чисел (т.е. что-то не так с форматом, поэтому доходность не считается натуральным числом) или (3) обман: неправильные числа в правильном формате. «Правильный» алгоритм вычитания требует внимательного отношения ко всем «случаям».

( x , y ) = {(0, 0), ( a , 0), (0, b ), ( a ≥ b , b ), ( a = b , b ), ( a < b , b )}.

Но даже когда было показано, что алгоритм дает ожидаемый результат в экземплярах {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, мы остались с неприятным чувством , пока мы не можем изобрести «убедительное доказательство» , что случаи ( х , у ) = ( п , т ) все дали ожидаемые результаты. На точку зрения Клини: достаточно ли убедительна наша «демонстрация» (то есть алгоритм, который является нашей демонстрацией), чтобы считаться эффективной ?

Альтернативные абстрактные машинные модели неограниченного μ-оператора от Мински (1967) и Булоса-Берджесса-Джеффри (2002) [ править ]

Неограниченный μ-оператор определен Минским (1967), с. 210, но со специфическим недостатком: оператор не даст t = 0, если его предикат (тест IF-THEN-ELSE) удовлетворен; скорее это дает t = 2. В версии Минского счетчик - « t », а функция φ ( t , x ) помещает его номер в регистр φ. В обычном регистре определения μ регистр w будет содержать 0, но Мински отмечает, что он может содержать любое число k . Набор инструкций Мински эквивалентен следующему, где "JNE" = Перейти к z, если не равно:

{CLR ( r ), INC ( r ), JNE ( r _j , r _k , z )}

Неограниченный μ-оператор также определен Булосом-Берджессом-Джеффри (2002), с. 60-61 для счетчика с набором команд, эквивалентным следующему:

{CLR (r), INC (r), DEC (r), JZ (r, z), H}

В этой версии счетчик «y» называется «r2», а функция f ( x , r2) помещает его номер в регистр «r3». Возможно, причина, по которой Булос-Берджесс-Джеффри очищает r3, заключается в том, чтобы облегчить безусловный переход в петлю ; это часто делается с помощью специального регистра «0», который содержит «0»:

Ссылки [ править ]

• Стивен Клини (1952) Введение в метаматематику , издательство North-Holland Publishing Company, Нью-Йорк, 11-е переиздание 1971 г .: (примечания ко 2-му изданию добавлены к 6-му переизданию).
• Kohlenbach, Ulrich (2005), высшего порядка Reverse Математика, Математика Reverse 2001 , Конспекты лекций по логике, Cambridge University Press , DOI : 10,1017 / +9781316755846,018 , ISBN 9781316755846
• Марвин Л. Мински (1967), Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Энглвуд Клиффс, Нью-Джерси.

На страницах 210-215 Мински показывает, как создать μ-оператор, используя модель регистровой машины , тем самым демонстрируя ее эквивалентность общерекурсивным функциям.

• Джордж Булос , Джон Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Великобритания. См. Стр. 70–71.