Saker Datorer Aldrig Kan Göra

Philip J. Erdelsky
Publicerades först i Dr. Dobb’s Journal Maj 1987

Skicka e-post till kommentarer, korrigeringar och tillägg till webbansvarig på [email protected]

Alla som har sett de enorma förbättringarna i datorer under de senaste 40 åren kan få intrycket att datorer så småningom kommer att kunna lösa alla väldefinierade problem. Framstegen när det gäller språkförståelse och andra former av konstgjord intelligens har varit en besvikelse, men mänskligt språk är fullt av oklarheter, så det är inte ett väldefinierat problem. Schack är å andra sidan mycket väl definierade. Även om det en gång ansågs vara symbolen för intelligent aktivitet, kan datorer nu spela schack bättre än alla utom några få mänskliga spelare.

Vissa problem, även om de är väl definierade, är för stora för att kunna lösas på rimlig tid även på våra största datorer. Men säkerligen, om en dator skulle kunna befrias från alla tids- och minnesbegränsningar, kan den lösa något väldefinierat problem?

Det överraskande svaret på denna fråga, som var känd för matematiker redan innan de första riktiga datorerna byggdes, är nej. Det finns några saker som ingen dator någonsin kan göra eftersom det kan bevisa att det inte finns några algoritmer för att göra dem – precis som det inte finns något sätt att kvadratera en cirkel med en kompass och raka.

Dessa saker är inte mer matematiska nyfikenheter. Det är saker som programmerare vill ha sina datorer att göra för dem och saker som leverantörer av mjukvaruutvecklingsverktyg skulle vilja integrera i sina felsökare. Programvetenskapliga läroplaner inkluderar vanligtvis ämnet för icke-kompatibla funktioner, men programmerare som inte är datorvetenskapliga huvudpersoner ber ibland om det omöjliga utan att inse det.

Alan Turing 1935 frågade om det finns en metod som ett datorprogram kan avgöra om något annat datorprogram kommer att stoppa. Detta är det berömda “stoppproblemet.” Turing visade att det inte har någon lösning.

En felsökare med denna förmåga skulle säkert vara användbar. Underlåtenhet att stoppa normalt är en vanlig form för programfel. Dessutom kan felsökningen tillämpas successivt på delar av det misslyckade programmet för att isolera den del som hänger upp.

Det är inte uppenbart att en sådan felsökare är omöjlig. Naturligtvis kan felsökaren inte bara enstegs programmet för att se om det stoppar. Om programmet misslyckas kan felsökningen köras för alltid utan att fastställa att detta är fallet. Eller så kan det ge upp precis som programmet är på väg att avsluta, som mänskliga programmerare ibland gör. Vid något tillfälle måste felsökaren kunna säga, “Aha! Denna slinga är oändlig!” Det verkar som om en smart skriven debugger som har alla verktyg för moderna språk på hög nivå till sitt förfogande skulle kunna göra det.

Omöjligt bevis är baserat på följande argument. Om du har en felsökare som kan lösa stoppproblemet, med tanke på obegränsad tid och minne, kan du använda samma kod för att få felsökaren att göra andra saker, av vilka några är självmotsägelsefulla och därmed omöjliga.

Det speciella datorspråket är inte viktigt. Om du kan lösa stoppproblemet för ett språk kan du lösa det för ett annat. Använd bara en kompilator eller annat översättningsprogram innan du löser stoppproblemet. Lägg märke till att det är ganska enkelt att översätta ett monteringsspråksprogram till ett högre språk, även om objektprogrammet är säkert ineffektivt. Målet är dock att visa att en lösning på stoppproblemet är omöjligt, inte bara ineffektivt.

Turing själv föreslog en minimal maskin som har kommit att kallas Turing Machine. Dess minne skulle vara oändligt långt men bara en bit bredt, och maskinen hade endast sekventiell åtkomst till det, som med ett band. Programmeringsspråket var i huvudsak ett flödesschema med bara några få grundkommandon. Trots detta visade Turing att hans maskin kunde emulera någon annan maskin, med tillräckligt med tid och ett lämpligt program. En sådan konstruktion är inte nödvändig för våra ändamål – du kan föreställa dig att datorn är programmerad på ett välbekant språk på hög nivå.

Överväg nu problemet med att avgöra om ett program kan skriva ut en specificerad sträng S (med eller utan annan utgång). Om du kan lösa stoppproblemet kan du lösa problemet. Byt bara ut alla utskriftssatser i programmet med en rutin som inte skickar utdata till skrivaren men håller reda på utdata och stoppar när strängen S visas. Sedan, för att förhindra att programmet stannar av någon annan anledning, byt ut alla stopputtalanden i programmet med oändliga loopar. Lös sedan stoppproblemet för resultatet.

Ett sådant program skulle vara användbart i sig själv eftersom många körfel producerar distinkta meddelanden, och det skulle vara bra att förutspå att sådana fel kommer att uppstå.

Eftersom detta gäller alla strängar S kan du också bestämma om ett program skriver ut en kopia av sig själv. Detta är inte så nyfiken som det verkar vid första anblicken. Det är lätt att skriva ett program med 1000 tecken som skriver ut alla kombinationer av 1 000 tecken, inklusive sig själv. Faktum är att 1 000 tecken förmodligen är en överskattning av antalet tecken som krävs på de flesta högnivåspråk.

Nu kan du skriva ett program för att göra följande saker. Först generera, en efter en, alla möjliga program. Det enklaste sättet att göra detta är att generera alla strängar och kontrollera var och en för att se om det är ett program. Kompilatorer gör detta när de kontrollerar syntax. Kontrollera sedan varje program för att se om det skriver ut en kopia av sig själv. Slutligen, skriv ut en kopia av varje program som inte skriver ut en kopia av sig själv.

Detta program, i processen att generera alla program, kommer så småningom att generera sig själv. Skrivar det ut en kopia av sig själv? Om det gör det bryter det regeln genom att skriva ut en kopia av ett program som skriver ut en kopia av sig själv. Om det inte gör det bryter det regeln genom att inte skriva ut en kopia av ett program som inte skriver ut en kopia av sig själv. Denna dödliga motsägelse bevisar att stoppproblemet inte har någon lösning.

Du kanske känner igen detta som Russells paradox (uppsättningen av alla uppsättningar som inte innehåller sig själva) eller som barberparadoxen (barberaren som rakar varje man som inte rakar sig själv).

Alla problem som en felsökare kan konvertera till stoppproblemet, till exempel strängutgångsproblemet, är lika olösliga. Några andra uppenbara exempel är:

  1. bestämma om ett program kommer att nå en specificerad punkt (Ada-programmerare: det är därför PROGRAM_ERROR måste vara ett körtidfel, inte ett kompileringstidsfel)
  2. bestämma om en variabel initialiseras innan den används
  3. bestämma om ett givet kodsegment är otillgängligt och aldrig kommer att köras
  4. avgöra om två program gör samma sak

Naturligtvis kan en felsökare eller kompilator ibland förutsäga sådana fel – till exempel kan otillgänglig kod ibland identifieras vid sammanställningstiden. Men universella lösningar på sådana problem finns inte.

Omöjligt att avgöra om två program gör samma sak innebär att det alltid är möjligt att besegra en viss typ av trojansk häst. I en föreläsning omtryckt i meddelandena om ACM (augusti 1984) hävdade Ken Thompson att han kunde sätta en trojansk häst i en C-kompilator som skulle felkompilera inloggningsförklaringen för att ge honom åtkomst till alla Unix-system som sammanställts med den, och det skulle felkompilera C-kompilatorn för att infoga en kopia av sig själv. Trojanhästen själv skulle inte visas i källkoden för C-kompilatorn. I ett brev till redaktören konstaterade Steve Draper att en sådan trojansk häst kan besegras genom att parafrasera C-kompilatorn (skriva en annan kod som gör samma sak) och sedan kompilera den igen. Ingen trojansk häst kan ofullständigt känna igen parafraserade program – därför finns det alltid en parafras som kommer att besegra trojanska hästen.

Min egen åsikt i denna fråga är att, om inte trojanska hästen var skickligt skriven, de flesta parafraser skulle besegra den, och i själva verket skulle den förmodligen bli besegrad med normalt programunderhåll. Varje trojansk häst som är smart nog att känna igen de flesta parafraser skulle förmodligen vara mycket större än resten av C-kompilatorn. Du skulle aldrig få det genom portarna.

Stoppproblemet är intimt relaterat till två andra problem, som matematikern David Hilbert ställde 1900. Finns det ett formellt bevis eller diskrimination för varje matematisk uttalande? Finns det en algoritm för att hitta bevis?

Den första frågan besvarades negativt av Kurt Gödel 1931. Gödels bevis var komplicerat, men om du accepterar att problemet med att stoppa problemet inte kan bevisas helt enkelt. Huruvida ett visst program stannar är ett matematiskt uttalande. Faktum är att många matematiska teorem redan är speciella fall för att stoppa problemet eftersom du kan skriva ett program för att söka efter motexempel och stoppa när det hittar ett. Satsen motsvarar påståendet att programmet aldrig stoppar.

Om det alltid fanns ett formellt bevis eller motbevisning av påståendet att ett program stannar, kan du helt enkelt generera alla bevis (mer eller mindre som programmet beskrev tidigare genererade alla program) tills du hittade antingen ett bevis eller ett motbevis. Det skulle lösa stoppproblemet. Eftersom stoppproblemet i allmänhet är olösligt måste det finnas minst ett matematiskt uttalande av detta slag som är obeslutbart – det vill säga det kan inte formellt bevisas eller motbevisas.

Detta visar att det i allmänhet är omöjligt att bevisa att ett program fungerar. Specifika program eller begränsade klasser av program kan bevisas göra vissa saker, men det finns inget sätt att göra detta för varje program.

Med tanke på att vissa matematiska uttalanden är obeslutbara, finns det ett program, “avgörbarhetsprogrammet”, som kan säga om något matematiskt uttalande är avgörbart, även utan att avgöra om det är sant eller falskt? Som du kanske har gissat utifrån tonen i den här artikeln är svaret igen nej. Om du har ett avgörbarhetsprogram kan du ta valfritt program och fråga om det stoppar. Använd sedan avgörbarhetsprogrammet på den här frågan. Om frågan kan avgöras kommer en sökning av alla bevis att bevisa den eller motbevisa den. Om frågan är obeslutbar stannar programmet aldrig; annars kan du bevisa att det stoppar genom att bara köra det tills det stoppar.

Därför kan teorem-bevisande program, hur framgångsrika de än är i begränsade områden, aldrig bevisa allt. Vissa saker måste alltid förbli utanför deras grepp.

Dessa argument är inte stränga i matematisk mening eftersom för mycket har lämnats ut. En stor del av Turing och Gödels arbete omfattade formalisering av begreppen “beräkning” och “bevis” till den punkt där deras argument skulle accepteras av matematiker.

Du kanske redan har upptäckt ett tyst antagande som inte motsvarar verkligheten. Programmen begränsas inte av minnesbegränsningar. Om ett program har en minnesbegränsning, kan stoppproblemet i teorin lösas – men bara med ett program med ett mycket större minne.

Det är så det kan göras. Ett program med en minnesbegränsning har endast ett begränsat antal tillstånd. En debugger kan enkeltsteg den och hålla reda på de stater den har ockuperat. Om det upptar samma tillstånd två gånger innan det stoppas, kommer det att upprepa samma sekvens av tillstånd på obestämd tid och kommer aldrig att stoppa.

För att göra detta behöver felsökaren tillräckligt med minne för att hålla reda på vilka stater programmet har upptaget. Endast en bit krävs för varje möjligt tillstånd, men antalet möjliga tillstånd för till och med ett enkelt program är verkligen förbluffande. Varje kombination av bitar i minnet är ett annat tillstånd. Följaktligen har ett program med endast 1 024 byte minne minst 2 (1024 x 8) tillstånd på grund av minneskonfiguration ensam, för att inte säga något om flaggor och register. Detta antal vippor skulle inte passa in i hela kända universum. Det kan därför sägas att stoppproblemet inte har någon lösning, även i detta fall.

Det borde därför vara klart att det definitivt finns några gränser för vad konstgjord intelligens kan åstadkomma och att matematiker och programmerare jobb aldrig kan automatiseras helt. (Detta är en stor tröst för mig eftersom jag är matematiker och programmerare.

Endast perfekta lösningar är emellertid omöjliga. Det kan fortfarande hävdas, och det hävdas av vissa, att program för konstgjord intelligens så småningom kommer att kunna lösa alla problem som det mänskliga sinnet kan lösa, med åtminstone samma framgångsgrad. Och om det enda kravet är praktiska lösningar, inte perfekta lösningar, kan många intressanta men teoretiskt olösliga problem lösas.


Lämna ett svar

E-postadressen publiceras inte. Obligatoriska fält är märkta *