operator μ - μ operator

W teoria obliczalności , w ľ-Operator , operatora minimalizacji lub nieograniczonych operatorów wyszukiwania poszukiwania najmniejszego liczby naturalnej z danej nieruchomości. Dodanie operatora μ do pięciu pierwotnych operatorów rekurencyjnych umożliwia zdefiniowanie wszystkich obliczalnych funkcji .

Definicja

Załóżmy, że R ( y , x 1 , ..., x k ) jest ustaloną ( k + 1) -arną relacją na liczbach naturalnych . Operator μ „μ y ”, w postaci nieograniczonej lub ograniczonej, jest „funkcją teorii liczb” zdefiniowaną od liczb naturalnych do liczb naturalnych. Jednak „μ y ” zawiera predykat nad liczbami naturalnymi, który dostarcza prawdę, gdy predykat jest spełniony, i fałsz, gdy nie jest.

Ograniczonym μ Operator pojawił się wcześniej w Kleene (1952), rozdział IX funkcji pierwotnie rekurencyjne, §45 Predykaty reprezentacja czynnik pierwszy jako:

„ ” (str. 225)

Stephen Kleene zauważa, że ​​dowolne z sześciu ograniczeń nierówności w zakresie zmiennej y jest dozwolone, tj. Y < z , y ≤ z , w < y < z , w < y ≤ z , w ≤ y < z i w ≤ y ≤ z . „Gdy wskazany zakres nie zawiera y takiego, że R ( y ) [jest„ prawda ”], wartość wyrażenia „ μ y ”jest liczbą kardynalną zakresu” (s. 226); dlatego w powyższej definicji pojawia się domyślne „ z ”. Jak pokazano poniżej, ograniczony operator μ "μ y y < z " jest zdefiniowany za pomocą dwóch pierwotnych funkcji rekurencyjnych zwanych sumą skończoną Σ i iloczynem skończonym Π, funkcji predykatu wykonującej test i funkcji reprezentującej, która przekształca {t, f} do { 0 , 1 }.

W rozdziale XI §57 Ogólne funkcje rekurencyjne Kleene definiuje nieograniczony operator μ na zmiennej y w następujący sposób:

" " (str. 279, gdzie " " oznacza "istnieje y takie, że ...")

W tym przypadku sam R lub jego funkcja reprezentująca dostarcza 0, gdy jest spełniony (tj. Dostarcza prawdę ); funkcja następnie dostarcza liczbę y . Na y nie ma górnej granicy , stąd w jej definicji nie występują żadne wyrażenia nierówności.

Dla danego R ( y ) nieograniczony operator μ μ y R ( y ) (zwróć uwagę, że nie ma wymagań dotyczących „(E y )”) jest funkcją częściową . Kleene czyni to jako funkcję całkowitą (por. S. 317):

Całkowita wersja nieograniczonego operatora μ jest badana w matematyce odwrotnej wyższego rzędu ( Kohlenbach (2005) ) w następującej postaci:

gdzie indeksy górne oznaczają, że n jest rzędu zer, f jest pierwszym i μ jest drugim rzędem. Aksjomat ten daje początek systemowi Wielkiej Piątki ACA 0 w połączeniu ze zwykłą teorią podstawową matematyki odwrotnej wyższego rzędu.

Nieruchomości

(i) W kontekście pierwotnych funkcji rekurencyjnych , w których zmienna wyszukiwania y operatora μ jest ograniczona, np. y < z w poniższym wzorze, jeśli predykat R jest rekursywny pierwotnie rekurencyjny (Dowód Kleene'a #E s. 228), następnie

μ y y < z R ( y , x 1 , ..., x n ) jest pierwotną funkcją rekurencyjną.

(ii) W kontekście (całkowitych) funkcji rekurencyjnych , gdzie zmienna wyszukiwania y jest nieograniczona, ale gwarantuje istnienie dla wszystkich wartości x i wszystkich parametrów predykatu rekurencyjnego R,

( x 1 ), ..., ( x n ) (Ey) R ( y , x i , ..., x n ) implikuje, że μ y R ( y , x i , ..., x n ) jest a całkowita funkcja rekurencyjna .
Tutaj ( x i ) oznacza „dla wszystkich x i ”, a E y oznacza „istnieje co najmniej jedna wartość y taka, że ​​...” (por. Kleene (1952) s. 279.)

wtedy pięć prymitywnych operatorów rekurencyjnych plus nieograniczony, ale całkowity operator μ-daje początek temu, co Kleene nazwał „ogólnymi” funkcjami rekurencyjnymi (tj. łącznymi funkcjami zdefiniowanymi przez sześć operatorów rekurencji).

(iii) W kontekście częściowych funkcji rekurencyjnych : Załóżmy, że relacja R zachodzi wtedy i tylko wtedy, gdy częściowa funkcja rekurencyjna jest zbieżna do zera. I przypuśćmy, że ta częściowa funkcja rekurencyjna jest zbieżna (do czegoś, niekoniecznie do zera), ilekroć μ y R ( y , x 1 , ..., x k ) jest zdefiniowane, a y jest μ y R ( y , x 1 , ... , x k ) lub mniejsze. Wtedy funkcja μ y R ( y , x 1 , ..., x k ) jest również częściową funkcją rekurencyjną.

Operator μ jest używany w charakteryzowaniu obliczalnych funkcji jako funkcje rekurencyjne μ .

W matematyce konstruktywnej operator wyszukiwania nieograniczonego jest powiązany z zasadą Markowa .

Przykłady

Przykład 1: Ograniczony operator μ jest pierwotną funkcją rekurencyjną

W poniższym x reprezentuje ciąg x i , ..., x n .

Ograniczonym μ Operator może być wyrażona raczej tylko w kategoriach dwóch pierwotnych funkcji rekurencyjnej (dalej „PRF”), które są także stosowane w celu określenia Przypadek Funkcjonalnie produkt, o-względem Π a suma-of-względem Σ (CF Kleene #B strona 224). (W razie potrzeby dowolna granica dla zmiennej, taka jak s ≤ t lub t < z , lub 5 < x <17 itd., Jest odpowiednia). Na przykład:

  • Π s ≤ t f s ( x , s ) = f 0 ( x , 0) × f 1 ( x , 1) × ... × f t ( x , t )
  • Σ t < z g t ( x , t ) = g 0 ( x , 0) + g 1 ( x , 1) + ... + g z-1 ( x , z -1)

Zanim przejdziemy dalej, musimy wprowadzić funkcję ψ zwaną „ funkcją reprezentującą ” predykatu R. Funkcję ψ definiuje się od danych wejściowych (t = „prawda”, f = „fałsz”) do wyników (0, 1) ( zwróć uwagę na kolejność ! ). W tym przypadku wejście do ψ. czyli {t, f}. pochodzi z wyjścia R:

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

Kleene wykazuje, że μ y y < z R ( y ) jest zdefiniowane następująco; widzimy, że funkcja iloczynu Π zachowuje się jak operator logiczny OR, a suma som działa trochę jak logiczne AND, ale generuje {Σ ≠ 0, Σ = 0} zamiast tylko {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)]
Zauważ, że Σ jest w rzeczywistości rekursją pierwotną z podstawą Σ ( x , 0) = 0 i krokiem indukcji Σ ( x , y +1) = Σ ( x , y ) + Π ( x , y ). Iloczyn Π jest również rekursją pierwotną z krokiem podstawowym Π ( x , 0) = ψ ( x , 0) i krokiem indukcyjnym Π ( x , y +1) = Π ( x , y ) × ψ ( x , y +1) ) .

Równanie jest łatwiejsze, jeśli obserwuje się je na przykładzie, jak podał Kleene. Właśnie stworzył wpisy dla funkcji reprezentującej ψ (R ( y )). Wyznaczał reprezentujące funkcje χ ( y ) zamiast ψ ( x , y ):

y 0 1 2 3 4 5 6 7 = z
χ ( y ) 1 1 1 0 1 0 0
π ( y ) = Π s ≤ y χ ( s ) 1 1 1 0 0 0 0 0
σ ( y ) = Σ t < y π ( t ) 1 2 3 3 3 3 3 3
najmniej y < z takie, że R ( y ) jest „prawdziwe”:
φ ( y ) = μ y y < z R ( y ) 		3

Przykład 2: nieograniczony operator μ nie jest prymitywno-rekurencyjny

Nieograniczony operator μ - funkcja μ y - jest tą powszechnie zdefiniowaną w tekstach. Ale czytelnik może się zastanawiać, dlaczego nieograniczony operator μ szuka funkcji R ( x , y ), aby dać zero , zamiast jakiejś innej liczby naturalnej.

W przypisie Minsky zezwala swojemu operatorowi na zakończenie działania, gdy funkcja wewnątrz tworzy dopasowanie do parametru " k "; ten przykład jest również przydatny, ponieważ pokazuje format innego autora:
„Dla μ t [φ ( t ) = k ]” (str. 210)

Przyczyną zera jest to, że operator nieograniczony μ y zostanie zdefiniowany w kategoriach funkcji „produkt” Π z indeksem y, który może „rosnąć” w miarę wyszukiwania operatora μ. Jak zauważono w powyższym przykładzie, iloczyn Π x < y ciągu liczb ψ ( x , 0) *, ..., * ψ ( x , y ) daje zero, gdy jeden z jego elementów ψ ( x , i ) wynosi zero:

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

jeśli istnieje ψ ( x , i ) = 0, gdzie 0≤ i ≤ s . Zatem Π działa jak logiczne AND.

Funkcja μ y daje jako „wyjście” pojedynczą liczbę naturalną y = {0, 1, 2, 3, ...}. Jednak wewnątrz operatora może pojawić się jedna z kilku „sytuacji”: (a) „funkcja teorii liczb” χ, która daje pojedynczą liczbę naturalną, lub (b) „predykat” R, który daje albo {t = prawda, f = false}. (A w kontekście częściowych funkcji rekurencyjnych, Kleene przyznaje później trzeci wynik: „μ = niezdecydowany”.)

Kleene rozdziela swoją definicję nieograniczonego operatora μ, aby obsłużyć dwie sytuacje (a) i (b). W sytuacji (b), zanim predykat R ( x , y ) będzie mógł służyć jako arytmetyczna pojemność iloczynu Π, jego wyjście {t, f} musi być najpierw „obsługiwane” przez funkcję reprezentującą χ, aby uzyskać {0, 1}. A dla sytuacji (a), jeśli ma być użyta jedna definicja, to teoretyczna funkcja liczb χ musi dawać zero, aby „spełnić” operator μ. Po załatwieniu tej sprawy demonstruje za pomocą pojedynczego „Dowodu III”, że typy (a) lub (b) razem z pięcioma prymitywnymi operatorami rekurencyjnymi dają (łącznie) funkcje rekurencyjne , z tym zastrzeżeniem dla funkcji całkowitej :

Dla wszystkich parametrów x należy przeprowadzić demonstrację, aby wykazać, że istnieje y spełniające (a) μ y ψ ( x , y ) lub (b) μ y R ( x , y ).

Kleene przyznaje również trzecią sytuację (c), która nie wymaga wykazania „dla wszystkich x a y istnieje takie, że ψ ( x , y )”. Używa tego w swoim dowodzie, że istnieje więcej totalnych funkcji rekurencyjnych, niż można wyliczyć ; cf przypis Całkowita demonstracja funkcji .

Dowód Kleene jest nieformalny i używa przykładu podobnego do pierwszego przykładu, ale najpierw rzuca operator μ na inną postać, która używa „iloczynu terminów” Π działającego na funkcji χ, która daje liczbę naturalną n , która może być dowolną liczbą naturalną i 0 w przypadku, gdy test operatora u jest „spełniony”.

Definicja przekształcona z funkcją Π:
μ 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 ) jest nieokreślone dla u = 0 lub v > 0.

To jest subtelne. Na pierwszy rzut oka wydaje się, że równania wykorzystują rekursję pierwotną. Ale Kleene nie dostarczył nam kroku podstawowego i kroku wprowadzającego w ogólnej formie:

  • krok podstawowy: φ (0, x ) = φ ( x )
  • krok indukcyjny: φ (0, x ) = ψ (y, φ (0, x ), x )

Aby zobaczyć, co się dzieje, musimy najpierw przypomnieć sobie, że każdej zmiennej x i przypisaliśmy parametr (liczbę naturalną) . Po drugie, widzimy następcę-operatora w pracy iterującej y (tj. Y ' ). Po trzecie, widzimy, że funkcja μ y y < z χ ( y , x ) po prostu tworzy wystąpienia χ ( y , x ) tj. Χ (0, x ), χ (1, x ), ... aż wystąpienie daje 0. Po czwarte, kiedy wystąpienie χ ( n , x ) daje 0, to powoduje, że środkowy człon τ, tj. v = π ( x , y ' ) daje 0. Wreszcie, gdy środkowy wyraz v = 0, μ y y < z χ ( y ) wykonuje wiersz (iii) i „wychodzi”. Przedstawione przez Kleene'a równania (ii) i (iii) zostały zamienione, aby wskazać, że linia (iii) reprezentuje wyjście - wyjście jest podejmowane tylko wtedy, gdy wyszukiwanie pomyślnie znajdzie y spełniające χ ( y ) i środkowy termin iloczynowy π ( x , y ' ) wynosi 0; operator kończy wtedy swoje wyszukiwanie z τ ( z ' , 0, y ) = y .

τ (π ( x , y ), π ( x , y ' ), y ), czyli:
  • τ (π ( x , 0), π ( x , 1), 0),
  • τ (π ( x , 1), π ( x , 2), 1)
  • τ (π ( x , 2), π ( x , 3), 2)
  • τ (π ( x , 3), π ( x , 4), 3)
  • ... aż do dopasowania przy y = n, a następnie:
  • τ ( z ' , 0, y ) = τ ( z' , 0, n ) = n i wyszukiwanie operatora μ jest zakończone.

Na przykład Kleene "... rozważ [s] dowolne ustalone wartości ( x i , ..., x n ) i napisz [s] po prostu 'χ ( y )' dla 'χ ( x i , ..., x n ), y ) '":

y 0 1 2 3 4 5 6 7 itp.
χ ( y ) 3 1 2 0 9 0 1 5 . . .
π ( y ) = Π s ≤ y χ ( s ) 1 3 3 6 0 0 0 0 . . .
↑
najmniej y < z takie, że R ( y ) jest „prawdziwe”:
φ ( y ) = μ y y < z R ( y ) 		3


Przykład 3: Definicja nieograniczonego operatora μ w postaci abstrakcyjnej maszyny

Zarówno Minsky (1967) str. 21 i Boolos-Burgess-Jeffrey (2002) str. 60-61 zawierają definicje operatora μ jako maszyny abstrakcyjnej; patrz przypis Alternatywne definicje μ .

Następująca demonstracja następuje po Minsky bez „osobliwości” wspomnianej w przypisie. Demonstracja wykorzysta „następcę” modelu maszyny licznika blisko związanego z aksjomatami Peano i prymitywnymi funkcjami rekurencyjnymi . Model składa się z (i) skończonej maszyny stanowej z TABELĄ instrukcji i tak zwanym „rejestrem stanu”, którego nazwę zmienimy na „Rejestr instrukcji” (IR), (ii) kilka „rejestrów”, z których każdy może zawierają tylko jedną liczbę naturalną oraz (iii) zbiór instrukcji czterech „poleceń” opisanych w poniższej tabeli:

W dalszej części symbolika „[r]” oznacza „zawartość”, a „→ r” oznacza akcję w odniesieniu do rejestru r.
Instrukcja Mnemoniczny Działanie na rejestrach „r” Działanie w sprawie rejestru instrukcji, IR
Rejestr CLeaR CLR (r) 0 → r [IR] + 1 → IR
Rejestr przyrostów INC (r) [r] + 1 → r [IR] + 1 → IR
Skocz, jeśli równe JE (r 1 , r 2 , z) Żaden JEŻELI [r 1 ] = [r 2 ] TO z → IR
ELSE [IR] + 1 → IR
Postój H. Żaden [IR] → IR

Algorytm operatora minimalizacji μ y [φ ( x , y )] w zasadzie utworzy sekwencję wystąpień funkcji φ ( x , y ) wraz ze wzrostem wartości parametru y (liczba naturalna); proces będzie kontynuowany (patrz uwaga † poniżej), dopóki nie nastąpi dopasowanie między wynikiem funkcji φ ( x , y ) a pewną wcześniej ustaloną liczbą (zwykle 0). Zatem ocena φ ( x , y ) wymaga, na początku, przypisania liczby naturalnej do każdej z jej zmiennych x i przypisania „numeru dopasowania” (zwykle 0) do rejestru „ w ”, a numer (zwykle 0) do zarejestrowania y .

Uwaga †: Nieograniczony operator μ będzie kontynuował tę próbę dopasowania w nieskończoność lub do momentu dopasowania. Zatem rejestr „ y ” musi być nieograniczony - musi być w stanie „pomieścić” liczbę o dowolnej wielkości. W przeciwieństwie do „prawdziwego” modelu komputerowego, pozwalają na to abstrakcyjne modele maszyn. W przypadku ograniczonego operatora μ, ograniczonego niższego operatora μ zaczyna się od zawartości y ustawionej na liczbę inną niż zero. Operator μ z ograniczeniem górnym wymagałby dodatkowego rejestru „ub”, który zawierałby liczbę reprezentującą górną granicę oraz dodatkową operację porównania; algorytm mógłby określać zarówno dolną, jak i górną granicę.

W dalszej części zakładamy, że rejestr instrukcji (IR) napotyka „procedurę” μ y pod numerem instrukcji „ n ”. Jego pierwszym działaniem będzie ustalenie liczby w dedykowanym rejestrze " w " - "przykładzie" liczby, którą funkcja φ ( x , y ) musi wygenerować, zanim algorytm będzie mógł zakończyć działanie (klasycznie jest to liczba zero, ale zobacz przypis o stosowaniu liczb innych niż zero). Następnym działaniem algorytmu w instrukcji „ n + 1” będzie wyczyszczenie rejestru „ y ” - „ y ” będzie działać jako „licznik w górę”, który zaczyna się od 0. Następnie algorytm oblicza na podstawie instrukcji „ n +2” jego funkcja φ ( x , y ) - zakładamy, że do wykonania tego zadania wymaga j instrukcji - a pod koniec oceny φ ( x , y) umieszcza swoje wyjście w rejestrze „φ”. W instrukcji ( n + j +3) rd algorytm porównuje liczbę w rejestrze „ w ” (np. 0) z liczbą w rejestrze „φ” - jeśli są one takie same, algorytm się powiódł i wychodzi przez wyjście ; poza tym, że zwiększa się zawartość z „ r ” rejestru i pętlę z powrotem do tej nowej wartości dla y funkcja testu cp ( x , y ) ponownie.

IR Instrukcja Działanie w rejestrze Czynność dotycząca rejestru instrukcji IR
n μ y [φ ( x , y )]: CLR (w) 0 → w [IR] + 1 → IR
n +1 CLR ( y ) 0 → y [IR] + 1 → IR
n +2 pętla: φ ( x , y ) φ ([ x ], [ y ]) → φ [IR] + j + 1 → IR
n + j +3 JE (φ, w , wyjście) Żaden PRZYPADEK: {JEŚLI [φ] = [ w ] TO wyjście → IR
ELSE [IR] + 1 → IR}
n + j +4 INC ( y ) [ y ] + 1 → y [IR] + 1 → IR
n + j +5 JE (0, 0, pętla) Bezwarunkowy skok PRZYPADEK: {IF [r 0 ] = [r 0 ] THEN pętla → IR
ELSE pętla → IR}
n + j +6 Wyjście: itp.

Zobacz też

Przypisy

Pełna demonstracja funkcji

To, co jest obowiązkowe, jeśli funkcja ma być funkcją totalną, to wykazanie inną metodą (np. Indukcją ), że dla każdej kombinacji wartości jej parametrów x i pewna liczba naturalna y spełni operator μ, więc algorytm co oznacza, że ​​obliczenia mogą się zakończyć:

„... zawsze musimy wahać się przed założeniem, że układ równań rzeczywiście definiuje funkcję generalnie-rekurencyjną (tj. całkowitą). Zwykle potrzebujemy na to pomocniczego dowodu, np. w postaci indukcyjnego dowodu, że dla każdej wartości argumentu, obliczenie kończy się unikalną wartością. " (Minsky (1967) str.186)
„Innymi słowy, nie powinniśmy twierdzić, że funkcja jest efektywnie obliczalna na tej podstawie, że wykazano, że jest ogólna (tj. Całkowita) rekurencyjna, chyba że wykazanie, że jest generalnie rekurencyjna, jest skuteczne.” (Kleene (1952) str. 0,319)

Aby zapoznać się z przykładem tego, co to oznacza w praktyce, zobacz przykłady w funkcjach rekurencyjnych mu - nawet najprostszy algorytm odejmowania obciętego " x - y = d " może dać w nieokreślonych przypadkach, gdy x < y , (1) brak zakończenia, (2 ) brak liczb (tj. coś jest nie tak z formatem, więc wydajność nie jest uważana za liczbę naturalną) lub (3) oszustwo: błędne liczby w prawidłowym formacie. „Właściwy” algorytm odejmowania wymaga szczególnej uwagi na wszystkie „przypadki”

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

Ale nawet jeśli wykazano, że algorytm generuje oczekiwane wyniki w instancjach {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, to pozostaje niespokojny uczucie aż można stworzyć „” przekonaniem wykazanie, że w przypadkach ( x , y ) = ( n , m ), wszystkie dają oczekiwane wyniki. Do punktu Kleene'a: ​​czy nasza „demonstracja” (tj. Algorytm, który jest naszą demonstracją) jest wystarczająco przekonująca, aby można ją było uznać za skuteczną ?

Alternatywne abstrakcyjne modele maszynowe nieograniczonego operatora μ z Minsky (1967) i Boolos-Burgess-Jeffrey (2002)

Nieograniczony operator μ jest zdefiniowany przez Minsky'ego (1967) str. 210, ale z osobliwą wadą: operator-nie da t = 0, gdy jego predykat (test JEŻELI-TO-JESZCZE) jest spełniony; raczej daje t = 2. W wersji Minsky'ego licznikiem jest „ t ”, a funkcja φ ( t , x ) umieszcza swój numer w rejestrze φ. W zwykłym rejestrze definicji μ w będzie zawierało 0, ale Minsky zauważa, że ​​może zawierać dowolną liczbę k . Zestaw instrukcji Minsky'ego jest równoważny z następującym, gdzie „JNE” = Skocz do z, jeśli nie jest równe:

{CLR ( r ), INC ( r ), JNE ( r j , r k , z )}
IR Instrukcja Działanie w rejestrze Działanie w sprawie rejestru instrukcji, IR
n μ y φ ( x ): CLR ( w ) 0 → w [IR] + 1 → IR
n + 1 CLR ( t ) 0 → t [IR] + 1 → IR
n +2 pętla: φ ( y , x ) φ ([ t ], [ x ]) → φ [IR] + j + 1 → IR
n + j +3 INC ( t ) [ t ] + 1 → t [IR] + 1 → IR
n + j +4 JNE (φ, w , pętla) Żaden PRZYPADEK: {JEŚLI [φ] ≠ [ w ] TO "wyjście" → IR
ELSE [IR] + 1 → IR}
n + j +5 INC ( t ) [ t ] + 1 → t [IR] + 1 → IR
n + j +6 Wyjście: itp.

Nieograniczony operator μ jest również zdefiniowany przez Boolos-Burgess-Jeffrey (2002) str. 60-61 dla maszyny liczącej z zestawem instrukcji równoważnym z poniższym:

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

W tej wersji licznik „y” nazywany jest „r2”, a funkcja f ( x , r2) umieszcza jego numer w rejestrze „r3”. Być może powodem, dla którego Boolos-Burgess-Jeffrey wyczyścił r3 jest ułatwienie bezwarunkowego skoku do pętli ; jest to często wykonywane przy użyciu dedykowanego rejestru „0”, który zawiera „0”:

IR Instrukcja Działanie w rejestrze Działanie w sprawie rejestru instrukcji, IR
n μ r 2 [f ( x , r 2 )]: CLR ( r 2 ) 0 → r 2 [IR] + 1 → IR
n +1 pętla: f ( y , x ) f ([ t ], [ x ]) → r 3 [IR] + j + 1 → IR
n +2 JZ ( r 3 , wyjście) Żaden IF [ r 3 ] = 0 TO wyjście → IR
ELSE [IR] + 1 → IR
n + j +3 CLR ( r 3 ) 0 → r 3 [IR] + 1 → IR
n + j +4 INC ( r 2 ) [ r 2 ] + 1 → r 2 [IR] + 1 → IR
n + j +5 JZ ( r 3 , pętla) PRZYPADEK: {JEŚLI [ r 3 ] = 0 TO pętla → IR
ELSE [IR] + 1 → IR}
n + j +6 Wyjście: itp.

Bibliografia

  • Stephen Kleene (1952) Introduction to Metamathematics , North-Holland Publishing Company, Nowy Jork, 11-ty przedruk 1971: (uwagi do 2. wydania dodane w 6. przedruku).
  • Kohlenbach, Ulrich (2005), Higher Order Reverse Mathematics, Reverse Mathematics 2001 , Lecture notes in Logic, Cambridge University Press , doi : 10.1017 / 9781316755846.018 , ISBN   9781316755846
  • Marvin L. Minsky (1967), Computation: Finite and Infinite Machines , Prentice-Hall, Inc. Englewood Cliffs, NJ
Na stronach 210-215 Minsky pokazuje, jak utworzyć operator μ za pomocą modelu maszyny rejestrującej , demonstrując w ten sposób jego równoważność z ogólnymi funkcjami rekurencyjnymi.