Stop problem - Halting problem

I beregningsteorien er stoppeproblemet problemet med at bestemme ud fra en beskrivelse af et vilkårligt computerprogram og et input, om programmet vil afslutte at køre eller fortsætte med at køre for evigt. Alan Turing beviste i 1936, at en generel algoritme til at løse stoppeproblemet for alle mulige program-input-par ikke kan eksistere.

For ethvert program f, der kan afgøre, om programmer standser, kan et "patologisk" program g , kaldet med noget input, videregive sin egen kilde og sit input til f og derefter specifikt gøre det modsatte af, hvad f forudsiger, g vil gøre. Der kan ikke eksistere f , der håndterer denne sag. En vigtig del af beviset er en matematisk definition af en computer og et program, der er kendt som en Turing -maskine ; standsningsproblemet er uafgjort over Turing -maskiner. Det er et af de første tilfælde af beslutningsproblemer, der har vist sig at være uløselige. Dette bevis er vigtigt for praktisk computingindsats og definerer en klasse af applikationer, som ingen programmeringsopfindelse muligvis kan udføre perfekt.

Jack Copeland (2004) tilskriver indførelsen af ​​begrebet halting problem til Martin Davis arbejde i 1950'erne.

Baggrund

Stopproblemet er et beslutningsproblem om egenskaber ved computerprogrammer på en fast Turing-komplet beregningsmodel, det vil sige alle programmer, der kan skrives i et givet programmeringssprog, der er generelt nok til at svare til en Turing-maskine. Problemet er at bestemme, givet et program og et input til programmet, om programmet i sidste ende vil stoppe, når det køres med det pågældende input. I denne abstrakte ramme er der ingen ressourcebegrænsninger for mængden af ​​hukommelse eller tid, der kræves til programmets udførelse; det kan tage vilkårligt lang tid og bruge en vilkårlig mængde lagerplads, før den standses. Spørgsmålet er simpelthen, om det givne program nogensinde vil standse et bestemt input.

For eksempel i pseudokode , programmet

while (true) continue

stopper ikke; den fortsætter snarere for evigt i en uendelig loop . På den anden side programmet

print "Hello, world!"

stopper.

Selvom det er enkelt at beslutte, om disse programmer skal standses, viser mere komplekse programmer sig at være problematiske. En tilgang til problemet kan være at køre programmet i et antal trin og kontrollere, om det stopper. Men hvis programmet ikke standser, er det uvist, om programmet i sidste ende vil stoppe eller køre for evigt. Turing viste, at der ikke findes nogen algoritme, der altid korrekt afgør, om programmet for et givet vilkårligt program og input stopper, når det køres med dette input. Essensen i Turings bevis er, at enhver sådan algoritme kan laves til at modsige sig selv og derfor ikke kan være korrekt.

Programmeringskonsekvenser

Nogle uendelige sløjfer kan være ganske nyttige. For eksempel er hændelsesløkker typisk kodet som uendelige sløjfer. De fleste underprogrammer er dog beregnet til at afslutte (standse). Især i hård real-time computing forsøger programmører at skrive underrutiner, der ikke kun garanteres at afslutte (standse), men også garanteres at blive færdige inden en given deadline.

Nogle gange bruger disse programmører et generelt programmeringssprog (Turing-complete), men forsøger at skrive i en begrænset stil-f.eks. MISRA C eller SPARK-hvilket gør det let at bevise, at de resulterende underrutiner slutter inden den givne deadline.

Andre gange anvender disse programmører reglen om mindste magt- de bruger bevidst et computersprog, der ikke helt er fuldstændigt Turing-komplet. Ofte er dette sprog, der garanterer, at alle underrutiner er færdige, f.eks. Coq .

Fælles faldgruber

Vanskeligheden ved at standse problemet ligger i kravet om, at beslutningsproceduren skal fungere for alle programmer og input. Et bestemt program stopper enten på et givet input eller stopper ikke. Overvej en algoritme, der altid svarer "stopper" og en anden, der altid svarer "stopper ikke". For ethvert specifikt program og input svarer en af ​​disse to algoritmer korrekt, selvom ingen måske ved hvilken. Alligevel løser ingen af ​​algoritmerne generelt standsningsproblemet.

Der er programmer ( tolke ), der simulerer udførelsen af ​​den kildekode, de får. Sådanne programmer kan demonstrere, at et program standser, hvis dette er tilfældet: tolken selv vil i sidste ende standse sin simulering, hvilket viser, at det originale program stoppede. En tolk stopper imidlertid ikke, hvis dets inputprogram ikke stopper, så denne fremgangsmåde kan ikke løse standsningsproblemet som anført; det svarer ikke med succes "stopper ikke" for programmer, der ikke standser.

Stopproblemet kan teoretisk afgøres for lineære afgrænsede automater (LBA'er) eller deterministiske maskiner med begrænset hukommelse. En maskine med begrænset hukommelse har et begrænset antal konfigurationer, og derfor skal ethvert deterministisk program på det i sidste ende enten standse eller gentage en tidligere konfiguration:

... enhver endelig-tilstandsmaskine, hvis den overlades helt til sig selv, vil til sidst falde i et perfekt periodisk gentaget mønster . Varigheden af ​​dette gentagende mønster kan ikke overstige antallet af interne tilstande på maskinen ... (kursiv i original, Minsky 1967, s. 24)

Minsky bemærker imidlertid, at en computer med en million små dele, hver med to stater, ville have mindst 2 ^1.000.000 mulige tilstande:

Dette er et 1 efterfulgt af omkring tre hundrede tusinde nuller ... Selvom en sådan maskine skulle fungere ved frekvenserne af kosmiske stråler, ville galakseudviklingens æoner være intet sammenlignet med tidspunktet for en rejse gennem en sådan cyklus ( Minsky 1967 s.25):

Minsky udtaler, at selv om en maskine kan være begrænset, og endelige automater "har en række teoretiske begrænsninger":

... de involverede størrelser bør få en til at mistanke om, at sætninger og argumenter, der hovedsageligt er baseret på det endelige [i] statsdiagrammet, muligvis ikke har stor betydning. (Minsky s. 25)

Det kan også automatisk afgøres, om en ikke -bestemmende maskine med begrænset hukommelse standser ingen, nogle eller alle de mulige sekvenser af ikke -bestemmende beslutninger ved at opregne tilstande efter hver mulig beslutning.

Historie

Stopproblemet er historisk vigtigt, fordi det var et af de første problemer, der skulle bevises uafklareligt . (Turings bevis gik i trykken i maj 1936, hvorimod Alonzo Kirkes bevis på et ubeslutsomheds problem i lambda -regningen allerede var blevet offentliggjort i april 1936 [Kirke, 1936].) Efterfølgende er mange andre uafklarbare problemer blevet beskrevet.

Tidslinje

• 1900: David Hilbert stiller sine "23 spørgsmål" (nu kendt som Hilberts problemer ) på den anden internationale matematikerkongres i Paris. "Af disse var det andet bevis for konsistensen af ​​de" Peano -aksiomer ", som han, som han havde vist, matematikkens stringens afhængede af". (Hodges s. 83, Davis 'kommentar i Davis, 1965, s. 108)
• 1920–1921: Emil Post undersøger stopproblemet for tagsystemer og betragter det som en kandidat til uløselighed. ( Absolut uløselige problemer og forholdsvis uafgjort beslutninger - redegørelse for en forventning i Davis, 1965, s. 340–433.) Dens uløselighed blev først fastslået meget senere af Marvin Minsky (1967).
• 1928: Hilbert omarbejder sit 'andet problem' på Bologna International Congress. (Reid s. 188–189) Hodges hævder, at han stillede tre spørgsmål: dvs. #1: Var matematik fuldendt ? #2: Var matematik konsekvent ? #3: Kan matematik afgøres ? (Hodges s. 91). Det tredje spørgsmål er kendt som Entscheidungsproblemet (beslutningsproblem). (Hodges s. 91, Penrose s. 34)
• 1930: Kurt Gödel meddeler et bevis som svar på de to første af Hilberts spørgsmål fra 1928 [jf. Reid s. 198]. "Først var han [Hilbert] kun vred og frustreret, men derefter begyndte han at forsøge at håndtere konstruktivt problemet ... Gödel følte - og udtrykte tanken i sit papir - at hans arbejde ikke modsagde Hilberts formalistiske pointe om se "(Reid s. 199)
• 1931: Gödel udgiver "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I", (genoptrykt i Davis, 1965, s. 5ff)
• 19. april 1935: Alonzo Church udgiver "An Unsolvable Problem of Elementary Number Theory", som foreslår, at den intuitive forestilling om en effektivt beregningsbar funktion kan formaliseres af de generelle rekursive funktioner eller ækvivalent af de lambda-definerbare funktioner . Han beviser, at stopproblemet for lambda-beregning (dvs. om et givet lambda-udtryk har en normal form ) ikke er effektivt beregningsbart.
• 1936: Kirken offentliggør det første bevis på, at Entscheidungsproblemet er uløseligt. ( En note om Entscheidungsproblemet , genoptrykt i Davis, 1965, s. 110.)
• 7. oktober 1936: Emil Posts papir "Endelige kombinationsprocesser. Formulering I" modtages. Post tilføjer til sin "proces" en instruktion "(C) Stop". Han kaldte en sådan proces "type 1 ... hvis den proces, den bestemmer, slutter for hvert specifikt problem." (Davis, 1965, s. 289ff)
• 1937: Alan Turings papir om Computable Numbers With an Application to the Entscheidungsproblem når ud i januar 1937 (genoptrykt i Davis, 1965, s. 115). Turings bevis afviger fra beregning ved hjælp af rekursive funktioner og introducerer forestillingen om beregning efter maskine. Stephen Kleene (1952) omtaler dette som et af de "første eksempler på beslutningsproblemer, der viste sig at være uløselige".
• 1939: J. Barkley Rosser observerer den væsentlige ækvivalens af "effektiv metode" defineret af Gödel, Church og Turing (Rosser i Davis, 1965, s. 223, "Informal Exposition of Proofs of Gödel's Theorem and Church's Theorem")
• 1943: I et papir udtaler Stephen Kleene , at "Ved oprettelsen af ​​en komplet algoritmisk teori er det, vi gør, at beskrive en procedure ... hvilken procedure nødvendigvis afsluttes og på en sådan måde, at vi ud fra resultatet kan læse et bestemt svar, 'Ja 'eller' Nej 'til spørgsmålet' Er prædikatværdien sand? '. "
• 1952: Kleene (1952) Kapitel XIII ("Computable Functions") inkluderer en diskussion af uløseligheden af ​​stopproblemet for Turing -maskiner og omformulerer det i form af maskiner, der "til sidst stopper", dvs. standser: "... der er ingen algoritme til at afgøre, om en given maskine, når den startes fra en given situation, i sidste ende stopper . " (Kleene (1952) s. 382)
• 1952: " Martin Davis mener det sandsynligt, at han først brugte udtrykket 'standsningsproblem' i en række foredrag, som han holdt på Control Systems Laboratory ved University of Illinois i 1952 (brev fra Davis til Copeland, 12. december 2001). " (Fodnote 61 i Copeland (2004) s. 40ff)

Formalisering

I sit originale bevis formaliserede Turing begrebet algoritme ved at introducere Turing -maskiner . Resultatet er dog på ingen måde specifikt for dem; det gælder ligeledes enhver anden beregningsmodel , der i sin beregningsevne er ækvivalent med Turing -maskiner, såsom Markov -algoritmer , Lambda -beregning , Postsystemer , registermaskiner eller mærkesystemer .

Det, der er vigtigt, er, at formaliseringen tillader en ligetil kortlægning af algoritmer til en datatype , som algoritmen kan operere på. For eksempel, hvis formalismen lader algoritmer definere funktioner over strenge (f.eks. Turing -maskiner), bør der være en kortlægning af disse algoritmer til strenge, og hvis formalismen lader algoritmer definere funktioner over naturlige tal (f.eks. Beregningsfunktioner ), skal der være en kortlægning af algoritmer til naturlige tal. Kortlægningen til strenge er normalt den mest ligetil, men strenge over et alfabet med n tegn kan også knyttes til tal ved at fortolke dem som tal i et n -numerisk system .

Repræsentation som et sæt

Den konventionelle repræsentation af beslutningsproblemer er det sæt objekter, der besidder den pågældende ejendom. Den standse sæt

K = {( i , x ) | program stopper jeg, når det køres på input x }

repræsenterer det stoppende problem.

Dette sæt kan rekursivt tælles , hvilket betyder, at der er en beregningsfunktion, der viser alle de par ( i ,  x ), det indeholder. Suppleringen af ​​dette sæt er imidlertid ikke rekursivt tællende.

Der er mange ækvivalente formuleringer af stopproblemet; ethvert sæt, hvis Turing -grad svarer til stopproblemets, er en sådan formulering. Eksempler på sådanne sæt inkluderer:

• { i | program stopper jeg til sidst, når det køres med input 0}
• { i | der er et input x sådan, at programmet i sidste ende stopper, når det køres med input x }.

Bevisskoncept

Christopher Strachey skitserede et bevis ved modsigelse af , at stopproblemet ikke er løseligt. Beviset forløber som følger: Antag, at der eksisterer en total beregningsbar funktionsstop (f), der returnerer sand, hvis underrutinen f stopper (når den køres uden input) og returnerer falsk ellers. Overvej nu følgende underprogram:

def g():
    if halts(g):
        loop_forever()

stop (g) skal enten returnere true eller false, fordi stop blev antaget at være total . Hvis stop (g) returnerer true, kalder g loop_forever og stopper aldrig, hvilket er en modsigelse. Hvis stopper (g) returnerer false, så g vil standse, fordi det ikke vil kalde loop_forever ; dette er også en modsætning. Samlet set gør g det modsatte af, hvad stopper siger, at g skal gøre, så stop (g) kan ikke returnere en sandhedsværdi, der er i overensstemmelse med, om g stopper. Derfor må den indledende antagelse om, at standsning er en samlet beregningsfunktion, være falsk.

Skitse af strenge beviser

Konceptet ovenfor viser bevisets generelle metode, men den beregnelige funktion stopper ikke direkte en underprogram som et argument; i stedet tager det kildekoden til et program. Desuden er definitionen af g er selvrefererende . Et grundigt bevis løser disse spørgsmål. Det overordnede mål er at vise, at der ikke er alt beregnelig funktion , der afgør, om et vilkårligt program I stopper på vilkårlige input x ; det vil sige, at følgende funktion h (for "stop") ikke kan beregnes (Penrose 1990, s. 57–63):

${\ displaystyle h (i, x) = {\ begin {cases} 1 & {\ text {if}} {\ text {program}} i {\ text {stopper ved input}} x, \\ 0 & {\ text { ellers.}} \ end {cases}}}$

Her refererer program i til det i program i en optælling af alle programmerne i en fast Turing-komplet beregningsmodel.

Beviset fortsætter ved direkte at fastslå, at ingen samlet beregningsfunktion med to argumenter kan være den nødvendige funktion h . Som i skitsen af ​​konceptet, givet enhver total beregningsbar binær funktion f , kan følgende delfunktion g også beregnes af et program e :

${\ displaystyle g (i) = {\ begin {cases} 0 & {\ text {if}} f (i, i) = 0, \\ {\ text {undefined}} & {\ text {ellers.}} \ slut {cases}}}$

Verifikationen af, at g kan beregnes, afhænger af følgende konstruktioner (eller deres ækvivalenter):

• beregningsbare underprogrammer (det program, der beregner f er et underprogram i program e ),
• dobbeltværdier (program e beregner input i , i for f fra input i for g ),
• betinget forgrening (program e vælger mellem to resultater afhængigt af den værdi, det beregner for f ( i , i )),
• ikke producerer et defineret resultat (for eksempel ved at loopes for evigt),
• returnerer værdien 0.

Følgende pseudokode illustrerer en ligetil måde at beregne g :

procedure compute_g(i):
    if f(i, i) == 0 then
        return 0
    else
        loop forever

Fordi g er delvis beregningsbar, skal der være et program e, der beregner g , under forudsætning af, at beregningsmodellen er Turing-komplet. Dette program er et af alle de programmer, som standsefunktionen h er defineret på. Det næste trin i beviset viser, at h ( e , e ) ikke vil have den samme værdi som f ( e , e ).

Det følger af definitionen af g, at nøjagtigt en af ​​de følgende to sager skal gælde:

• f ( e , e ) = 0 og så g ( e ) = 0. I dette tilfælde h ( e , e ) = 1, fordi program e stopper på input e .
• f ( e , e ) ≠ 0 og så g ( e ) er udefineret. I dette tilfælde h ( e , e ) = 0, fordi program e ikke standser input e .

I begge tilfælde kan f ikke være den samme funktion som h . Fordi f var en vilkårlig total beregningsfunktion med to argumenter, skal alle sådanne funktioner afvige fra h .

Dette bevis er analogt med Cantors diagonale argument . Man kan visualisere et todimensionalt array med en kolonne og en række for hvert naturligt tal, som angivet i tabellen ovenfor. Værdien af f ( i , j ) er placeret i kolonne i , række j . Fordi f formodes at være en samlet beregningsfunktion, kan ethvert element i arrayet beregnes ved hjælp af f . Konstruktionen af ​​funktionen g kan visualiseres ved hjælp af hoveddiagonalen i dette array. Hvis arrayet har en 0 på position ( i , i ), så er g ( i ) 0. Ellers er g ( i ) udefineret. Modsigelsen kommer af, at der er en kolonne e i arrayet, der svarer til g selv. Antag nu, at f var standsefunktionen h , hvis g ( e ) er defineret ( g ( e ) = 0 i dette tilfælde), stopper g ( e ) så f ( e, e ) = 1. Men g ( e ) = 0 kun når f ( e, e ) = 0, modsiger f ( e, e ) = 1. På samme måde, hvis g ( e ) ikke er defineret, så standser funktionen f ( e, e ) = 0, hvilket fører til g ( e ) = 0 under g 's konstruktion. Dette modsiger antagelsen om, at g ( e ) ikke defineres. I begge tilfælde opstår der modsætning. Derfor kan enhver vilkårlig beregningsfunktion f ikke være standsefunktionen h .

Beregningsteori

En typisk metode til at bevise, at et problem er uafgjort, er at reducere det til standsningsproblemet. For eksempel kan der ikke være en generel algoritme, der afgør, om en given sætning om naturlige tal er sand eller falsk. Grunden til dette er, at forslaget om, at et bestemt program vil standse givet et bestemt input, kan konverteres til en tilsvarende erklæring om naturlige tal. Hvis en algoritme kunne finde sandhedsværdien af ​​hver sætning om naturlige tal, kunne den helt sikkert finde sandhedsværdien af ​​denne; men det ville afgøre, om det originale program standser.

Rices sætning generaliserer sætningen om, at standsningsproblemet er uløseligt. Det hedder, at for enhver ikke-triviel ejendom er der ingen generel beslutningsprocedure, der for alle programmer afgør, om den delfunktion, der er implementeret af inputprogrammet, har denne egenskab. (En delfunktion er en funktion, der muligvis ikke altid giver et resultat, og derfor bruges til at modellere programmer, som enten kan producere resultater eller ikke standse.) For eksempel er egenskaben "stop for input 0" ikke bestemt. Her betyder "ikke-trivielt", at sættet med delfunktioner, der opfylder ejendommen, hverken er det tomme sæt eller sættet for alle delfunktioner. For eksempel er "stopper eller ikke standser på input 0" klart for alle delfunktioner, så det er en triviel egenskab og kan afgøres af en algoritme, der simpelthen rapporterer "sand". Denne sætning gælder også kun for egenskaber ved delfunktionen implementeret af programmet; Rices sætning gælder ikke for selve programmets egenskaber. For eksempel er "stop på input 0 inden for 100 trin" ikke en egenskab ved den delfunktion, der implementeres af programmet - det er en egenskab for programmet, der implementerer delfunktionen og kan i høj grad afgøres.

Gregory Chaitin har defineret en stoppende sandsynlighed , repræsenteret ved symbolet Ω , en type reelt tal, der uformelt siges at repræsentere sandsynligheden for, at et tilfældigt produceret program stopper. Disse tal har samme Turing -grad som stopproblemet. Det er et normalt og transcendentalt tal, der kan defineres, men ikke kan beregnes fuldstændigt . Det betyder, at man kan bevise, at der ikke er nogen algoritme, der producerer cifrene i Ω, selvom de første få cifre kan beregnes i enkle tilfælde.

Selvom Turings bevis viser, at der ikke kan være nogen generel metode eller algoritme til at afgøre, om algoritmer standser, kan enkelte tilfælde af dette problem meget vel være modtagelige for angreb. I betragtning af en specifik algoritme kan man ofte vise, at den skal standse for ethvert input, og faktisk gør computerforskere ofte netop det som en del af et korrekthedsbevis . Men hvert bevis skal udvikles specifikt til algoritmen ved hånden; der er ingen mekanisk, generel måde at afgøre, om algoritmer på en Turing -maskine standser. Der er dog nogle heuristikker, der kan bruges på en automatisk måde til at forsøge at konstruere et bevis, som ofte lykkes på typiske programmer. Dette forskningsfelt er kendt som automatiseret termineringsanalyse .

Da det negative svar på standsningsproblemet viser, at der er problemer, der ikke kan løses med en Turing -maskine, begrænser kirke -Turing -afhandlingen , hvad der kan opnås med enhver maskine, der implementerer effektive metoder . Imidlertid er ikke alle maskiner, der kan tænkes i menneskelig fantasi, underlagt kirken -Turing -tesen (f.eks. Orakelmaskiner ). Det er et åbent spørgsmål, om der kan være faktiske deterministiske fysiske processer , der på sigt undgår simulering af en Turing -maskine, og især om en sådan hypotetisk proces med fordel kan udnyttes i form af en beregningsmaskine (en hypercomputer ) det kunne blandt andet løse stopproblemet for en Turing -maskine. Det er også et åbent spørgsmål om, hvorvidt sådanne ukendte fysiske processer er involveret i den menneskelige hjernes funktion , og om mennesker kan løse stopproblemet (Copeland 2004, s. 15).

Gödels ufuldstændighedssætninger

Begreberne, der rejses ved Gödel's ufuldstændighedssætninger, ligner meget dem, der blev rejst af stopproblemet, og beviserne er ret ens. Faktisk er en svagere form af den første ufuldstændighedssætning en let konsekvens af det ubeslutsomhed, der er ved at standse problemet. Denne svagere form adskiller sig fra standarderklæringen om ufuldstændighedssætningen ved at hævde, at en aksiomatisering af de naturlige tal, der er både fuldstændig og sund, er umulig. "Lyd" -delen er svækkelsen: det betyder, at vi kræver, at det pågældende aksiomatiske system kun beviser sande udsagn om naturlige tal. Da sundhed indebærer konsistens , kan denne svagere form ses som en følge af den stærke form. Det er vigtigt at bemærke, at udsagnet om standardformen for Gödel's første ufuldstændighedssætning er fuldstændig ligeglad med sandhedsværdien af ​​et udsagn, men kun vedrører spørgsmålet om, hvorvidt det er muligt at finde det gennem et matematisk bevis .

Sætningens svagere form kan bevises ud fra stop -problemets ubestemmelighed som følger. Antag, at vi har en sund (og dermed konsekvent) og fuldstændig aksiomatisering af alle sande førsteordens logiske udsagn om naturlige tal . Derefter kan vi bygge en algoritme, der opregner alle disse udsagn. Dette betyder, at der er en algoritme N ( n ), der givet et naturligt tal n , beregner en sand førsteordens logisk sætning om naturlige tal, og at der for alle sande udsagn er mindst én n sådan, at N ( n ) giver den erklæring. Antag nu, at vi vil beslutte, om algoritmen med repræsentation a standser input jeg . Vi ved, at denne erklæring kan udtrykkes med en førsteordens logisk sætning, siger H ( a , i ). Da aksiomatiseringen er fuldendt, følger det, at der enten er et n, således at N ( n ) = H ( a , i ) eller der er en n ' sådan, at N ( n' ) = ¬ H ( a , i ). Så hvis vi gentager alle n, indtil vi enten finder H ( a , i ) eller dens negation, vil vi altid stoppe, og endvidere vil svaret, det giver os, være sandt (ved sundhed). Det betyder, at dette giver os en algoritme til at afgøre stopproblemet. Da vi ved, at der ikke kan være en sådan algoritme, følger det, at antagelsen om, at der er en konsekvent og fuldstændig aksiomatisering af alle sande førsteordens logiske udsagn om naturlige tal, skal være falsk.

Generalisering

Mange varianter af stopproblemet findes i beregningsbøger (f.eks. Sipser 2006, Davis 1958, Minsky 1967, Hopcroft og Ullman 1979, Börger 1989). Typisk følger deres ubeslutsomhed ved reduktion fra standardstopproblemet. Nogle af dem har imidlertid en højere grad af uløselighed . De næste to eksempler er typiske.

Stop for alle input

Det universelle stopproblem , også kendt (i rekursionsteori ) som totalitet , er problemet med at afgøre, om et givet computerprogram vil stoppe for hvert input (navnet totalitet kommer fra det tilsvarende spørgsmål om, hvorvidt den beregnede funktion er total ). Dette problem er ikke kun ubeslutsomt, som stopproblemet, men meget uafgjort. Med hensyn til det aritmetiske hierarki er det -komplet (Börger 1989, s. 121). ${\ displaystyle \ Pi _ {2}^{0}}$

Dette betyder især, at det ikke kan afgøres selv med et orakel for at standse problemet.

Anerkendelse af delvise løsninger

Der er mange programmer, der for nogle input returnerer et korrekt svar på stopproblemet, mens de for andre input slet ikke returnerer et svar. Men problemet "givet program p , er det en delvis standsning -løsning" (i den beskrevne betydning) er mindst lige så hårdt som stopproblemet. For at se dette skal du antage, at der er en algoritme PHSR ("delvis standsning af løsningsgenkender") til at gøre det. Derefter kan det bruges til at løse stopproblemet som følger: For at teste om inputprogram x stopper på y , konstruer et program p, der på input ( x , y ) rapporterer sandt og afviger fra alle andre input. Test derefter p med PHSR.

Ovenstående argument er en reduktion af stopproblemet til PHS -genkendelse, og på samme måde kan hårdere problemer som f.eks. Standsning af alle input også reduceres, hvilket indebærer, at PHS -genkendelse ikke kun er uafgjort, men højere i det aritmetiske hierarki , specifikt -komplet. ${\ displaystyle \ Pi _ {2}^{0}}$

Tabt beregning

En tabende Turing-maskine er en Turing-maskine, hvor en del af båndet ikke-deterministisk kan forsvinde. Haltningsproblemet kan afgøres til tabende Turing-maskine, men ikke- primitiv rekursiv .

Oracle maskiner

En maskine med et orakel til standsningsproblemet kan afgøre, om bestemte Turing -maskiner standser på bestemte input, men de kan generelt ikke afgøre, om maskiner svarende til dem selv standser.

Se også

• Travl bæver
• Gödels ufuldstændighedssætning
• Brouwer-Hilbert kontrovers
• Kolmogorov kompleksitet
• P versus NP problem
• Opsigelsesanalyse
• Udførelsestid i værste tilfælde

Noter

Referencer

• Turing, AM (1937). "Om beregningsnumre, med en applikation til Entscheidungsproblemet" . Proceedings of the London Mathematical Society . Wiley. s2-42 (1): 230–265. doi : 10.1112/plms/s2-42.1.230 . ISSN  0024-6115 ., Turing, AM (1938). "Om beregningsnumre, med en applikation til Entscheidungsproblemet. En rettelse" . Proceedings of the London Mathematical Society . Wiley. s2-43 (1): 544–546. doi : 10.1112/plms/s2-43.6.544 . ISSN  0024-6115 .Dette er det epokale papir, hvor Turing definerer Turing -maskiner , formulerer stoppeproblemet og viser, at det (såvel som Entscheidungsproblemet ) er uløseligt.
• Sipser, Michael (2006). "Afsnit 4.2: Stopproblemet" . Introduktion til teorien om beregning (anden udgave). PWS Publishing. s.  173–182 . ISBN 0-534-94728-X.
• c2: Stopproblem
• Kirke, Alonzo (1936). "Et uløseligt problem med elementær talteori". American Journal of Mathematics . 58 (2): 345–363. doi : 10.2307/2371045 . JSTOR  2371045 .
• B. Jack Copeland red. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN  0-19-825079-7 .
• Davis, Martin (1965). De uafgørelige, grundlæggende papirer om uafgjort forslag, uløselige problemer og beregningsfunktioner . New York: Raven Press.. Turings papir er nr. 3 i dette bind. Papirer inkluderer dem af Godel, Church, Rosser, Kleene og Post.
• Davis, Martin (1958). Beregnelighed og uløselighed . New York: McGraw-Hill..
• Alfred North Whitehead og Bertrand Russell , Principia Mathematica til *56, Cambridge ved University Press, 1962. Ad: problemet med paradokser, diskuterer forfatterne problemet med et sæt, der ikke skal være et objekt i nogen af ​​dets "bestemmende funktioner", i særlig "Introduktion, kap. 1 s. 24" ... vanskeligheder, der opstår i formel logik ", og kap. 2.I." Princippet om ond cirkel "s. 37ff, og kap. 2.VIII." Modsætningerne "s. 60ff.
• Martin Davis , "What is a computation", i Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Et vidunderligt lille papir, måske det bedste, der nogensinde er skrevet om Turing Machines til den ikke-specialist. Davis reducerer Turing-maskinen til en langt enklere model baseret på Post's beregningsmodel. Diskuterer Chaitin -bevis . Inkluderer små biografier om Emil Post , Julia Robinson .
• Marvin Minsky , Computation: Finite and Infinite Machines , Prentice-Hall, Inc., NJ, 1967. Se kapitel 8, afsnit 8.2 "Uopløseligheden af ​​stopproblemet."
• Roger Penrose , The Emperor's New Mind: Angående computere, Minds and the Laws of Physics , Oxford University Press , Oxford England, 1990 (med rettelser). Jf. Kapitel 2, "Algoritmer og turningsmaskiner". En for kompliceret præsentation (se Davis's papir for en bedre model), men en grundig præsentation af Turing-maskiner og stopproblemet, og Kirkens Lambda Calculus.
• John Hopcroft og Jeffrey Ullman , Introduction to Automata Theory, Languages ​​and Computation , Addison-Wesley, Reading Mass, 1979. Se kapitel 7 "Turing Machines." En bog centreret omkring maskintolkning af "sprog", NP-fuldstændighed osv.
• Andrew Hodges , Alan Turing: The Enigma , Simon and Schuster , New York. Jf. Kapitel "Sandhedens ånd" for en historie, der fører til og en diskussion af hans bevis.
• Constance Reid , Hilbert , Copernicus: Springer-Verlag, New York, 1996 (første gang udgivet 1970). Fascinerende historie om tysk matematik og fysik fra 1880'erne til 1930'erne. Hundredvis af navne, der er velkendte for matematikere, fysikere og ingeniører, vises på dens sider. Måske ødelagt af ingen åbenlyse referencer og få fodnoter: Reid siger, at hendes kilder var talrige interviews med dem, der personligt kendte Hilbert, og Hilberts breve og papirer.
• Edward Beltrami , hvad er tilfældigt? Chance og orden i matematik og liv , Copernicus: Springer-Verlag, New York, 1999. Dejlig, blid læsning for den matematisk tilbøjelige ikke-specialist, sætter hårdere ting til sidst. Har en Turing-maskine model i den. Diskuterer Chaitin -bidragene .
• Moore, Cristopher ; Mertens, Stephan (2011), The Nature of Computation , Oxford University Press, ISBN 9780191620805
• Ernest Nagel og James R. Newman , Godels bevis , New York University Press, 1958. Fantastisk forfatterskab om et meget vanskeligt emne. For den matematisk tilbøjelige ikke-specialist. Diskuterer Gentzens bevis på side 96–97 og fodnoter. Bilagene diskuterer Peano -aksiomerne kort og introducerer læserne forsigtigt formel logik.
• Taylor Booth , Sequential Machines and Automata Theory , Wiley, New York, 1967. Jf. Kapitel 9, Turningsmaskiner. Vanskelig bog, beregnet til elektriske ingeniører og tekniske specialister. Diskuterer rekursion, delvis rekursion med henvisning til Turing Machines, standsningsproblem. Har en Turing Machine -model i sig. Henvisninger i slutningen af ​​kapitel 9 fanger de fleste af de ældre bøger (dvs. 1952 til 1967, herunder forfatterne Martin Davis, FC Hennie, H. Hermes, SC Kleene, M. Minsky, T. Rado) og forskellige tekniske artikler. Se note under Busy-Beaver-programmer.
• Travle bæverprogrammer er beskrevet i Scientific American, august 1984, også marts 1985 s. 23. En henvisning i Booth tilskriver dem Rado, T. (1962), On non-computable functions, Bell Systems Tech. J. 41. Booth definerer også Rados travle bæverproblem i problemerne 3, 4, 5, 6 i kapitel 9, s. 396.
• David Bolter , Turing's Man: Western Culture in the Computer Age , University of North Carolina Press, Chapel Hill, 1984. For den almindelige læser. Kan dateres. Har endnu en (meget enkel) Turing Machine -model i sig.
• Egon Börger. "Beregnelighed, kompleksitet, logik". Nordholland, 1989.
• Stephen Kleene , Introduction to Metamathematics , North-Holland, 1952. Kapitel XIII ("Computable Functions") indeholder en diskussion af uløseligheden af ​​stopproblemet for Turing-maskiner. I en afvigelse fra Turings terminologi for cirkelfrie ikke-holdbare maskiner henviser Kleene i stedet til maskiner, der "stopper", dvs. standser.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, Om tilnærmelse af stopproblemer i den virkelige verden , s. 454-466 (2005) ISBN  3540281932 Springer-forelæsningsnotater i datalogi bind 3623: Ubeslutsomhed om stopproblemet betyder, at ikke alle instanser kan besvares korrekt ; men måske "nogle", "mange" eller "de fleste" kan? På den ene side vil det konstante svar ”ja” være korrekt uendeligt ofte og forkert også uendeligt ofte. Overvej tætheden af de tilfælde, der kan løses, for at gøre spørgsmålet rimeligt . Dette viser sig at afhænge betydeligt af det pågældende programmeringssystem .
• Logiske begrænsninger for maskinetik med konsekvenser for dødelige autonome våben - papir diskuteret i: Betyder stopproblemet ingen moralske robotter?
• Nicholas J. Daras og Themistocles M. Rassias , Modern Discrete Mathematics and Analysis: with Applications in Cryptography, Information Systems and Modeling Springer, 2018. ISBN  978-3319743240 . Kapitel 3 Afsnit 1 indeholder en kvalitetsbeskrivelse af stopproblemet, et bevis ved modsigelse og en nyttig grafisk fremstilling af stopproblemet.

eksterne links

• Scooping the loop snooper - et poetisk bevis på ubeslutsomhed af stopproblemet
• animeret film - en animation, der forklarer beviset på, at stopproblemet ikke kan afgøres
• Et 2-minutters bevis på 2.-vigtigste sætning fra det 2. årtusinde -et bevis på kun 13 linjer