Beregningsfunktion - Computable function

Beregnelige funktioner er de grundlæggende undersøgelsesobjekter inden for beregningsteori . Beregningsfunktioner er den formaliserede analog til den intuitive opfattelse af algoritmer , i den forstand at en funktion kan beregnes, hvis der findes en algoritme, der kan udføre funktionen, dvs. ved at få et input fra funktionsdomænet, kan den returnere det tilsvarende output. Beregnelige funktioner bruges til at diskutere beregningsevne uden at henvise til nogen konkret beregningsmodel, såsom Turing -maskiner eller registreringsmaskiner . Enhver definition skal imidlertid henvise til en bestemt beregningsmodel, men alle gyldige definitioner giver den samme klasse af funktioner. Særlige modeller for beregning, der giver anledning til sættet med beregningsfunktioner, er de Turing-beregningsbare funktioner og de generelle rekursive funktioner .

Før den præcise definition af beregningsfunktion brugte matematikere ofte det uformelle udtryk effektivt beregningsbart . Dette udtryk er siden blevet identificeret med de beregningsbare funktioner. Bemærk, at den effektive beregning af disse funktioner ikke indebærer, at de kan beregnes effektivt (dvs. beregnes inden for en rimelig tid). Faktisk kan det for nogle effektivt beregningsbare funktioner vises, at enhver algoritme, der beregner dem, vil være meget ineffektiv i den forstand, at algoritmens driftstid stiger eksponentielt (eller endda superexponentielt ) med inputets længde. Områderne med gennemførlig beregning og beregningskompleksitetsundersøgelsesfunktioner , der kan beregnes effektivt.

Ifølge kirke -Turing -tesen er beregningsfunktioner nøjagtigt de funktioner, der kan beregnes ved hjælp af en mekanisk beregningsenhed givet ubegrænsede mængder tid og lagerplads. Tilsvarende siger denne afhandling, at en funktion kan beregnes, hvis og kun hvis den har en algoritme. Bemærk, at en algoritme i denne forstand forstås som en sekvens af trin, en person med ubegrænset tid og en ubegrænset forsyning af pen og papir kan følge.

De Blum aksiomer kan anvendes til at definere en abstrakt beregningsmæssig kompleksitet teori på sættet af beregnelige funktioner. I beregningskompleksitetsteorien er problemet med at bestemme kompleksiteten af ​​en beregningsbar funktion kendt som et funktionsproblem .

Definition

Beregning af en funktion er en uformel forestilling. En måde at beskrive det på er at sige, at en funktion kan beregnes, hvis dens værdi kan opnås ved en effektiv procedure . Med mere stringens kan en funktion beregnes, hvis og kun hvis der er en effektiv procedure, der givet værdien en given k - tupel af naturlige tal . I overensstemmelse med denne definition forudsætter resten af ​​denne artikel, at beregningsfunktioner tager uendeligt mange naturlige tal som argumenter og frembringer en værdi, der er et enkelt naturligt tal. ${\ displaystyle f: \ mathbb {N} ^{k} \ rightarrow \ mathbb {N}}$ ${\ displaystyle \ mathbf {x}}$${\ displaystyle f (\ mathbf {x})}$

Som modparter til denne uformelle beskrivelse findes der flere formelle, matematiske definitioner. Klassen af ​​beregningsfunktioner kan defineres i mange ækvivalente beregningsmodeller , herunder

• Turningsmaskiner
• μ-rekursive funktioner
• Lambda -beregning
• Postmaskiner ( Post -Turing -maskiner og tagmaskiner ).
• Registrer maskiner

Selvom disse modeller anvender forskellige repræsentationer for funktionerne, deres input og output, findes der oversættelser mellem to modeller, og derfor beskriver hver model stort set den samme klasse af funktioner, hvilket giver anledning til den opfattelse, at formel beregning er både naturlig og ikke for snæver .

For eksempel kan man formalisere beregningsfunktioner som μ-rekursive funktioner , som er delfunktioner, der tager begrænsede tupler af naturlige tal og returnerer et enkelt naturligt tal (ligesom ovenfor). De er den mindste klasse af delfunktioner, der inkluderer konstant-, efterfølger- og projektionsfunktionerne og lukkes under sammensætning , primitiv rekursion og μ -operatoren .

Tilsvarende kan beregningsbare funktioner formaliseres som funktioner, der kan beregnes af et idealiseret computermiddel, såsom en Turing -maskine eller en registermaskine . Formelt set kan en delvis funktion beregnes, hvis og kun hvis der findes et computerprogram med følgende egenskaber: ${\ displaystyle f: \ mathbb {N} ^{k} \ rightarrow \ mathbb {N}}$

1. Hvis er defineret, vil programmet afslutte på input med værdien gemt i computerens hukommelse.${\ displaystyle f (\ mathbf {x})}$${\ displaystyle \ mathbf {x}}$${\ displaystyle f (\ mathbf {x})}$
2. Hvis det er udefineret, afsluttes programmet aldrig på input .${\ displaystyle f (\ mathbf {x})}$${\ displaystyle \ mathbf {x}}$

Egenskaber ved beregningsfunktioner

Den grundlæggende egenskab ved en beregningsbar funktion er, at der skal være en endelig procedure (en algoritme ), der fortæller, hvordan funktionen skal beregnes. Beregningsmodellerne anført ovenfor giver forskellige fortolkninger af, hvad en procedure er, og hvordan den bruges, men disse fortolkninger deler mange egenskaber. Det faktum, at disse modeller giver ækvivalente klasser af beregningsfunktioner, stammer fra det faktum, at hver model er i stand til at læse og efterligne en procedure for en af ​​de andre modeller, ligesom en kompilator er i stand til at læse instruktioner på et computersprog og udsende instruktioner i et andet sprog.

Enderton [1977] giver følgende karakteristika ved en procedure til beregning af en beregningsbar funktion; lignende karakteriseringer er blevet givet af Turing [1936], Rogers [1967] og andre.

• "Der skal være nøjagtige instruktioner (dvs. et program), begrænset i længden, for proceduren." Hver beregningsbar funktion skal således have et begrænset program, der fuldstændigt beskriver, hvordan funktionen skal beregnes. Det er muligt at beregne funktionen ved blot at følge instruktionerne; ingen gætte eller særlig indsigt er påkrævet.
• "Hvis proceduren får et k -dobbelt x i domænet f , skal proceduren efter et begrænset antal diskrete trin afslutte og producere f ( x ) ." Intuitivt fortsætter proceduren trin for trin med en specifik regel, der dækker, hvad der skal gøres ved hvert trin i beregningen. Kun uendeligt mange trin kan udføres, før værdien af ​​funktionen returneres.
• "Hvis proceduren får et k -tuple x, der ikke er i f -domænet , kan proceduren fortsætte for evigt, aldrig standse. Eller den kan blive hængende på et tidspunkt (dvs. en af ​​dens instruktioner kan ikke udføres) , men det må ikke foregive at producere en værdi for f ved x . " Så hvis der nogensinde findes en værdi for f ( x ) , skal den være den korrekte værdi. Det er ikke nødvendigt for computermidlet at skelne korrekte resultater fra forkerte, fordi proceduren er defineret som korrekt, hvis og kun hvis det giver et resultat.

Enderton fortsætter med at liste flere præciseringer af disse 3 krav til proceduren for en beregningsbar funktion:

1. Proceduren skal teoretisk virke for vilkårligt store argumenter. Det antages ikke, at argumenterne for eksempel er mindre end antallet af atomer i Jorden.
2. Proceduren skal standses efter endeligt mange trin for at producere et output, men det kan tage vilkårligt mange trin, før den standses. Der antages ingen tidsbegrænsning.
3. Selvom proceduren muligvis kun bruger en begrænset mængde lagerplads under en vellykket beregning, er der ingen grænser for mængden af ​​plads, der bruges. Det antages, at proceduren kan få yderligere lagerplads, når proceduren beder om det.

For at opsummere, baseret på denne opfattelse kan en funktion beregnes, hvis: (a) givet et input fra sit domæne, muligvis afhængig af ubegrænset lagerplads, kan den give det tilsvarende output ved at følge en procedure (program, algoritme), der er dannet af en begrænset antal nøjagtige entydige instruktioner; (b) den returnerer sådan output (stopper) i et begrænset antal trin; og (c) hvis det får et input, der ikke er i sit domæne, stopper det enten aldrig, eller det sætter sig fast.

Feltet med beregningskompleksitetsstudier fungerer med foreskrevne grænser for tid og/eller rum tilladt i en vellykket beregning.

Beregnelige sæt og relationer

Et sæt A af naturlige tal kaldes beregnelige (synonymer: rekursive , afgørbart ) hvis der er en beregnelig, total funktion f sådan at for enhver naturligt tal n , f ( n ) = 1 , hvis n er i A og f ( n ) = 0 hvis n er ikke i A .

Et sæt naturlige tal kaldes computable enumerable (synonymer: rekursivt tællende , semidecidable ), hvis der er en beregningsfunktion f sådan, at for hvert tal n er f ( n ) defineret, hvis og kun hvis n er i sættet. Et sæt er således beregningsbart opregnet, hvis og kun hvis det er domænet for en eller anden beregningsbar funktion. Ordet optællende bruges, fordi følgende er ækvivalente for en ikke -undtaget delmængde B af de naturlige tal:

• B er domænet for en beregningsbar funktion.
• B er området for en total beregningsbar funktion. Hvis B er uendelig, kan funktionen antages at være injektiv .

Hvis et sæt B er den række af en funktion f derefter funktionen kan ses som en opregning af B , fordi listen f (0), f (1), ... vil omfatte ethvert element i B .

Fordi hver finitær relation på de naturlige tal kan identificeres med et tilsvarende sæt af begrænsede sekvenser af naturlige tal, kan forestillinger om beregningsrelation og beregningsbart talbare forhold defineres ud fra deres analoger for sæt.

Formelle sprog

I beregningsteori inden for datalogi er det almindeligt at overveje formelle sprog . Et alfabet er et vilkårligt sæt. Et ord på et alfabet er en begrænset sekvens af symboler fra alfabetet; det samme symbol kan bruges mere end én gang. For eksempel er binære strenge nøjagtigt ordene i alfabetet {0, 1} . Et sprog er en delmængde af samlingen af ​​alle ord på et fast alfabet. For eksempel er samlingen af ​​alle binære strenge, der indeholder præcis 3 en, et sprog over det binære alfabet.

En nøgleegenskab ved et formelt sprog er den sværhedsgrad, der kræves for at afgøre, om et givet ord er på sproget. Noget kodningssystem skal udvikles for at give en beregningsfunktion mulighed for at tage et vilkårligt ord i sproget som input; dette betragtes normalt som rutine. Et sprog kaldes computable (synonymer: recursive , decidable ), hvis der er en beregningsfunktion f sådan, at for hvert ord w over alfabetet, f ( w ) = 1 hvis ordet er på sproget og f ( w ) = 0 hvis ordet er ikke på sproget. Således kan et sprog beregnes, bare hvis der er en procedure, der er i stand til korrekt at fortælle, om vilkårlige ord er i sproget.

Et sprog kan tælles op (synonymer: rekursivt tællende , semidecidable ), hvis der er en beregningsfunktion f sådan, at f ( w ) defineres, hvis og kun hvis ordet w er i sproget. Udtrykket optællende har den samme etymologi som i beregningsmæssigt talbare sæt af naturlige tal.

Eksempler

Følgende funktioner kan beregnes:

• Hver funktion med et begrænset domæne ; f.eks. enhver endelig rækkefølge af naturlige tal.
• Hver konstant funktion f  : N ^k → N , f ( n ₁ , ... n _k ): = n .
• Tilføjelse f  : N ² → N , f ( n ₁ , n ₂ ): = n ₁ + n ₂
• Den største fællesdeler af to tal
• En Bézout -koefficient på to tal
• Den mindste primfaktor af et tal

Hvis f og g kan beregnes, så er det også: f + g , f * g , hvis f er unary , max ( f , g ), min ( f , g ), arg max { y  ≤  f ( x )} og mange flere kombinationer. ${\ displaystyle f \ circ g}$

De følgende eksempler illustrerer, at en funktion kan beregnes, selvom det ikke vides, hvilken algoritme der beregner den.

• Funktionen f sådan, at f ( n ) = 1, hvis der er en sekvens af mindst n på hinanden følgende fem i decimaludvidelsen af π , og f ( n ) = 0 ellers, kan beregnes. (Funktionen f er enten konstant 1 -funktionen, som kan beregnes, eller også er der en k, så f ( n ) = 1 hvis n < k og f ( n ) = 0 hvis n ≥ k . Hver sådan funktion kan beregnes . Det vides ikke, om der er vilkårligt lange femkørsler i decimaludvidelsen af ​​π, så vi ved ikke, hvilken af disse funktioner der er f . Ikke desto mindre ved vi, at funktionen f skal kunne beregnes.)
• Hvert endeligt segment af en un beregnelige sekvens af naturlige tal (såsom Busy Beaver funktion Σ ) beregningsmetode. F.eks. Findes der for hvert naturligt tal n en algoritme, der beregner den endelige sekvens Σ (0), Σ (1), Σ (2), ..., Σ ( n ) - i modsætning til at der ikke er nogen algoritme, der beregner hele Σ-sekvensen, dvs. Σ ( n ) for alle n . Således er "Print 0, 1, 4, 6, 13" en triviel algoritme til beregning af Σ (0), Σ (1), Σ (2), Σ (3), Σ (4); På samme måde eksisterer en sådan triviel algoritme for en given værdi af n (selvom det måske aldrig er kendt eller produceret af nogen) til at beregne Σ (0), Σ (1), Σ (2), ..., Σ ( n ).

Kirke -Turing -afhandling

De Church-Turing-tesen hedder, at enhver funktion beregnelige fra en procedure, der har de tre ejendomme opført ovenfor er en beregnelig funktion. Fordi disse tre ejendomme ikke formelt er angivet, kan kirke -Turing -tesen ikke bevises. Følgende fakta tages ofte som bevis for afhandlingen:

• Mange ækvivalente beregningsmodeller kendes, og de giver alle den samme definition af beregningsfunktion (eller en svagere version, i nogle tilfælde).
• Der er ikke blevet foreslået en stærkere beregningsmodel, der generelt anses for effektivt at kunne beregnes .

Church -Turing -tesen bruges undertiden i beviser til at retfærdiggøre, at en bestemt funktion kan beregnes ved at give en konkret beskrivelse af en procedure for beregningen. Dette er tilladt, fordi det menes, at alle sådanne anvendelser af afhandlingen kan fjernes ved den kedelige proces at skrive en formel procedure for funktionen i en eller anden beregningsmodel.

Tilgængelighed

I betragtning af en funktion (eller på lignende måde et sæt) kan man være interesseret ikke kun, hvis det kan beregnes, men også om dette kan bevises i et bestemt bevissystem (normalt Peano -aritmetik i første ordre ). En funktion, der kan bevises at være beregningsbar, kaldes beviseligt total .

Sættet med beviseligt samlede funktioner er rekursivt tællende : man kan opregne alle de beviseligt samlede funktioner ved at opregne alle deres tilsvarende beviser, der beviser deres beregning. Dette kan gøres ved at optælle alle beviser i bevissystemet og ignorere irrelevante.

Forhold til rekursivt definerede funktioner

I en funktion, der er defineret af en rekursiv definition , er hver værdi defineret af en fast førsteordens formel for andre, tidligere definerede værdier for den samme funktion eller andre funktioner, som simpelthen kan være konstanter. En delmængde af disse er de primitive rekursive funktioner . Hver sådan funktion er beviseligt total: For sådan en k-ary- funktion f kan hver værdi beregnes ved at følge definitionen bagud, iterativt, og efter endeligt antal iterationer (som let kan bevises), nås en konstant. ${\ displaystyle f (n_ {1}, n_ {2} ... n_ {k})}$

Det omvendte er ikke sandt, da ikke alle beviseligt samlede funktioner er primitive rekursive. Faktisk kan man opregne alle de primitive rekursive funktioner og definere en funktion en sådan, at for alle n , m : en ( n , m ) = f _n ( m ), hvor f _n er den n-th primitive rekursive funktion (for k -ary -funktioner, indstilles dette til f _n ( m , m ... m )). Nu er g ( n ) = da ( n , n ) +1 beviseligt total, men ikke primitiv rekursiv, ved et diagonaliseringsargument : havde der været en j sådan, at g = f _j , ville vi have fået g ( j ) = en ( j , j ) +1 = f _j ( j )+1 = g ( j ) +1, en modsætning. ( Gödel -tallene for alle primitive rekursive funktioner kan opregnes med en primitiv rekursiv funktion, selvom de primitive rekursive funktioners værdier ikke kan.)

En sådan funktion, som kan bevises total, men ikke primitiv rekursiv, er Ackermann -funktionen : da den er rekursivt defineret, er det faktisk let at bevise dens beregning (Dog kan et lignende diagonaliseringsargument også bygges for alle funktioner defineret ved rekursiv definition ; der er således beviselige samlede funktioner, der ikke kan defineres rekursivt).

Samlede funktioner, der ikke beviseligt er samlede

I et lydisoleret system er hver beviseligt totalfunktion faktisk total, men det modsatte er ikke sandt: i hvert førsteordens bevissystem, der er stærkt nok og sundt (inklusive Peano-aritmetik), kan man bevise (i et andet bevissystem) eksistensen af ​​samlede funktioner, der ikke kan bevises total i bevissystemet.

Hvis de samlede beregningsfunktioner er opregnet via de Turing -maskiner, der producerer dem, kan ovenstående sætning, hvis bevissystemet er forsvarligt, vises med et lignende diagonaliseringsargument som det, der blev brugt ovenfor, ved hjælp af optællingen af ​​beviseligt samlede funktioner givet tidligere. Man bruger en Turing -maskine, der opregner de relevante beviser, og for hvert input kalder n f _n ( n ) (hvor f _n er n -th funktion ved denne optælling) ved at påberåbe Turing -maskinen, der beregner den i henhold til n -th bevis . Sådan en Turing -maskine standser garanteret, hvis bevissystemet er forsvarligt.

Ukomputable funktioner og uløselige problemer

Hver beregningsfunktion har en endelig procedure, der giver eksplicitte, entydige instruktioner om, hvordan den skal beregnes. Desuden denne fremgangsmåde har, der skal kodes i det endelige alfabet, der anvendes af den beregningsmæssige model, så der er kun tælleligt mange beregnelige funktioner. Funktioner kan f.eks. Være kodet ved hjælp af en streng bit (alfabetet Σ = {0, 1 }).

De reelle tal er utallige, så de fleste reelle tal kan ikke beregnes. Se beregningsnummer . Sættet af endelige funktioner på de naturlige tal er utallige, så de fleste kan ikke beregnes. Konkrete eksempler på sådanne funktioner er Busy beaver , Kolmogorov -kompleksitet eller enhver funktion, der udsender cifrene i et ikke -beregningsbart tal, såsom Chaitins konstant .

På samme måde kan de fleste undersæt af de naturlige tal ikke beregnes. Den standse problem var den første af disse sæt beregnes. Den Entscheidungsproblem , foreslået af David Hilbert , spurgt, om der er en effektiv procedure til at afgøre, hvilke matematiske udsagn (kodet som naturlige tal) er sande. Turing og Kirke viste uafhængigt i 1930'erne, at dette sæt naturlige tal ikke kan beregnes. Ifølge kirke -Turing -tesen er der ingen effektiv procedure (med en algoritme), der kan udføre disse beregninger.

Udvidelser af beregningsbarhed

Relativ beregningsevne

Begrebet beregnelighed af en funktion kan relativeres til en vilkårlig sæt af naturlige tal A . En funktion f er defineret til at kunne beregnes i A (ækvivalent A -computer eller beregningsbar i forhold til A ), når den opfylder definitionen af ​​en beregningsbar funktion med modifikationer, der giver adgang til A som et orakel . Som med begrebet en beregningsbar funktion kan relativ beregning gives tilsvarende definitioner i mange forskellige beregningsmodeller. Dette er almindeligt opnås ved at supplere den model af beregning med en yderligere primitiv operation, som spørger, om en given heltal er medlem af A . Vi kan også tale om, at f kan beregnes i g ved at identificere g med dets graf.

Højere rekursionsteori

Hyperaritmetisk teori studerer de sæt, der kan beregnes ud fra et beregningsværdigt antal iterater af Turing -springet i det tomme sæt. Dette svarer til sæt defineret af både en universel og eksistentiel formel på sproget i anden ordens aritmetik og til nogle modeller af hypercomputation . Endnu mere generelle rekursionsteorier er blevet undersøgt, såsom E-rekursionsteori , hvor ethvert sæt kan bruges som argument til en E-rekursiv funktion.

Hyper-beregning

Selvom kirke -Turing -tesen siger, at de beregningsfunktioner omfatter alle funktioner med algoritmer, er det muligt at overveje bredere klasser af funktioner, der slækker de krav, algoritmer skal have. Feltet af Hypercomputation undersøgelser modeller for beregning, der går ud over normal Turing beregning.

Se også

• Beregneligt nummer
• Effektiv metode
• Beregningsteori
• Rekursionsteori
• Turing grad
• Aritmetisk hierarki
• Hypercomputation
• Super-rekursiv algoritme
• Semicomputable funktion

Referencer

• Cutland, Nigel. Beregnelighed . Cambridge University Press, 1980.
• Enderton, HB Elementer af rekursionsteori. Handbook of Mathematical Logic (Nordholland 1977) s. 527–566.
• Rogers, H. Teori om rekursive funktioner og effektiv beregning (McGraw – Hill 1967).
• Turing, A. (1937), Om beregningsnumre, med en applikation til Entscheidungsproblemet . Proceedings of the London Mathematical Society , Series 2, bind 42 (1937), s.230–265. Genoptrykt i M. Davis (red.), The Undecidable , Raven Press, Hewlett, NY, 1965.