Alan Turing og standseproblemet

turing-artikel

En af de almindeligste misforståelser i teorien om beregnelighed er at Alan Turing beviste at standseproblemet er uafgørbart. Jeg har desværre selv været med til at viderebringe denne fejlagtige påstand, og mange andre derude bliver ved med at gøre det også – i den bedste mening.

Her er et eksempel fra Benjy Weinbergers blog, der har undertitlen “Computer science and technology demystified”

Although the previous example may seem trivial, Turing applied similar thinking to a more far-reaching computability problem, known as the halting problem. In contemporary terms, the halting problem can be described thus: Left to run without interruption, some computer programs eventually stop running, while other programs continue to run forever. The halting problem asks:

Is it possible to write a computer program that can inspect other computer programs and tell if they run forever or if they eventually stop running?

Turing answered this question with an emphatic NO.

Men sådan er det faktisk ikke. Turing kendte slet ikke til “standseproblemet”. Hvis Det var først i 1958, det vi i dag kender som standseproblemet og som på engelsk kaldes The Halting Problem blev formuleret og vist uafgørbart. Det var den amerikanske matematiker Martin David, der gjorde det.

I den berømte artikel fra 1936, “On Computable Numbers With an Application to the Entscheidungsproblem”, viser Alan Turing at der findes et nummer \beta som ikke er beregnbart og bruger dette i et modstridsbevis for at der ikke findes en algoritme, der kan afgøre om en vilkårlig Turing-maskine er “cirkulær”. Men dette er bestemt ikke standseproblemet, og beviset for at \beta ikke er beregnbart er meget anderledes i sin struktur end beviset for at standseproblemet er uafgørbart.

Hvor fejltagelsen kommer fra, ved jeg ikke. Men den burde overbevise os om at vi nogle gange er nødt til at gå tilbage til de primære kilder.