Opdagede Turing virkelig standseproblemet?

Den 25. november skal jeg holde et foredrag om Alan Turing på Institut for Matematiske Fag. I mit foredrag vil jeg selvfølgelig bruge tid på Turings bidrag til teorien om beregnelighed. Det første, mange tænker på, er her standseproblemet.

Standseproblemet som man lærer det i et typisk kursus i beregnelighed er

Givet en Turing-maskine M og en streng w, vil M da standse, hvis den får w som input?

Dette problem er uafgørbart, og i folkemunde hedder det sig, at det var Alan Turing, der beviste dette. Det har jeg selv bildt studerende ind. Men da jeg forberedte min første udgave af mit foredrag (som jeg holdt for Ungdommens Naturvidenskabelige Forening) læste jeg Turings oprindelige artikel og opdagede ved den lejlighed, at det faktisk ikke var det, Turing beviste.

Turing var interesseret i noget lidt andet, og det afsløres allerede af titlen på hans artikel fra 1936: On Computable Numbers With An Application To The Entscheidungsproblem. Alan Turing konstruerer sin maskinmodel for at kunne give en præcis definition af begrebet `beregnbart tal’.

Turings oprindelige maskiner udskriver cifre. Et reelt tal r er beregnbart, hvis der findes en Turing-maskine, der på sit bånd kan skrive cifrene i r (altså også decimalerne) i korrekt rækkefølge. Det er klart, at sådan en maskine ikke nødvendigvis bliver færdig – dette er tilfældet, hvis r har en uendelig decimalekspansion.  Men der skal altid gå endeligt mange skridt inden næste ciffer bliver skrevet. En maskine, der kan foretage uendeligt mange skridt uden at skrive et ciffer siges at gå i uendelig løkke.

Turing viser nu to resultater om beregnbare tal:

  1. Der findes tal, der ikke er beregnbare.
  2. Det er uafgørbart om en given Turing-maskine går i uendelig løkke.

Det første resultat kan vises direkte ved en anvendelse af Cantors andet diagonaliseringsprincip. Bemærk at dette egentlig følger af at \mathbb{R} er overtællelig, mens der kun kan være tælleligt uendeligt mange Turing-maskiner, da hver Turing-maskine kan kodes som et naturligt tal. Vi kan derfor tale om maskine M_1, M_2, M_3 \ldots.

Diagonalargumentet er nu dette:

Betragt en liste over alle beregnbare tal, listet således at maskine M_i beregner r_i.
r_1 = 23,457535548 \ldots
r_2 = 0,777992838 \ldots
r_3 = 0,003355455 \ldots

Vi kan nu konstruere et nyt tal, x, som er givet ved at decimal nummer i i x er forskellig fra decimal nummer i i r_i ved at lægge 1 til denne decimal (medmindre der er tale om 9, så skriver vi 0). Dette tal kan selvfølgelig ikke være i vores liste og er derfor ikke beregnbart.

Det andet resultat er et modstridsargument – antag at der var en særlig Turing-maskine H, der kunne afgøre om en vilkårlig given Turing-maskine gik i uendelig løkke. Men så kunne vi beregne x således:

For at finde den k‘te decimal i x finder vi frem til maskine M_k således:

  1. For hvert naturligt tal i, startende med 1, find ud af om k er koden for en Turing-maskine. Brug H til at finde ud af om der er tale om en Turing-maskine, der går i uendelig løkke. Bliv ved på denne måde, indtil der er fundet k maskiner, der ikke går i uendelig løkke.
  2. Den sidste sådanne maskine, der blev fundet, må derfor være M_k. Start M_k og lad den skrive k cifre. Læg 1 til det sidste ciffer (medmindre der er tale om 9, da skriver vi 0). Dette er den k‘te decimal i x.

Men x er ikke beregnbar, så her er tale om en modstrid.

Men hvor kommer standseproblemet så fra? vil nogen nu spørge. Begrebet dukker så vidt jeg ved først op i 1958, dvs. 4 år efter Turings død, nemlig i bogen Computability and Unsolvability af Martin Davis. Denne bog er i sig selv en klassiker, som har inspireret formodentlig alle senere fremstillinger af teorien for beregnelighed.

Turings oprindelige artikel er genoptrykt mange steder og findes også frit tilgængelig på WWW. Hvis man gerne vil have en ven ved hånden, kan jeg anbefale Charles Petzolds bog  The Annotated Turing, der er en 372 sider lang gennemgang af Turings artikel (hele den originale tekst er med) med en masse perspektiverende afstikkere til matematikkens og datalogiens historie – der starter med Diophantus og slutter tæt på vor tid. Se mere om den på dens websted.

(Visited 64 times, 1 visits today)
Loading Facebook Comments ...

Skriv et svar