fredag 4 september 2009

Turingmaskinen och dess begränsningar

Melanie Mitchells bok "Complexity, A Guided Tour" är en trevlig bok som presenterar den s.k. komplexitetsteorins nuvarande läge. Det framgår att även om det finns en del intressanta resultat, så är teorin är långtifrån mogen. Det finns t.ex. ingen allmänt accepterad definition av själva begreppet komplexitet.

Avsnittet om Alan Turings insatser är speciellt välskrivet. Hon beskriver på ett för mig nästan begripligt sätt Turings bevis för att svaret är "nej" på matematikern Hilberts fråga om det alltid finns en bestämd procedur, en "beräkning", som kan besvara om ett matematiskt påstående är sant eller inte. (Hilberts berömda problem brukar kallas för "Entscheidungsproblem".)

Turing började med att precisera uttrycket "bestämd procedur" till att betyda "det som en turingmaskin kan beräkna". Och en turingmaskin är helt enkelt ett dataprogram, en algoritm som utifrån indata i ett antal logiska steg kommer fram till ett resultat. Eller inte kommer till ett resultat, eftersom ett program kan ha fel ("oändliga loopar") som gör att det aldrig stoppar. Eller så kanske det inte stoppar för att algoritmen tar ett oändligt antal steg för att utföra.

Jag tyckte inte Mitchells beskrivning av Turings bevis var 100 % klart, så jag tänkte presentera det här i en som jag tycker något begripligare form.

Turing bevisar sitt påstående genom att utgå från antagandet att det finns en turingmaskin, kallad H, som kan avgöra om ett påstående är sant eller falskt. Sedan bevisar han att detta leder till en motsägelse, varför antagandet måste vara falskt.

Antagandet om existensen av turingmaskinen H innebär att H som indata får en annan turingmaskin M och indata I, och då antingen stoppar med resultatet "ja" eller stoppar med resultatet "nej". Vi kan uttrycka det som att H(M, I) ger antingen "ja" eller "nej" som resultat.
Indatat I kan vara vad som helst, inklusive M! (Mitchell är speciellt imponerad av är att Turing före dataåldern förstod att ett dataprogram, som M, både kan "köras" och behandlas som indata till ett annat program, eventuellt till sig självt!)

Nästa steg är att göra en enkel modifiering av turingmaskinen H. Vi kallar den H´ och den är likadan som H, bortsett från att när H stoppar med "ja", så går H´ in i en oändlig loop, dvs H´stoppar inte. Dessutom när H stoppar med "nej", så stoppar H´ (med ett resultat som inte är intressant för resonemanget).

Nu är frågan vad händer om vi som input till H tar M = H´ och I = H´? Ja, H stoppar ju alltid, med antingen "ja" eller "nej". H(H´, H´) ger alltså "ja" eller "nej".

Vad blir då resultatet av H´(H´, H´)? Jo, om svaret på förra frågan var "stopp med ja", så går H´ in i en oändlig loop! Vilket är en motsägelse: om H´stoppar så stoppar H´inte!

Å andra sidan om svaret skulle vara "stopp med nej" så stoppar H´. Om H´ inte stoppar så stoppar H´. Också en motsägelse!

Alltså kan det inte finnas en sådan turingmaskin H´, och eftersom den var en enkel modifikation av turingmaskinen H, så kan inte heller en turingmaskin H finnas. Alltså finns ingen algoritm som kan avgöra om ett godtyckligt program ger ett svar i ett ändligt antal steg.

Slutsatsen man måste dra är att det finns en begränsningar i vad som går att beräkna. Och kanske också att den mänskliga hjärnan, som kom på detta bevis t.ex., klarar av mer än varje tänkbar dator. Skulle en turingmaskin ha kunnat bevisa Turings sats? Kanske. Men skulle en turingmaskin någonsin ha ställt sig frågan? Nyfikenhet är nog en egenskap som inte går att reducera till en algoritm.

Inga kommentarer:

Skicka en kommentar