μ-operatör

I beräkningsteorin söker operatorn μ-operator , minimeringsoperator eller obegränsad sökoperator efter det minsta naturliga talet med en given egenskap. Att lägga till μ-operatorn till de primitiva rekursiva funktionerna gör det möjligt att definiera alla beräkningsbara funktioner .

Definition

Antag att R( y , x 1 , ..., x k ) är en fast ( k +1)-är relation på de naturliga talen . μ-operatorn "μ y ", i antingen obunden eller begränsad form, är en "talteoretisk funktion" definierad från de naturliga talen till de naturliga talen. Men "μ y " innehåller ett predikat över de naturliga talen, vilket kan ses som ett villkor som utvärderas till sant när predikatet är uppfyllt och falskt när det inte är det.

Den avgränsade μ-operatorn förekommer tidigare i Kleene (1952) Kapitel IX Primitiva rekursiva funktioner, §45 Predikat, primfaktorrepresentation som:

" " (sid. 225)

0 Stephen Kleene noterar att vilken som helst av de sex olikhetsrestriktionerna för intervallet för variabeln y är tillåten, dvs y < z , y ≤ z , w < y < z , w < y ≤ z , w ≤ y < z och w ≤ y ≤ z . "När det angivna intervallet inte innehåller något y så att R( y ) [är "sant"], är värdet på uttrycket "μ y " intervallets kardinalnummer" (sid. 226); det är därför som standard " z " visas i definitionen ovan. Som visas nedan definieras den avgränsade μ-operatorn "μ y y < z " i termer av två primitiva rekursiva funktioner som kallas den finita summan Σ och finita produkten Π, en predikatfunktion som "gör testet" och en representerande funktion som omvandlar {t, f} till { , 1 }.

I kapitel XI §57 Allmänna rekursiva funktioner, definierar Kleene den obegränsade μ-operatorn över variabeln y på följande sätt,

" " (s. 279, där " betyder "där finns ett sådant att...")

0 levererar R själv, eller dess representerande funktion , när den är uppfylld (dvs. levererar true ); funktionen levererar sedan talet y . Det finns ingen övre gräns på y , därför förekommer inga olikhetsuttryck i dess definition.

För en given R( y ) är den ogränsade μ-operatorn μ y R( y ) (observera inget krav för "(E y )" ) en partiell funktion . Kleene gör det som en total funktion istället (jfr s. 317):

Den totala versionen av den obegränsade μ-operatorn studeras i högre ordnings omvänd matematik ( Kohlenbach (2005)) i följande form:

där de upphöjda betyder att n är nollte ordningen, f är första ordningen och μ är andra ordningen. Detta axiom ger upphov till Big Five-systemet ACA 0 när det kombineras med den vanliga basteorin för omvänd matematik av högre ordning. [ citat behövs ]

Egenskaper

(i) I samband med de primitiva rekursiva funktionerna , där sökvariabeln y för μ-operatorn är begränsad, t.ex. y < z i formeln nedan, om predikatet R är primitivt rekursivt (Kleene Proof #E s. 228), sedan

μ y y < z R( y , x 1 , ..., x n ) är en primitiv rekursiv funktion.

(ii) I samband med de (totala) rekursiva funktionerna , där sökvariabeln y är obegränsad men garanterat existerar för alla värden x i av det totala rekursiva predikatets R parametrar,

( x 1 ),...,( x n ) (Ey) R( y , x i , ..., x n ) antyder att μ y R( y , x i , ..., x n ) är en total rekursiv funktion .
Här betyder ( x i ) "för alla x i " och E y betyder "det finns åtminstone ett värde på y så att..." (jfr Kleene (1952) s. 279.)

då ger de fem primitiva rekursiva operatorerna plus den obegränsade-men-totala μ-operatorn upphov till vad Kleene kallade de "allmänna" rekursiva funktionerna (dvs totala funktioner definierade av de sex rekursionsoperatorerna).

(iii) I samband med de partiella rekursiva funktionerna : Antag att relationen R gäller om och endast om en partiell rekursiv funktion konvergerar till noll. Och antag att den partiella rekursiva funktionen konvergerar (till något, inte nödvändigtvis noll) närhelst μ y R( y , x 1 , ..., x k ) definieras och y är μ y R( y , x 1 , ... , x k ) eller mindre. Då är funktionen μ y R( y , x 1 , ..., x k ) också en partiell rekursiv funktion.

μ-operatorn används i karakteriseringen av de beräkningsbara funktionerna som de μ-rekursiva funktionerna .

I konstruktiv matematik är den obegränsade sökoperatorn relaterad till Markovs princip .

Exempel

Exempel 1: Den avgränsade μ-operatorn är en primitiv rekursiv funktion

I det följande representerar x strängen x i , ..., x n .

Den avgränsade μ-operatorn kan uttryckas ganska enkelt i termer av två primitiva rekursiva funktioner (hädanefter "prf") som också används för att definiera CASE-funktionen - produkten av termer Π och summan av termer Σ (jfr. Kleene #B sid 224). (Efter behov är vilken gräns som helst för variabeln som s ≤ t eller t < z , eller 5 < x < 17 etc. lämplig). Till exempel:

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

Innan vi fortsätter måste vi introducera en funktion ψ som kallas "den representerande funktionen " av predikatet R. Funktionen ψ definieras från ingångar (t = "sanning", f = "falsitet") till utgångar (0, 1) ( notera ordningen ! ). I detta fall inmatningen till ψ. dvs {t, f}. kommer från utgången av R:

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

Kleene visar att μ y y < z R( y ) definieras enligt följande; vi ser att produktfunktionen Π agerar som en boolesk ELLER-operator, och summan Σ fungerar ungefär som en boolesk AND men producerar {Σ≠0, Σ=0} snarare än bara {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)]
Observera att Σ faktiskt är en primitiv rekursion med basen Σ( x , 0) = 0 och induktionssteget Σ( x , y +1) = Σ( x , y ) + Π( x , y ). Produkten Π är också en primitiv rekursion med bassteg Π( x , 0) = ψ( x , 0) och induktionssteg Π( x , y +1) = Π( x , y ) × ψ( x , y +1 ) .

Ekvationen är lättare om den observeras med ett exempel, som ges av Kleene. Han gjorde precis upp posterna för den representerande funktionen ψ(R( y )). Han betecknade de representerande funktionerna χ( y ) snarare än ψ( 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

minst y < z så att R( y ) är "sant": φ( y ) = μ y y < z R( y ) 		3

Exempel 2: Den obegränsade μ-operatorn är inte primitiv-rekursiv

Den obegränsade μ-operatorn - funktionen μ y - är den som vanligtvis definieras i texterna. Men läsaren kan undra varför den obegränsade μ-operatorn söker efter en funktion R( x , y ) för att ge noll , snarare än något annat naturligt tal.

I en fotnot låter Minsky sin operatör avslutas när funktionen inuti producerar en matchning med parametern " k " ; det här exemplet är också användbart eftersom det visar en annan författares format:
"För μ t [φ( t ) = k ]" (s. 210)

Anledningen till noll är att den obegränsade operatorn μ y kommer att definieras i termer av funktionen "produkt" Π med dess index y tillåtet att "växa" när μ-operatorn söker. Som noterats i exemplet ovan ger produkten Π x < y av en sträng med tal ψ( x , 0) *, ..., * ψ( x , y ) noll när en av dess medlemmar ψ( x , i ) är noll:

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

om någon ψ( x , i ) = 0 där 0≤ i ≤ s . Således Π fungerar som en boolesk AND.

Funktionen μ y producerar som "utgång" ett enda naturligt tal y = {0, 1, 2, 3, ...}. Men inuti operatorn kan en av ett par "situationer" förekomma: (a) en "talteoretisk funktion" χ som producerar ett enda naturligt tal, eller (b) ett "predikat" R som ger antingen {t = sant, f = falskt}. (Och i samband med partiella rekursiva funktioner medger Kleene senare ett tredje resultat: "μ = obestämd".)

Kleene delar upp sin definition av den obegränsade μ-operatorn för att hantera de två situationerna (a) och (b). För situation (b), innan predikatet R( x , y ) kan tjäna i en aritmetisk kapacitet i produkten Π, måste dess utsignal {t, f} först "opereras" av dess representerande funktion χ för att ge {0, 1}. Och för situation (a) om en definition ska användas måste den talteoretiska funktionen χ producera noll för att "tillfredsställa" μ-operatorn. Med denna fråga avgjord visar han med ett enda "Bevis III" att antingen typerna (a) eller (b) tillsammans med de fem primitiva rekursiva operatorerna ger de (totala) rekursiva funktionerna, med detta förbehåll för en total funktion :

För alla parametrar x måste en demonstration tillhandahållas för att visa att det finns ett y som uppfyller (a) μ y ψ( x , y ) eller (b) μ y R( x , y ) .

situation (c) som inte kräver demonstrationen av "för alla x existerar a y så att ψ( x , y )." Han använder detta i sitt bevis på att det finns fler totala rekursiva funktioner än vad som kan räknas upp ; cf fotnot Total funktionsdemonstration .

Kleenes bevis är informellt och använder ett exempel som liknar det första exemplet, men först kastar han μ-operatorn till en annan form som använder "produkt-av-termer" Π som arbetar på funktionen χ som ger ett naturligt tal n , som kan vara vilket naturligt tal som helst och 0 i det fall då u-operatörens test är "uppfyllt".

Definitionen omarbetad med Π-funktionen:
μ 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 ) är odefinierad för u = 0 eller v > 0.

Det här är subtilt. Vid första anblicken verkar ekvationerna använda primitiv rekursion. Men Kleene har inte försett oss med ett bassteg och ett induktionssteg av den allmänna formen:

  • bassteg: φ(0, x ) = φ( x )
  • induktionssteg: φ(0, x ) = ψ(y, φ(0, x ), x )

För att se vad som pågår måste vi först påminna oss själva om att vi har tilldelat en parameter (ett naturligt tal) till varje variabel x i . För det andra ser vi en efterföljande operatör på jobbet som itererar y (dvs. y') . Och för det tredje ser vi att funktionen μ y y < z χ( y , x ) bara producerar instanser av χ( y , x ) dvs. χ(0, x ), χ(1, x ), ... tills en instans ger 0. För det fjärde, när en instans χ( n , x ) ger 0 gör det att mellantermen av τ, dvs v = π( x , y' ) ger 0. Slutligen, när mellantermen v = 0, μ y y < z χ( y ) exekverar rad (iii) och "avslutar". Kleenes presentation av ekvationerna (ii) och (iii) har bytts ut för att påpeka att linje (iii) representerar en utgång - en utgång som tas endast när sökningen lyckas hitta ett y för att uppfylla χ( y ) och mellanprodukttermen π( x , y' ) är 0; operatorn avslutar sedan sin sökning med τ( z' , 0, y ) = y .

τ(π( x , y ), π( x , y' ), y ), dvs:
  • τ(π( x , 0), π( x , 1), 0),
  • τ(π( x , 1), π( x , 2), 1)
  • τ(π( x , 2), π( x , 3), 2)
  • τ(π( x , 3), π( x , 4), 3)
  • ... tills en matchning sker vid y = n och sedan:
  • τ( z' , 0, y ) = τ( z' , 0, n ) = n och μ-operatörens sökning är gjord.

För exemplet Kleene "... överväg[s] alla fasta värden på ( x i , ..., x n ) och skriv[s] helt enkelt 'χ( y )' för 'χ( x i , ..., x n ), y )'":

y 0 1 2 3 4 5 6 7 etc.
χ( y ) 3 1 2 0 9 0 1 5 . . .
π( y ) = Π s ≤ y χ( s ) 1 3 3 6 0 0 0 0 . . .
↑

minst y < z så att R( y ) är "sant": φ( y ) = μ y y < z R( y ) 		3


Exempel 3: Definition av den obegränsade μ-operatorn i termer av en abstrakt maskin

Både Minsky (1967) sid. 21 och Boolos-Burgess-Jeffrey (2002) sid. 60-61 ger definitioner av μ-operatören som en abstrakt maskin; se fotnot Alternativa definitioner av μ .

Följande demonstration följer Minsky utan den "egenhet" som nämns i fotnoten. Demonstrationen kommer att använda en "efterträdare" motmaskinmodell som är nära relaterad till Peano Axioms och de primitiva rekursiva funktionerna . Modellen består av (i) en finit tillståndsmaskin med en TABELL över instruktioner och ett så kallat 'tillståndsregister' som vi kommer att döpa om till "instruktionsregistret" (IR), (ii) några få "register" som vart och ett kan innehåller endast ett enda naturligt tal, och (iii) en instruktionsuppsättning av fyra "kommandon" som beskrivs i följande tabell:

I det följande betyder symboliken " [ r ] " "innehållet i", och " →r " indikerar en åtgärd med avseende på register r.
Instruktion Mnemonic Åtgärd på register(n) "r" Åtgärd om instruktionsregister, IR
CLEAR register CLR ( r ) 0 → r [IR] + 1 → IR
Increment register INC ( r ) [ r ] + 1 → r [IR] + 1 → IR
Hoppa om lika JE (r 1 , r 2 , z) ingen

OM [ r 1 ] = [ r 2 ] SÅ z → IR ANNAT [ IR ] + 1 → IR
Stanna H ingen [ IR ] → IR

Algoritmen för minimeringsoperatorn μ y [φ( x , y )] kommer i huvudsak att skapa en sekvens av instanser av funktionen φ( x , y ) när värdet på parametern y (ett naturligt tal) ökar; processen kommer att fortsätta (se anmärkning † nedan) tills en matchning sker mellan utdata från funktionen φ( x , y ) och något förutbestämt tal (vanligtvis 0). Sålunda kräver utvärderingen av φ( x , y ), i början, tilldelning av ett naturligt tal till var och en av dess variabler x och en tilldelning av ett "matchningsnummer" (vanligtvis 0) till ett register " w ", och en nummer (vanligtvis 0) för att registrera y .

Notera †: Den obegränsade μ-operatorn kommer att fortsätta denna försök att matcha processen i all oändlighet eller tills en matchning inträffar. Således måste " y "-registret vara obegränsat -- det måste kunna "hålla" ett antal godtyckliga storlekar. Till skillnad från en "riktig" datormodell tillåter abstrakta maskinmodeller detta. I fallet med en begränsad μ-operator, skulle en lägre gränsad μ-operator börja med innehållet i y satt till ett annat tal än noll. En övre gräns μ-operator skulle kräva ett extra register "ub" för att innehålla talet som representerar den övre gränsen plus en ytterligare jämförelseoperation; en algoritm skulle kunna tillhandahålla både nedre och övre gränser.

I det följande antar vi att instruktionsregistret (IR) möter μ y "rutinen" vid instruktionsnummer " n ". Dess första åtgärd kommer att vara att upprätta ett tal i ett dedikerat " w "-register - ett "exempel på" talet som funktionen φ( x , y ) måste producera innan algoritmen kan avslutas (klassiskt är detta talet noll, men se fotnot om användningen av andra siffror än noll). Algoritmens nästa åtgärd vid instruktion " n +1" kommer att vara att rensa " y "-registret -- " y " kommer att fungera som en "uppräknare" som börjar från 0. Sedan vid instruktion " n +2" utvärderar algoritmen dess funktion φ( x , y ) -- vi antar att detta kräver j instruktioner att utföra - och i slutet av dess utvärdering lägger φ( x , y) sin utdata i registret "φ". Vid den ( n + j +3):e instruktionen jämför algoritmen talet i " w "-registret (t.ex. 0) med numret i "φ"-registret - om de är desamma har algoritmen lyckats och den kommer ut genom exit ; annars ökar den innehållet i " y " -registret och går tillbaka med detta nya y-värde för att testa funktionen φ( x , y ) igen.

IR Instruktion Åtgärd på register Åtgärd på Instruktionsregister IR
n μ y [φ( x , y )]: CLR ( w ) 0 → w [IR] + 1 → IR
n +1 CLR ( y ) 0 → y [IR] + 1 → IR
n +2 slinga: φ( x , y ) φ([ x ], [ y ]) → φ [IR] + j + 1 → IR
n + j +3 JE (φ, w , utgång) ingen

FALL: { OM [ φ ]=[ w ] SÅ avsluta → IR ELSE [IR] + 1 → IR }
n + j +4 INC ( y ) [ y ] + 1 → y [IR] + 1 → IR
n + j +5 JE (0, 0, loop) Ovillkorligt hopp 00

FALL: { OM [ r ] =[ r ] THEN loop → IR ELSE loop → IR }
n + j +6 utgång: etc.

Se även

Fotnoter

Total funktionsdemonstration

Det som är obligatoriskt om funktionen ska vara en totalfunktion är en demonstration med någon annan metod (t.ex. induktion ) att för varje kombination av värden av dess parametrar x i kommer ett naturligt tal y att tillfredsställa μ-operatorn så att algoritmen som representerar beräkningen kan avslutas:

"...vi måste alltid tveka att anta att ett ekvationssystem verkligen definierar en generell-rekursiv (dvs total) funktion. Vi kräver normalt hjälpbevis för detta, t.ex. i form av ett induktivt bevis som för varje argumentvärde, beräkningen avslutas med ett unikt värde." (Minsky (1967) s.186)
"Med andra ord, vi bör inte hävda att en funktion är effektivt beräkningsbar på grund av att den har visat sig vara generell (dvs total) rekursiv, såvida inte demonstrationen att den är allmän rekursiv är effektiv." (Kleene (1952) s. 319)

För ett exempel på vad detta betyder i praktiken, se exemplen vid mu rekursiva funktioner — även den enklaste trunkerade subtraktionsalgoritmen " x - y = d " kan ge, för de odefinierade fallen när x < y , (1) ingen avslutning, (2) ) inga siffror (dvs. något fel på formatet så avkastningen anses inte vara ett naturligt tal), eller (3) bedrägeri: fel siffror i rätt format. Den "riktiga" subtraktionsalgoritmen kräver noggrann uppmärksamhet på alla "fall"

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

Men även när algoritmen har visat sig producera den förväntade utsignalen i instanserna {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)} lämnas vi med en orolig känsla tills vi kan skapa en "övertygande demonstration" att fallen ( x , y ) = ( n , m ) alla ger de förväntade resultaten. Till Kleenes poäng: är vår "demonstration" (dvs. algoritmen som är vår demonstration) tillräckligt övertygande för att anses vara effektiv ?

Alternativa abstrakta maskinmodeller av den obegränsade μ-operatören från Minsky (1967) och Boolos-Burgess-Jeffrey (2002)

Den obegränsade μ-operatorn definieras av Minsky (1967) sid. 210 men med en speciell brist: operatören kommer inte att ge t =0 när dess predikat (OM-DÅ-ANELSE-testet) är uppfyllt; snarare ger det t =2. I Minskys version är räknaren " t ", och funktionen φ( t , x ) deponerar sitt nummer i register φ. I det vanliga μ-definitionsregistret w att innehålla 0, men Minsky observerar att det kan innehålla vilket tal k som helst . Minskys instruktionsuppsättning motsvarar följande där "JNE" = Hoppa till z om inte lika:

{ CLR ( r ), INC ( r ), JNE ( r j , r k , z ) }
IR Instruktion Åtgärd på register Åtgärd om instruktionsregister, IR
n μ y φ( x ): CLR ( w ) 0 → w [IR] + 1 → IR
n + 1 CLR ( t ) 0 → t [IR] + 1 → IR
n +2 slinga: φ ( y , x ) φ( [ t ], [ x ] ) → φ [IR] + j + 1 → IR
n + j +3 INC ( t ) [ t ] + 1 → t [IR] + 1 → IR
n + j +4 JNE (φ, w , loop) ingen

FALL: { OM [φ] ≠ [ w ] SÅ "avsluta" → IR ANNARS [IR] + 1 → IR }
n + j +5 INC ( t ) [ t ] + 1 → t [IR] + 1 → IR
n + j +6 utgång: etc.

Den obegränsade μ-operatorn definieras också av Boolos-Burgess-Jeffrey (2002) sid. 60-61 för en diskmaskin med en instruktionsuppsättning motsvarande följande:

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

I denna version kallas räknaren "y" för "r2", och funktionen f( x , r2 ) sätter in sitt nummer i registret "r3". Kanske är anledningen till att Boolos-Burgess-Jeffrey klarar r3 för att underlätta ett ovillkorligt hopp till loop ; detta görs ofta med hjälp av ett dedikerat register "0" som innehåller "0":

IR Instruktion Åtgärd på register Åtgärd om instruktionsregister, IR
n μ r 2 [f( x , r 2 )]: CLR ( r 2 ) 0 → r 2 [IR] + 1 → IR
n +1 slinga: f( y , x ) f( [ t ], [ x ] ) → r 3 [IR] + j + 1 → IR
n +2 JZ ( r 3 , utgång ) ingen

OM [ r 3 ] = 0 SÅ avsluta → 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 , loop)

FALL: { OM [ r 3 ] = 0 DÅ loop → IR ANNARS [IR] + 1 → IR }
n + j +6 utgång: etc.
  •    Kleene, Stephen (2009) [1952], Introduction to Metamathematics , North-Holland, ISBN 9780923891572 , OCLC 935015457
  •   Kohlenbach, Ulrich (2005), Higher Order Reverse Mathematics, Reverse Mathematics 2001 , Lecture notes in Logic, Cambridge University Press , s. 281–295, doi : 10.1017/9781316755846.018 , ISBN 777 513469
  •    Minsky, Marvin L. (1972) [1967], Computation: Finite and Infinite Machines , Prentice-Hall, ISBN 9780131654495 , OCLC 974146753
På sidorna 210-215 visar Minsky hur man skapar μ-operatören med hjälp av registermaskinmodellen, och visar på så sätt dess likvärdighet med de allmänna rekursiva funktionerna.
Hämtad från " https://en.wikipedia.org/w/index.php?title=Μ_operator&oldid=1145864114 "