В теории вычислимости μ -оператор , оператор минимизации или оператор неограниченного поиска ищет наименьшее натуральное число с заданным свойством. Добавление μ-оператора к примитивным рекурсивным функциям позволяет определить все вычислимые функции .
Предположим, что R( y , x 1 , ..., x k ) — фиксированное ( k +1)-арное отношение на натуральных числах . μ-оператор "μ y ", как в неограниченной, так и в ограниченной форме, является "теоретико-числовой функцией", определенной из натуральных чисел в натуральные числа. Однако "μ y " содержит предикат над натуральными числами, который можно рассматривать как условие, которое оценивается как истинное, когда предикат выполняется, и ложное , когда он не выполняется.
Ограниченный μ-оператор ранее появился в работе Клини (1952), Глава IX Примитивные рекурсивные функции , §45 Предикаты, представление простых множителей как:
Стивен Клини отмечает, что допускается любое из шести ограничений неравенства на диапазон переменной 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 следующим образом:
В этом случае сама R или представляющая ее функция возвращает 0, когда она удовлетворена (т.е. возвращает true ); затем функция возвращает число y . Верхней границы для y не существует , поэтому в ее определении не появляются выражения неравенства.
Для заданного R( y ) неограниченный μ-оператор μ y R( y ) (обратите внимание, что нет требования для "(E y )") является частичной функцией . Клини вместо этого делает его полной функцией (ср. с. 317):
Полная версия неограниченного μ-оператора изучается в обратной математике высшего порядка (Kohlenbach (2005)) в следующей форме:
где верхние индексы означают, что n — нулевого порядка, f — первого порядка, а μ — второго порядка. Эта аксиома приводит к системе Большой пятерки ACA 0, когда она сочетается с обычной базовой теорией обратного порядка математики высшего порядка. [ необходима цитата ]
(i) В контексте примитивных рекурсивных функций , где переменная поиска y μ-оператора ограничена, например, y < 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 ) также является частично рекурсивной функцией.
Оператор μ используется при характеристике вычислимых функций как рекурсивных функций μ .
В конструктивной математике оператор неограниченного поиска связан с принципом Маркова .
Ограниченный μ-оператор может быть выражен довольно просто в терминах двух примитивных рекурсивных функций (далее «prf»), которые также используются для определения функции CASE — произведения членов Π и суммы членов Σ (см. Kleene #B, стр. 224). (При необходимости подойдет любая граница для переменной, такая как s ≤ t или t < z , или 5 < x < 17 и т. д.). Например:
Прежде чем продолжить, нам нужно ввести функцию ψ, называемую « представляющей функцией » предиката R. Функция ψ определяется из входов (t = «истина», f = «ложь») в выходы (0, 1) ( обратите внимание на порядок! ). В этом случае вход для ψ, т. е. {t, f}, поступает из выхода R:
Клини демонстрирует, что μ y y < z R( y ) определяется следующим образом; мы видим, что функция произведения Π действует как логический оператор ИЛИ, а сумма Σ действует как логический оператор И, но производит {Σ≠0, Σ=0}, а не просто {1, 0}:
Уравнение становится проще, если рассмотреть его на примере, как это сделал Клини. Он просто составил записи для представляющей функции ψ(R( y )). Он обозначил представляющие функции χ( y ) вместо ψ( x , y ):
Неограниченный μ-оператор — функция μ y — обычно определяется в текстах. Но читатель может задаться вопросом, почему неограниченный μ-оператор ищет функцию R( x , y ), чтобы получить ноль , а не какое-то другое натуральное число.
Причина нуля в том, что неограниченный оператор μ y будет определен в терминах функции "произведение" Π с ее индексом y , которому разрешено "расти" по мере поиска μ-оператора. Как отмечено в примере выше, произведение Π x < y строки чисел ψ( x , 0) *, ..., * ψ( x , y ) дает ноль всякий раз, когда один из его членов ψ( x , i ) равен нулю:
если любое ψ( x , i ) = 0, где 0 ≤ i ≤ s . Таким образом, Π действует как логическое И.
Функция μ y производит в качестве «выхода» одно натуральное число y = {0, 1, 2, 3, ...}. Однако внутри оператора может возникнуть одна из пары «ситуаций»: (a) «теоретико-числовая функция» χ, которая производит одно натуральное число, или (b) «предикат» R, который производит либо {t = true, f = false}. (И в контексте частично рекурсивных функций Клини позже допускает третий результат: «μ = не решено». [1] )
Клини разделяет свое определение неограниченного μ-оператора, чтобы справиться с двумя ситуациями (a) и (b). Для ситуации (b), прежде чем предикат R( x , y ) сможет служить в арифметической емкости в произведении Π, его выход {t, f} должен быть сначала "обработан" его представляющей функцией χ , чтобы получить {0, 1}. А для ситуации (a), если должно использоваться одно определение, то теоретико-числовая функция χ должна выдавать ноль, чтобы "удовлетворить" μ-оператор. Урегулировав этот вопрос, он демонстрирует с помощью одного "Доказательства III", что либо типы (a), либо (b) вместе с пятью примитивными рекурсивными операторами дают (полные) рекурсивные функции , с этим условием для полной функции :
Клини также допускает третью ситуацию (c), которая не требует доказательства того, что «для всех x существует y , такой что ψ( x , y )». Он использует это в своем доказательстве того, что существует больше тотальных рекурсивных функций, чем можно перечислить; см. сноску «Тотальная демонстрация функций».
Доказательство Клини неформально и использует пример, аналогичный первому примеру, но сначала он приводит μ-оператор к другой форме, которая использует «произведение членов» Π, работающее с функцией χ, которая дает натуральное число n , которое может быть любым натуральным числом, и 0 в случае, когда тест u-оператора «удовлетворён».
Это тонко. На первый взгляд кажется, что уравнения используют примитивную рекурсию. Но Клини не предоставил нам базовый шаг и шаг индукции общей формы:
Чтобы увидеть, что происходит, мы сначала должны напомнить себе, что мы назначили параметр (натуральное число) каждой переменной 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 i , ..., x n ) и запишем просто 'χ( y )' вместо 'χ( x i , ..., x n ), y )'»:
И Минский (1967) стр. 21, и Булос-Берджесс-Джеффри (2002) стр. 60-61 дают определения μ-оператора как абстрактной машины; см. сноску Альтернативные определения μ.
Следующая демонстрация следует Мински без "особенности", упомянутой в сноске. Демонстрация будет использовать модель "преемника" счетчика машины, тесно связанную с аксиомами Пеано и примитивными рекурсивными функциями . Модель состоит из (i) конечного автомата с ТАБЛИЦЕЙ инструкций и так называемого "регистра состояния", который мы переименуем в "Регистр инструкций" (IR), (ii) нескольких "регистров", каждый из которых может содержать только одно натуральное число, и (iii) набора инструкций из четырех "команд", описанных в следующей таблице:
Алгоритм для оператора минимизации μ 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)-й инструкции алгоритм сравнивает число в регистре « w » (например, 0) с числом в регистре «φ» — если они одинаковы, алгоритм выполнился успешно и он выходит через выход ; в противном случае он увеличивает содержимое регистра « y » и возвращается к циклу с этим новым значением y, чтобы снова проверить функцию φ( x , y ).
Для того чтобы функция была полной функцией, необходимо продемонстрировать каким-либо другим методом (например, индукцией ), что для каждой комбинации значений ее параметров x i некоторое натуральное число y будет удовлетворять μ-оператору, так что алгоритм, представляющий вычисление, может быть завершен :
Для примера того, что это означает на практике, см. примеры в mu рекурсивных функциях — даже простейший алгоритм усеченного вычитания " x - y = d " может дать, для неопределенных случаев, когда x < y , (1) нет окончания, (2) нет чисел (т.е. что-то не так с форматом, поэтому результат не считается натуральным числом), или (3) обман: неправильные числа в правильном формате. "Правильный" алгоритм вычитания требует внимательного отношения ко всем "случаям"
Но даже когда алгоритм показал, что он выдает ожидаемый результат в случаях {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, у нас остается неприятное чувство, пока мы не сможем разработать «убедительную демонстрацию» того, что все случаи ( x , y ) = ( n , m ) дают ожидаемые результаты. К вопросу Клини: достаточно ли убедительна наша «демонстрация» (т. е. алгоритм, который является нашей демонстрацией), чтобы считаться эффективной ?
Неограниченный μ-оператор определен Мински (1967) стр. 210, но с особым недостатком: оператор не даст t = 0, когда его предикат (тест IF-THEN-ELSE) удовлетворен; вместо этого он даст t = 2. В версии Мински счетчиком является " t ", а функция φ( t , x ) помещает свое число в регистр φ. В обычном определении μ регистр w будет содержать 0, но Мински замечает, что он может содержать любое число k . Набор инструкций Мински эквивалентен следующему, где "JNE" = Перейти к z, если не равно:
Неограниченный μ-оператор также определен Булосом-Берджессом-Джеффри (2002) на стр. 60-61 для счетчиковой машины с набором инструкций, эквивалентным следующему:
В этой версии счетчик "y" называется "r2", а функция f( x , r2 ) помещает свое число в регистр "r3". Возможно, причина, по которой Boolos-Burgess-Jeffrey clear r3, заключается в том, чтобы облегчить безусловный переход к циклу ; это часто делается с помощью специального регистра "0", который содержит "0":
