м оператор

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

Определение

Предположим, что R( , ... , _y,x1 xk ) _{+ 1} — фиксированное ( k )-арное отношение на натуральных числах . μ-оператор «μ y », как в неограниченной, так и в ограниченной форме, представляет собой «теоретико-числовую функцию», определенную от натуральных чисел к натуральным числам. Однако «μ y » содержит предикат над натуральными числами, что можно рассматривать как условие, которое оценивается как истинное , когда предикат удовлетворен, и ложное , когда это не так.

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

" $\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.$(с. 225)

Стивен Клини любое из шести ограничений неравенства на диапазон переменной 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 следующим образом:

" $(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}$(стр. 279, где " $(\exists y)$" означает "существует такой y , что...")

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

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

$\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}}$

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

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

где верхние индексы означают, что n имеет нулевой порядок, f - первый порядок, а µ - второй порядок. Эта аксиома порождает систему Большой Пятерки ACA ₀ в сочетании с обычной базовой теорией обратной математики высшего порядка.

Характеристики

(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 ) является Полная рекурсивная функция .

Здесь ( xi ₎ означает «для всех xi _» , а Ey означает «существует по крайней мере одно значение 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 .

Ограниченный μ-оператор может быть довольно просто выражен через две примитивно-рекурсивные функции (далее «prf»), которые также используются для определения CASE-функции — произведения термов Π и суммы термов Σ (см. Клини № B, стр. 224). любая граница переменной, например s ≤ t или t < z или 5 < x (При необходимости подойдет < 17 и т. д.). Например:

• Π _{s ≤ т} ж _s ( Икс , s ) знак равно ж ₀ ( Икс , 0) × ж ₁ ( Икс , 1) × ... × ж _т ( Икс , т )
• Σ _{т < z} г _т ( Икс , т ) знак равно г ₀ ( Икс , 0) + г ₁ ( Икс , 1) + ... + г _z-1 ( Икс , 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 )) =

[ψ( х , 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 ):

и	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 ) знак равно Σ т < y π( т )	1	2	3	3	3	3	3	3
хотя бы y < z такой, что R( y ) «истинно»: φ( y ) = μ y y < z R( y )				3

Пример 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, е = ложь}. (И в контексте частично рекурсивных функций Клини позже допускает третий результат: «μ = не определено». )

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

Для всех параметров x , должна быть предоставлена ​​демонстрация того, что существует y удовлетворяющий условиям (a) µ y ψ( x , y ) или (b) µ y R( x , y ).

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

Доказательство Клини является неформальным и использует пример, аналогичный первому примеру, но сначала он приводит μ-оператор к другой форме, которая использует «произведение термов» Π, действующее на функцию χ, которое дает натуральное число 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 )'":

и	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 < z такой, что R( y ) «истинно»: φ( y ) = μ y y < z R( y )				3

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

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

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

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

Инструкция	Мнемоника	Действие над регистром(ами) "r"	Действие по регистру инструкций, IR
ОЧИСТИТЬ регистр	CLR ( р )	0 → р	[ И ] + 1 → И
Регистр INCrement	ИНК ( р )	[ р ] + 1 → р	[ И ] + 1 → И
Перейти, если равно	ЕС (р 1 , р 2 , z)	никто	ЕСЛИ [ р 1 ] = [ р 2 ] ТОГДА z → ИК ИНАЧЕ [ ЕСТЬ ] + 1 → ЕСТЬ
Остановиться	ЧАС	никто	[ И ] → И

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

И		Инструкция	Действия по регистрации	Действия по регистрации инструкций IR
н	μ y [φ( x , y )]:	ЦЛР ( ж )	0 → ш	[ И ] + 1 → И
п +1		CLR ( и )	0 → й	[ И ] + 1 → И
п +2	петля:	φ( Икс , у )	φ([ x ], [ y ]) → φ	[ И ] + j + 1 → И
н + д +3		Я (φ, ш , выход)	никто	СЛУЧАЙ: { ЕСЛИ [ φ ]=[ ш ] ТОГДА выход → ИК ИНАЧЕ [Есть] + 1 → ЕСТЬ }
н + д +4		ИНК ( у )	[ y ] + 1 → y	[ И ] + 1 → И
н + д +5		JE (0, 0, цикл)	Безусловный прыжок	СЛУЧАЙ: {ЕСЛИ [ г 0 ] = [ г 0 ] ТОГДА цикл → ИК ELSE цикл → IR }
н + д +6	Выход:	и т. д.

См. также

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

Сноски

Полная демонстрация функций

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

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

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

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

( Икс , у ) знак равно {(0, 0), ( а , 0), (0, б ), ( а ≥ б , б ), ( а знак равно б , б ), ( а < б , б )}.

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

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

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

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

И		Инструкция	Действия по регистрации	Действие по регистру инструкций, IR
н	μ y φ( x ):	ЦЛР ( ж )	0 → ш	[ И ] + 1 → И
п + 1		ЦЛР ( т )	0 → т	[ И ] + 1 → И
п +2	петля:	φ ( у , х )	φ( [ т ], [ Икс ] ) → φ	[ И ] + j + 1 → И
н + д +3		ВКЛ ( т )	[ т ] + 1 → т	[ И ] + 1 → И
н + д +4		JNE (φ, w , цикл)	никто	СЛУЧАЙ: { ЕСЛИ [φ] ≠ [ ш ] ТОГДА «выход» → ИК ИНАЧЕ [Есть] + 1 → ЕСТЬ }
н + д +5		ВКЛ ( т )	[ т ] + 1 → т	[ И ] + 1 → И
н + д +6	Выход:	и т. д.

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

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

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

И		Инструкция	Действия по регистрации	Действие по регистру инструкций, IR
н	мкм р 2 [е( х , р 2 )]:	CLR ( р 2 )	0 → р 2	[ И ] + 1 → И
п +1	петля:	е ( у , х )	ж( [ т ], [ Икс ] ) → р 3	[ И ] + j + 1 → И
п +2		JZ ( р 3 , выход)	никто	ЕСЛИ [ р 3 ] = 0 ТОГДА выход → ИК ИНАЧЕ [ ЕСТЬ ] + 1 → ЕСТЬ
н + д +3		CLR ( р 3 )	0 → р 3	[ И ] + 1 → И
н + д +4		ВКЛ ( р 2 )	[ р 2 ] + 1 → р 2	[ И ] + 1 → И
н + д +5		ИЗ ( р 3 , петля)		СЛУЧАЙ: { ЕСЛИ [ r 3 ] = 0 ТОГДА цикл → ИК ИНАЧЕ [Есть] + 1 → ЕСТЬ }
н + д +6	Выход:	и т. д.

Ссылки

• Клини, Стивен (2009) [1952], Введение в метаматематику , Северная Голландия, ISBN  9780923891572 , OCLC   935015457
• Коленбах, Ульрих (2005), Обратная математика высшего порядка, Обратная математика 2001 , Конспекты лекций по логике, Cambridge University Press , стр. 281–295, CiteSeerX   10.1.1.643.551 , doi : 10.1017/9781316755846.018 , ISBN  9781316755846
• Мински, Марвин Л. (1972) [1967], Вычисления: конечные и бесконечные машины , Прентис-Холл, ISBN  9780131654495 , OCLC   974146753

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

• Булос, Джордж ; Берджесс, Джон ; Джеффри, Ричард (2002), «Минимизация S6.2» , Вычислимость и логика (4-е изд.), Cambridge University Press, стр. 70–71, ISBN  9780521701464