mina favoritförfattare (David Deutsch, Roger Penrose och Douglas Hofstadter) dyker alla in i Church-Turing-tesen om beräkningsteori och, ännu viktigare, dess starkaste Tolkning: Turing-principen. I det här inlägget kommer jag först att förklara Church-Turing-avhandlingen i lekman.
tillbaka när jag arbetade på min datavetenskap examen jag studerade Turing maskiner och Kyrkan-Turing avhandling i min Intro till beräkningsteori klass. Då tyckte jag att det var ett stort slöseri med tid. Jag ville bara programmera datorer och jag kunde inte bry mig mindre om den här döda Turing-killen (eller den här kyrkan) eller hans dumma teoretiska maskiner.
nu när jag förstår de filosofiska konsekvenserna av kyrkans Turing-avhandling, önskar jag att jag hade uppmärksammat i klassen! Eftersom kyrkans Turing-avhandling, om den är sann, har några djupa filosofiska konsekvenser och det kan också berätta något om verklighetens djupa och speciella natur.
ändlig automat
alla texter och klasser på teorin om beräkning börjar med något som kallas ”ändlig automat.”Grundtanken bakom dem är ganska lätt. Du föreställer dig bara en enkel ’maskin’ som kan göra val och flytta mellan stater. Här är ett exempel på en mycket enkel som representerar ”logiken” för en myntstyrd turnstile.
på vanlig engelska säger detta att om du försöker trycka igenom en turnstile som är låst, kan du inte om du inte först har lagt in ett mynt. Om du har lagt in ett mynt men inte har tryckt igenom ännu, lämnar ytterligare mynt bara det i olåst tillstånd. Om du har lagt in ett mynt kan du trycka igenom. Det låser sedan igen för nästa person.
det var förmodligen lättare att förstå från diagrammet än från beskrivningen.
ändliga automater kan utföra mycket mer komplicerad logik än detta. Men detta borde ge dig en grundläggande känsla för hur ändliga automater fungerar.
en sak att notera är att en ändlig automat, som den ovan, är rent teoretisk eftersom den bara existerar som en massa bubblor och linjer på ett papper. Det är inte som att det finns någon liten ”ändlig automatmaskin” inuti svängen som fattar dessa beslut. Eller kanske borde jag istället säga att turnstile själv är den ändliga automatmaskinen.
om vi verkligen ville, kunde vi förmodligen bygga en maskin i verkligheten som skulle vara en ändlig automat.Det finns inget som hindrar någon från att bygga den som en riktig maskin i verkligheten och sedan installera den i svängen. Det är bara inte det billigaste sättet att göra det.
så alla ”program” du gör som en ritning av en ändlig automat kan förvandlas till en verklig ”beräkning” som verkligen fungerar. Betydelsen av skillnaden mellan en beräkningsmaskin som faktiskt kan existera (som en ändlig automat) och en som bara är hypotetisk och bryter mot fysikens lagar blir viktig på ett ögonblick.
mer kraftfulla maskiner
när en klass i beräkningsteori fortskrider introduceras eleverna till alltmer komplexa ’maskiner’ som är kraftfullare än ändliga automater. Som figuren till höger visar är den näst mest kraftfulla Pushdown-automaten (PDA). En PDA är egentligen bara en DFA med tillägg av ett slags ”minne”. Detta minne tillåter en PDA att skapa och köra beräkningar (eller program) som en DFA inte kan.
nyckelpunkten är bara att det finns vissa typer av program som kan skrivas för en PDA som inte kan skrivas på en deterministisk ändlig automat (DFA). Med andra ord är handdatorer ”kraftfullare” än Dfa eftersom de kan uttrycka klasser av ”program” som Dfa inte kan.
så det finns ett samband mellan Dfa och handdatorer när det gäller ” beräkningskraft.”Det är nämligen möjligt att bevisa att alla program som skrivs på en DFA också kan skrivas på en PDA, men att det omvända inte är sant.
beviset är i beviset
beviset att en PDA kan köra allt som en DFA kan görs genom att komma fram till ett schema genom vilket logiken i en DFA kan mappas till en PDA. Eftersom en PDA bara är en DFA med minne är det inte svårt att göra — använd bara inte ”minnesfunktionen”.
men vad sägs om det omvända? Kan vi bevisa att det är omöjligt att ta vissa typer av ”program” skrivna för en PDA och översätta dem till en DFA? Det vill säga, finns det ett bevis på att Pushdown Automata inte kan mappas till en ändlig Automata? Eller antar vi bara att en ändlig Automat är mindre kraftfull än en Pushdown-automat eftersom vi för närvarande inte vet ett sätt att kartlägga en PDA tillbaka till en FDA? Kanske finns det ett sätt att kartlägga PDA: er till FDA: er och kanske har ingen upptäckt hur man gör det ännu? Är inte det åtminstone en möjlighet?
som det visar sig är det möjligt att bevisa att en PDA kan köra vissa typer av program som en DFA inte kan. Hur du skulle göra det är att du skulle hitta en beräkning (dvs. ett program) som du kan bevisa att en DFA inte kan beräkna och sedan visa att en PDA kan beräkna den.
Computational Power of a Machine
detta faktum — att det finns mer kraftfulla (PDA) och mindre kraftfulla (DFA) logiska maskiner — är intressant i och för sig.
men det leder till en filosofisk fråga: finns det något sådant som en ” kraftfullaste datormaskin?”
om det fanns en sådan ”kraftfullaste maskin”, hur skulle vi veta att någon specifik föreslagen maskin råkar vara ” den mest kraftfulla?”Eller finns det bara olika typer av datorer tillgängliga och du måste välja rätt för jobbet?
Turing-maskiner
så vilken maskin är kraftfullare än en PDA?
som historien skulle ha det, föreslogs ungefär samtidigt två mycket olika typer av ”maskiner” som båda bevisligen var kraftfullare än handdatorer.
en var Alan Turings Turing-maskin. Den andra var inte så mycket en maskin som en smart uppsättning noteringar utvecklade av Alonzo Church som tjänade samma syfte som att utveckla en maskin. Av dessa två ”maskiner” är Turing-maskinen konceptuellt lättare att undervisa, så vanligtvis är det maskinen som lärs ut i en Beräkningsteorikurs.
Turing-maskiner är roliga små teoretiska maskiner som har ett läs – /skrivhuvud och ett (hypotetiskt) pappersband som det kan läsa från eller skriva till. Baserat på vad Turing-maskinen läser sätter den Turing-maskinen i ett åtgärdsläge som utför någon form av kombination av uppgifter som består av att antingen flytta läs – /skrivhuvudet framåt eller bakåt, läsa från en ny position på bandet eller skriva så en ny position på bandet. En Turing-maskin ser ut så här:
Turing maskiner och moderna datorer
en sak av intresse är att en Turing maskin är, trots ytan framträdanden, faktiskt ganska lik en modern dator. I en modern dator motsvarar centralenheten (CPU) läs – /skrivhuvudet på en Turing-maskin. Minneskretsarna (RAM eller ROM) liknar mycket cellerna i det långa pappersbandet som vridmaskinen kan läsa från eller skriva till. Så moderna datorer verkar ungefär motsvara en Turing-maskin.
en modern dator har en fördel jämfört med Turing-maskinen. En modern dator behöver inte flytta från en cell i sitt ”minne” i sekventiell ordning som en Turing-maskin gör.
det faktum att en Turing-maskin bara kan flytta en cell i taget verkar som en betydande begränsning, eller hur? Vi såg bara hur vissa maskiner är logiskt ’kraftfullare’ än andra: en PDA kan utföra beräkningsuppgifter som en FDA inte kan. Så kanske finns det maskiner som är kraftfullare än Turing-maskiner som kan utföra uppgifter som Turing-maskiner inte kan? Och kanske modern dator — på grund av deras förmåga att hoppa runt minnet snarare än att behöva flytta från cell till cell i följd-kan köra några program som en Turing-maskin inte kan?
i själva verket har modern dator faktiskt mindre uttryckskraft än en Turing-maskin på grund av det faktum att Turing-maskiner var tänkt att ha ett oändligt långt pappersband (dvs. oändligt minne) där som en verklig dator alltid kommer att ha ändligt minne. Men i allmänhet gör detta mycket liten skillnad i vilka typer av beräkningar man kan utföra eftersom människor i allmänhet inte är alla som är intresserade av oändligt långa beräkningar som ger oändligt långa resultat. Det är därför jag säger att moderna datorer och Turing-maskiner är ”ungefär” likvärdiga. Faktum är att så länge du antar någon godtycklig men ändlig storlek på minnet, är de exakt likvärdiga när det gäller vilka typer av program de kan köra.
kyrkan Turing Thesis: Turing Machine = Max logisk kraft
men hur dålig Alonzo kyrka? Hans stackars lilla” maskin ” glömt eftersom Turing maskiner är lättare att undervisa. Kan hans maskin kanske uttrycka några beräkningar /program som en Turing-maskin inte kan, eller vice versa?
skulle det inte vara en fantastisk slump om det bara hände att Alan Turing och Alonzo Church bara så hände att skapa två helt olika typer av teoretiska beräkningsmaskiner och det hände bara så att de var exakt identiska när det gäller vilka typer av beräkningar de kunde utföra?
så föreställ dig allas överraskning när Alan Turing kunde producera ett bevis på att alla program skrivna för en Turing-maskin också kunde skrivas för en Kyrkamaskin och också ett bevis på att alla program skrivna för en Kyrkamaskin också kunde skrivas för en Turing-maskin.
faktum är att det finns ett antal föreslagna typer av teoretiska beräkningsmaskiner. Till exempel försökte teoretiker låta en Turing-maskin ha flera band att läsa/skriva med. De försökte till och med tillåta en Turing-maskin ett 2-dimensionellt ’Ark’ att läsa och skriva med. Teoretiker försökte alla möjliga förbättringar av Turing-maskiner (och Kyrkmaskiner).
och hittills har det varit möjligt att producera ett bevis för var och en av dem att de motsvarar en enkel Turing-maskin.
det verkar som en vild slump, eller hur? Och det skulle vara en vild tillfällighet om det inte finns en övre begränsad till vilka typer av beräkningar som kan utföras.
om det finns en sådan övre gräns, skulle det inte vara någon slump att Turing-maskinen och kyrkans maskin och alla andra beräkningsmaskiner föreslog att alla bara råkar ha samma beräkningskraft, eftersom faktiskt anledningen till att de alla är likvärdiga är att vi har nått den övre gränsen för beräkningskraft.
men kan vi bevisa att det inte finns någon beräkningsmaskin där ute — en som vi bara inte har upptäckt ännu — som har förmågan att utföra beräkningar som en Turing-maskin inte kan?
hur exakt skulle vi producera ett sådant bevis? Faktum är att vi inte kan bevisa att det inte finns något kraftfullare än en Turing-maskin. Så vem vet, kanske finns det.
men faktum är att vi inte kan hitta (eller uppfinna) några sådana maskiner.
så efter stora ansträngningar att försöka och misslyckas, att hitta ett sätt att förbättra kraften i Turing-maskiner, slutligen kyrkan-Turing tesen accepterades även om det inte var visat sig vara sant. Church-Turing-avhandlingen säger i huvudsak något så här:
det är inte möjligt att komma med någon form av beräkningsmaskin som kan utföra ett logikprogram som en vanlig gammal Turing-maskin inte kan.
eller med andra ord:
Turing-maskiner och deras ekvivalenter är de mest kraftfulla möjliga typerna av beräkningsmaskiner och det finns inga mer kraftfulla där ute som vi bara inte vet om ännu.
efter år och år av forskning på denna avhandling håller denna avhandling fortfarande i grunden. Vi får se senare att det har skett något av en modifiering av avhandlingen med introduktionen av teoretiska kvantdatorer. Men i grund och botten gäller avhandlingen fortfarande idag. Ingen har någonsin kommit på ett sätt att överträffa Turing-maskiner när det gäller logisk uttrycksförmåga. Turing-maskiner är fortfarande den regerande mästaren.
så nu förstår du kyrkans Turing-avhandling. Kyrkan-Turing-avhandlingen är dock inte riktigt likvärdig med Turing-principen. Så i ett framtida inlägg kommer jag att utveckla vad skillnaden är och vad det är filosofiska konsekvenser är.
Anteckningar
Turing-Principen. Så namngiven av Roger Penrose, som inte tror på det (åtminstone inte i nuvarande form). Den utvecklades till Turing-Deutsch-principen av David Deutsch, som tror på den, åtminstone i sin form av den.) (Se Artikel i Wikipedia för mer information)