μ-operator - μ operator

In de berekenbaarheidstheorie zoekt de μ-operator , de minimalisatie-operator of de onbegrensde zoekoperator naar het minst natuurlijke getal met een bepaalde eigenschap. Door de μ-operator toe te voegen aan de vijf primitieve recursieve operatoren, is het mogelijk om alle berekenbare functies te definiëren .

Definitie

Stel dat R ( y , x 1 , ..., x k ) een vaste ( k +1) -aire relatie is op de natuurlijke getallen . De μ-operator "μ y ", in de onbegrensde of begrensde vorm, is een "getaltheoretische functie" gedefinieerd van de natuurlijke getallen tot de natuurlijke getallen. Echter, "μ y " bevat een predikaat boven de natuurlijke getallen dat true oplevert wanneer aan het predikaat wordt voldaan en false wanneer dit niet het geval is.

De begrensde μ-operator verschijnt eerder in Kleene (1952) Hoofdstuk IX Primitieve recursieve functies, §45 Predicaten, priemfactorrepresentatie als:

​

Stephen Kleene merkt op dat elk van de zes ongelijkheidsbeperkingen op het bereik van de variabele y is toegestaan, dwz y < z , y ≤ z , w < y < z , w < y ≤ z , w ≤ y < z en w ≤ y ≤ z . "Als het aangegeven bereik geen y bevat , zodat R ( y ) [" waar "is], is de waarde van de uitdrukking " μ y "het hoofdgetal van het bereik" (p. 226); daarom verschijnt de standaard " z " in de bovenstaande definitie. Zoals hieronder wordt getoond, wordt de begrensde μ-operator "μ y y < z " gedefinieerd in termen van twee primitieve recursieve functies die de eindige som Σ en het eindige product Π worden genoemd, een predikaatfunctie die 'de test doet' en een representatieve functie die converteert {t, f} tot { 0 , 1 }.

In Hoofdstuk XI §57 Algemene Recursieve Functies, definieert Kleene de onbegrensde μ-operator over de variabele y op de volgende manier,

​

In dit geval levert R zelf, of zijn representatieve functie , 0 op als eraan wordt voldaan (dwz levert waar ); de functie levert dan het getal y op . Er bestaat geen bovengrens op y , daarom verschijnen er geen ongelijkheidsuitdrukkingen in de definitie ervan.

Voor een gegeven R ( y ) is de onbegrensde μ-operator μ y R ( y ) (let op: geen vereiste voor "(E y )") is een deelfunctie . Kleene maakt het in plaats daarvan tot een totale functie (vgl. P.317):

De totale versie van de onbegrensde μ-operator wordt bestudeerd in omgekeerde wiskunde van hogere orde ( Kohlenbach (2005) ) in de volgende vorm:

waarbij de superscripts betekenen dat n de nulde orde is, f de eerste orde is en μ de tweede orde. Dit axioma geeft aanleiding tot het Big Five-systeem ACA 0 in combinatie met de gebruikelijke basistheorie van omgekeerde wiskunde van hogere orde.

Eigendommen

(i) In de context van de primitieve recursieve functies , waarbij de zoekvariabele y van de μ-operator begrensd is, bijv. y < z in de onderstaande formule, als het predikaat R primitief recursief is (Kleene Proof #E p.228), vervolgens

μ y y < z R ( y , x 1 , ..., x n ) is een primitieve recursieve functie.

(ii) In de context van de (totale) recursieve functies , waarbij het zoeken met variabele y is onbegrensd maar gegarandeerd bestaan voor alle waarden x i parameters van het totale recursieve predicaat R's,

​
Hier betekent ( x i ) "voor alle x i " en E y betekent "er bestaat tenminste één waarde van y zodat ..." (cf. Kleene (1952) p. 279.)

dan geven de vijf primitieve recursieve operatoren plus de onbegrensde-maar-totaal μ-operator aanleiding tot wat Kleene de "algemene" recursieve functies noemde (dwz totale functies gedefinieerd door de zes recursieoperatoren).

(iii) In de context van de partieel recursieve functies : Stel dat de relatie R geldt als en slechts als een partieel recursieve functie convergeert naar nul. En stel dat die gedeeltelijk recursieve functie convergeert (naar iets, niet noodzakelijk nul) wanneer μ y R ( y , x 1 , ..., x k ) is gedefinieerd en y is μ y R ( y , x 1 , ... , x k ) of kleiner. Dan is de functie μ y R ( y , x 1 , ..., x k ) ook een partieel recursieve functie.

De μ-operator wordt gebruikt bij de karakterisering van de berekenbare functies als de μ recursieve functies .

In constructieve wiskunde is de onbegrensde zoekoperator gerelateerd aan het principe van Markov .

Voorbeelden

Voorbeeld 1: De begrensde μ-operator is een primitief recursieve functie

In het volgende staat x voor de string x i , ..., x n .

De begrensde μ-operator kan vrij eenvoudig worden uitgedrukt in termen van twee primitieve recursieve functies (hierna "prf") die ook worden gebruikt om de CASE-functie te definiëren - het product-of-terms Π en de som-of-terms Σ (cf Kleene #B pagina 224). (Indien nodig is elke grens voor de variabele zoals s ≤ t of t < z , of 5 < x <17 enz. Geschikt). Bijvoorbeeld:

  • Π 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)

Voordat we verder gaan, moeten we een functie ψ introduceren genaamd "de representatieve functie " van predikaat R. Functie ψ wordt gedefinieerd van inputs (t = "truth", f = "falsity") naar outputs (0, 1) ( let op de volgorde ! ). In dit geval de invoer naar ψ. dwz {t, f}. komt van de output van R:

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

Kleene toont aan dat μ y y < z R ( y ) als volgt wordt gedefinieerd; we zien dat de productfunctie Π zich gedraagt ​​als een Booleaanse OR-operator, en dat de som somewhat enigszins als een Booleaanse AND werkt, maar {Σ ≠ 0, Σ = 0} produceert in plaats van alleen {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)]
Merk op dat Σ eigenlijk een primitieve recursie is met de basis Σ ( x , 0) = 0 en de inductiestap Σ ( x , y +1) = Σ ( x , y ) + Π ( x , y ). Het product Π is ook een primitieve recursie met basisstap Π ( x , 0) = ψ ( x , 0) en inductiestap Π ( x , y +1) = Π ( x , y ) × ψ ( x , y +1 ) .

De vergelijking is gemakkelijker als ze wordt bekeken met een voorbeeld, zoals gegeven door Kleene. Hij verzon zojuist de gegevens voor de vertegenwoordigende functie ψ (R ( y )). Hij wees de representatieve functies χ ( y ) aan in plaats van ψ ( 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
tenminste y < z zodat R ( y ) "waar" is:
φ ( y ) = μ y y < z R ( y ) 		3

Voorbeeld 2: De onbegrensde μ-operator is niet primitief-recursief

De onbegrensde μ-operator - de functie μ y - is degene die gewoonlijk in de teksten wordt gedefinieerd. Maar de lezer kan zich afvragen waarom de onbegrensde μ-operator zoekt naar een functie R ( x , y ) om nul op te leveren , in plaats van een ander natuurlijk getal.

In een voetnoot staat Minsky zijn operator toe om te beëindigen wanneer de functie binnen een overeenkomst produceert met de parameter " k "; dit voorbeeld is ook handig omdat het het formaat van een andere auteur laat zien:
'Voor μ t [φ ( t ) = k ]' (p. 210)

De reden voor nul is dat de onbegrensde operator μ y zal worden gedefinieerd in termen van de functie "product" Π waarvan de index y mag "groeien" als de μ-operator zoekt. Zoals opgemerkt in het bovenstaande voorbeeld, levert het product Π x < y van een reeks getallen ψ ( x , 0) *, ..., * ψ ( x , y ) nul op wanneer een van de leden ψ ( x , i ) is nul:

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

indien aanwezig ψ ( x , i ) = 0 waarbij 0≤ i ≤ s . Dus de Π gedraagt ​​zich als een Booleaanse EN.

De functie μ y produceert als "uitvoer" een enkel natuurlijk getal y = {0, 1, 2, 3, ...}. Binnen de operator kan echter een van de volgende "situaties" voorkomen: (a) een "getaltheoretische functie" χ die een enkel natuurlijk getal produceert, of (b) een "predikaat" R dat ofwel {t = true, f = false}. (En in de context van partieel recursieve functies geeft Kleene later een derde uitkomst toe: "μ = onbeslist".)

Kleene splitst zijn definitie van de onbegrensde μ-operator om de twee situaties (a) en (b) te behandelen. Voor situatie (b), voordat het predikaat R ( x , y ) kan dienen in een rekenkundige hoedanigheid in het product its, moet de uitvoer {t, f} eerst worden "bewerkt" door zijn representatieve functie χ om {0, 1}. En voor situatie (a) als er één definitie moet worden gebruikt, dan moet de getaltheoretische functie zero nul opleveren om "te voldoen" aan de μ-operator. Nu deze kwestie is opgelost, demonstreert hij met enkele "Proof III" dat ofwel de typen (a) of (b) samen met de vijf primitieve recursieve operatoren de (totale) recursieve functies opleveren , met deze voorwaarde voor een totale functie :

Voor alle parameters x moet een demonstratie worden gegeven om aan te tonen dat er een y bestaat die voldoet aan (a) μ y ψ ( x , y ) of (b) μ y R ( x , y ).

Kleene geeft ook een derde situatie toe (c) die niet vereist dat "voor alle x a y bestaat zodanig dat a ( x , y )". Hij gebruikt dit in zijn bewijs dat er meer totaal recursieve functies bestaan ​​dan opgesomd kunnen worden ; zie voetnoot Totale functiedemonstratie .

Kleene's bewijs is informeel en gebruikt een voorbeeld dat lijkt op het eerste voorbeeld, maar eerst gooit hij de μ-operator in een andere vorm die het 'product-van-termen' gebruikt Π die werkt op functie χ die een natuurlijk getal n oplevert , dat kan een willekeurig natuurlijk getal zijn, en 0 in het geval dat de test van de u-operator "voldaan" is.

De definitie herschreven met de Π-functie:
μ y y < z χ ( y ) =
  • (ik): π ( X , Y ) = Π s < Y χ ( X , s )
  • (ii): φ ( x ) = τ (π ( x , y ), π ( x , y ' ), y )
  • (iii): τ ( z ' , 0, y ) = y ; τ ( u , v , w ) is niet gedefinieerd voor u = 0 of v > 0.

Dit is subtiel. Op het eerste gezicht lijken de vergelijkingen primitieve recursie te gebruiken. Maar Kleene heeft ons geen basisstap en een inductiestap van de algemene vorm gegeven:

  • basisstap: φ (0, x ) = φ ( x )
  • inductiestap: φ (0, x ) = ψ (y, φ (0, x ), x )

Om te zien wat er aan de hand is, moeten we ons er eerst aan herinneren dat we aan elke variabele x i een parameter (een natuurlijk getal) hebben toegewezen . Ten tweede zien we een opvolger-operator aan het werk die y (dwz de y ' ) itereert . En ten derde zien we dat de functie μ y y < z χ ( y , x ) slechts instanties produceert van χ ( y , x ) dwz χ (0, x ), χ (1, x ), ... tot een instantie levert 0 op. Ten vierde, als een instantie χ ( n , x ) 0 oplevert, zorgt dit ervoor dat de middelste term van τ, dwz v = π ( x , y ' ) , 0 oplevert . Ten slotte, als de middelste term v = 0, μ y y < z χ ( y ) voert regel (iii) en "exits" uit. Kleene's presentatie van vergelijkingen (ii) en (iii) zijn uitgewisseld om dit punt te maken dat lijn (iii) een uitgang vertegenwoordigt - een uitgang die alleen wordt genomen als de zoekopdracht met succes een y vindt die voldoet aan χ ( y ) en de middelste productterm π ( x , y ' ) is 0; de operator beëindigt zijn zoektocht met τ ( z ' , 0, y ) = y .

τ (π ( x , y ), π ( x , y ' ), y ), dat wil zeggen:
  • τ (π ( x , 0), π ( x , 1), 0),
  • τ (π ( x , 1), π ( x , 2), 1)
  • τ (π ( x , 2), π ( x , 3), 2)
  • τ (π ( x , 3), π ( x , 4), 3)
  • ... totdat een match plaatsvindt op y = n en dan:
  • τ ( z ' , 0, y ) = τ ( z' , 0, n ) = n en de zoekactie van de μ-operator is voltooid.

Voor het voorbeeld Kleene "... beschouw [s] alle vaste waarden van ( x i , ..., x n ) en schrijf [s] simpelweg 'χ ( y )' voor 'χ ( x i , ..., x n ), y ) '":

y 0 1 2 3 4 5 6 7 enz.
χ ( y ) 3 1 2 0 9 0 1 5 ​ ​ ​
π ( y ) = Π s ≤ y χ ( s ) 1 3 3 6 0 0 0 0 ​ ​ ​
​
tenminste y < z zodat R ( y ) "waar" is:
φ ( y ) = μ y y < z R ( y ) 		3


Voorbeeld 3: Definitie van de onbegrensde μ-operator in termen van een abstracte machine

Beide Minsky (1967) p. 21 en Boolos-Burgess-Jeffrey (2002) p. 60-61 geven definities van de μ-operator als een abstracte machine; zie voetnoot Alternatieve definities van μ .

De volgende demonstratie volgt Minsky zonder de "eigenaardigheid" die in de voetnoot wordt genoemd. De demonstratie een "opvolger" gebruikt teller machine model nauw verwant aan de Peano Axioma en primitief recursieve functie . Het model bestaat uit (i) een eindige toestandsmachine met een TABEL met instructies en een zogenaamd 'toestandsregister' dat we zullen hernoemen tot 'het Instructieregister' (IR), (ii) een paar 'registers' die elk kunnen bevatten slechts een enkel natuurlijk getal, en (iii) een instructieset van vier "commando's" beschreven in de volgende tabel:

In het volgende betekent de symboliek "[r]" "de inhoud van", en "→ r" geeft een actie aan met betrekking tot register r.
Instructie Ezelsbruggetje Actie op register (s) "r" Actie op instructieregister, IR
CLeaR register CLR (r) 0 → r [IR] + 1 -> IR
INCrement register INC (r) [r] + 1 → r [IR] + 1 -> IR
Spring indien gelijk JE (r 1 , r 2 , z) geen ALS [r 1 ] = [r 2 ] DAN z → IR
ELSE [IR] + 1 → IR
Stop H. geen [IR] → IR

Het algoritme voor de minimalisatie-operator μ y [φ ( x , y )] zal in wezen een reeks instanties van de functie φ ( x , y ) creëren naarmate de waarde van parameter y (een natuurlijk getal) toeneemt; het proces zal doorgaan (zie opmerking † hieronder) totdat er een overeenkomst optreedt tussen de uitvoer van functie φ ( x , y ) en een vooraf vastgesteld nummer (meestal 0). De evaluatie van φ ( x , y ) vereist dus in het begin de toewijzing van een natuurlijk getal aan elk van de variabelen x en een toewijzing van een 'matchnummer' (meestal 0) aan een register ' w ', en een nummer (meestal 0) om y te registreren .

Opmerking †: De onbegrensde μ-operator zal dit proces van poging tot overeenkomst tot in het oneindige voortzetten of totdat er een overeenkomst plaatsvindt. Dus het " y " -register moet onbegrensd zijn - het moet in staat zijn om een ​​aantal van willekeurige grootte te "vasthouden". In tegenstelling tot een "echt" computermodel laten abstracte machinemodellen dit toe. In het geval van een begrensde μ-operator, zou een ondergrens μ-operator beginnen met de inhoud van y ingesteld op een ander getal dan nul. Een μ-operator met een bovengrens zou een aanvullend register "ub" nodig hebben om het getal te bevatten dat de bovengrens vertegenwoordigt, plus een aanvullende vergelijkingsoperatie; een algoritme zou voor zowel onder- als bovengrenzen kunnen zorgen.

In het volgende nemen we aan dat het Instructieregister (IR) de μ y "routine" tegenkomt bij instructienummer " n ". De eerste actie is om een ​​getal vast te leggen in een speciaal " w " -register - een "voorbeeld van" het getal dat de functie φ ( x , y ) moet produceren voordat het algoritme kan eindigen (klassiek is dit het getal nul, maar zie de voetnoot over het gebruik van andere getallen dan nul). De volgende actie van het algoritme bij instructie " n +1" is het wissen van het " y " -register - " y " zal fungeren als een "up-counter" die begint bij 0. Vervolgens evalueert het algoritme bij instructie " n +2" zijn functie φ ( x , y ) - we nemen aan dat hiervoor j instructies nodig zijn - en aan het einde van zijn evaluatie deponeert φ ( x , y) zijn output in register "φ". Bij de ( n + j +3) rd instructie vergelijkt het algoritme het getal in het " w " register (bijv. 0) met het getal in het "φ" register - als ze hetzelfde zijn, is het algoritme geslaagd en ontsnapt het door exit ; anders verhoogt het de inhoud van het " y " -register en loopt terug met deze nieuwe y-waarde om de functie φ ( x , y ) opnieuw te testen .

IR Instructie Actie op register Actie op instructieregister IR
n μ y [φ ( x , y )]: CLR (w) 0 → w [IR] + 1 -> IR
n +1 CLR ( y ) 0 → y [IR] + 1 -> IR
n +2 lus: φ ( x , y ) φ ([ x ], [ y ]) → φ [IR] + j + 1 -> IR
n + j +3 JE (φ, w , uitgang) geen GEVAL: {IF [φ] = [ w ] THEN exit → IR
ELSE [IR] + 1 → IR}
n + j +4 INC ( y ) ​ [IR] + 1 -> IR
n + j +5 JE (0, 0, lus) Onvoorwaardelijke sprong GEVAL: {IF [r 0 ] = [r 0 ] THEN lus → IR
ELSE lus → IR}
n + j +6 Uitgang: enz.

Zie ook

Voetnoten

Totale functiedemonstratie

Wat verplicht is als de functie een totale functie moet zijn, is een demonstratie door een andere methode (bijv. Inductie ) dat voor elke combinatie van waarden van zijn parameters x i een natuurlijk getal y zal voldoen aan de μ-operator, zodat het algoritme dat vertegenwoordigt de berekening kan eindigen:

"... we moeten altijd aarzelen om aan te nemen dat een stelsel vergelijkingen echt een algemeen-recursieve (dwz totale) functie definieert. Normaal gesproken hebben we hiervoor aanvullend bewijs nodig, bijvoorbeeld in de vorm van een inductief bewijs dat, voor elke argumentwaarde, de berekening eindigt met een unieke waarde. " (Minsky (1967) p.186)
"Met andere woorden, we moeten niet beweren dat een functie effectief berekenbaar is op grond van het feit dat is aangetoond dat deze algemeen (dwz totaal) recursief is, tenzij de demonstratie dat deze algemeen recursief is effectief is." (Kleene (1952) p. .319)

Voor een voorbeeld van wat dit in de praktijk betekent, zie de voorbeelden bij mu recursieve functies — zelfs het eenvoudigste afgekapte aftrekalgoritme " x - y = d " kan opleveren, voor de ongedefinieerde gevallen wanneer x < y , (1) geen beëindiging, (2 ) geen getallen (dwz er is iets mis met het formaat, dus de opbrengst wordt niet als een natuurlijk getal beschouwd), of (3) bedrog: verkeerde getallen in het juiste formaat. Het 'juiste' aftrekalgoritme vereist zorgvuldige aandacht voor alle 'gevallen'

​

Maar zelfs als is aangetoond dat het algoritme de verwachte uitvoer produceert in de gevallen {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, blijven we achter met een ongemakkelijk gevoel totdat we een "overtuigende demonstratie" kunnen bedenken dat de gevallen ( x , y ) = ( n , m ) alle de verwachte resultaten opleveren. Wat Kleene betreft: is onze "demonstratie" (dwz het algoritme dat onze demonstratie is) overtuigend genoeg om als effectief te worden beschouwd ?

Alternatieve abstracte machinemodellen van de onbegrensde μ-operator uit Minsky (1967) en Boolos-Burgess-Jeffrey (2002)

De onbegrensde μ-operator wordt gedefinieerd door Minsky (1967) p. 210 maar met een eigenaardige fout: de operator zal geen t = 0 opleveren als aan zijn predikaat (de IF-THEN-ELSE-test) is voldaan; het levert eerder t = 2 op. In de versie van Minsky is de teller " t ", en de functie φ ( t , x ) deponeert zijn nummer in register φ. In het gebruikelijke μdefinitieregister bevat w 0, maar Minsky merkt op dat het elk getal k kan bevatten . De instructieset van Minsky is gelijk aan de volgende, waarbij "JNE" = Spring naar z indien niet gelijk:

{CLR ( r ), INC ( r ), JNE ( r j , r k , z )}
IR Instructie Actie op register Actie op instructieregister, IR
n μ y φ ( x ): CLR ( w ) 0 → w [IR] + 1 -> IR
n + 1 CLR ( t ) 0 → t [IR] + 1 -> IR
n +2 lus: φ ( y , x ) φ ([ t ], [ x ]) → φ [IR] + j + 1 -> IR
n + j +3 INC ( t ) ​ [IR] + 1 -> IR
n + j +4 JNE (φ, w , lus) geen GEVAL: {ALS [φ] ≠ [ w ] THEN "exit" → IR
ELSE [IR] + 1 → IR}
n + j +5 INC ( t ) ​ [IR] + 1 -> IR
n + j +6 Uitgang: enz.

De onbegrensde μ-operator wordt ook gedefinieerd door Boolos-Burgess-Jeffrey (2002) p. 60-61 voor een telmachine met een instructieset gelijk aan het volgende:

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

In deze versie heet de teller "y" "r2", en de functie f ( x , r2) deponeert zijn nummer in register "r3". Misschien is de reden dat Boolos-Burgess-Jeffrey r3 vrijmaakt om een ​​onvoorwaardelijke sprong naar een lus te vergemakkelijken ; dit wordt vaak gedaan door gebruik te maken van een speciaal register "0" dat "0" bevat:

IR Instructie Actie op register Actie op instructieregister, IR
n μ r 2 [f ( x , r 2 )]: CLR ( r 2 ) 0 → r 2 [IR] + 1 -> IR
n +1 lus: f ( y , x ) f ([ t ], [ x ]) → r 3 [IR] + j + 1 -> IR
n +2 JZ ( r 3 , exit) geen IF [ r 3 ] = 0 THEN exit → IR
ELSE [IR] + 1 → IR
n + j +3 CLR ( r 3 ) 0 → r 3 [IR] + 1 -> IR
n + j +4 INC ( r 2 ) ​ [IR] + 1 -> IR
n + j +5 JZ ( r 3 , lus) GEVAL: {IF [ r 3 ] = 0 THEN lus → IR
ELSE [IR] + 1 → IR}
n + j +6 Uitgang: enz.

Referenties

  • Stephen Kleene (1952) Inleiding tot Metamathematica , North-Holland Publishing Company, New York, 11e herdruk 1971: (aantekeningen 2e editie toegevoegd op 6e herdruk).
  • 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
Op pagina's 210-215 laat Minsky zien hoe je de μ-operator maakt met behulp van het registermachinemodel , waarmee hij de gelijkwaardigheid ervan met de algemeen recursieve functies aantoont.