mine yndlingsforfattere (David Deutsch, Roger Penrose og Douglas Hofstadter) dykker alle ned i kirke-Turing-afhandlingen om Beregningsteori og, endnu vigtigere, dens stærkeste fortolkning: Turing-princippet. I dette indlæg vil jeg først forklare Church-Turing-afhandlingen i lægmandssprog.
tilbage da jeg arbejdede på min computer science grad studerede jeg Turing maskiner og kirke-Turing afhandling i min Intro til Computational Theory klasse. Dengang troede jeg, det var et stort spild af tid. Jeg ville bare programmere computere, og jeg kunne ikke bekymre mig mindre om denne langdøde Turing Fyr (heller ikke denne kirke fyr) eller hans dumme teoretiske maskiner.
nu hvor jeg forstår de filosofiske forgreninger af kirke-Turing-afhandlingen, ville jeg ønske, at jeg havde været opmærksom i klassen! Fordi Kirketuring-afhandlingen, hvis den er sand, har nogle dybe filosofiske forgreninger, og den kan også fortælle os noget om virkelighedens dybe — og specielle — natur.
Finite Automata
alle tekster og klasser om teorien om beregning starter med noget, der hedder “Finite Automata.”Den grundlæggende ide bag dem er ret let. Du forestiller dig bare en simpel ‘maskine’, der er i stand til at træffe valg og flytte mellem stater. Her er et eksempel på en meget enkel, der repræsenterer “logikken” af en møntdrevet turnstile.
på almindeligt engelsk siger Dette, at hvis du prøver at skubbe gennem en turnstile, der er låst, kan du ikke, hvis du ikke først har lagt en mønt. Hvis du har lagt en mønt, men ikke har skubbet igennem endnu, skal du bare lade den være i ulåst tilstand. Hvis du har lagt i en mønt, så kan du skubbe igennem. Det låses derefter igen for den næste person.
det var sandsynligvis lettere at forstå fra diagrammet end fra beskrivelsen.
Finite Automata er i stand til at udføre langt mere kompliceret logik end dette. Men dette skal give dig en grundlæggende fornemmelse for, hvordan finite automata fungerer.
en ting at bemærke er, at en endelig automat, som den ovenfor, er rent teoretisk, fordi den kun eksisterer som en flok bobler og linjer på et stykke papir. Det er ikke som om der er en lille “endelig automatmaskine” inde i turnstile, der gør disse beslutninger. Eller måske skulle jeg i stedet sige, at turnstile selv er den endelige automat maskine.
hvis vi virkelig ville, kunne vi sandsynligvis bygge en maskine i det virkelige liv, der ville være en endelig automat.Der er intet, der forhindrer nogen i at bygge den som en rigtig maskine i det virkelige liv og derefter installere den i turnstile. Det er bare ikke den billigste måde at gøre det på.
så ethvert ‘program’, du laver som en tegning af en endelig automat, kan omdannes til en “beregning” i det virkelige liv, der virkelig fungerer. Betydningen af forskellen mellem en beregningsmaskine, der faktisk kan eksistere (som en endelig automat) og en, der kun er hypotetisk og overtræder fysikens love, bliver vigtig i et øjeblik.
mere kraftfulde maskiner
efterhånden som en klasse i beregningsteori skrider frem, introduceres de studerende til stadig mere komplekse ‘maskiner’, der er mere magtfulde end endelige automater. Som figuren til højre viser, er den næste mest kraftfulde Push-ned Automata (PDA). En PDA er egentlig bare en DFA med tilføjelsen af en slags “hukommelse”. Denne hukommelse tillader en PDA at oprette og køre beregninger (eller programmer), som en DFA ikke kan.
nøglepunktet er kun, at der er visse typer programmer, der kan skrives til en PDA, der ikke kan skrives på en deterministisk endelig automat (Dfa). Med andre ord er PDA’ er ‘mere magtfulde’ end Dfa ‘ er, fordi de kan udtrykke klasser af “programmer”, som Dfa ‘er ikke kan.
så der er et forhold mellem Dfa’ er og PDA ‘ er med hensyn til “beregningskraft.”Det er nemlig muligt at bevise, at ethvert program skrevet på en DFA også kan skrives på en PDA, men at det omvendte ikke er sandt.
beviset er i beviset
beviset for, at en PDA kan køre alt, hvad en DFA kan, gøres ved at komme med et skema, hvormed logikken i en DFA kan kortlægges til en PDA. Da en PDA kun er en DFA med hukommelse, er det ikke svært at gøre — brug bare ikke “hukommelsesfunktionen”.
men hvad med det omvendte? Kan vi bevise, at det er umuligt at tage visse typer “programmer” skrevet til en PDA og oversætte dem til en DFA? Det vil sige, er der et bevis på, at push-ned Automata ikke kan kortlægges til en endelig Automata? Eller antager vi bare, at en endelig automat er mindre kraftfuld end en push-ned-automat, fordi vi ikke i øjeblikket kender en måde at kortlægge en PDA tilbage til en FDA? Måske er der en måde at kortlægge PDA ‘er til FDA’ er, og måske har ingen opdaget, hvordan man gør det endnu? Er det ikke i det mindste en mulighed?
det viser sig, at det er muligt at bevise, at en PDA kan køre visse typer programmer, som en DFA ikke kan. Den måde du ville gøre det på er, at du ville finde en beregning (dvs. et program), som du kan bevise, at en DFA ikke kan beregne og derefter demonstrere, at en PDA kan beregne den.
computerkraft af en maskine
denne kendsgerning — at der er mere kraftfulde (PDA) og mindre kraftfulde (DFA) logiske maskiner — er interessant i sig selv.
men det fører til et filosofisk spørgsmål: er der sådan noget som en “mest magtfulde computermaskine?”
hvis der var sådan en “mest magtfulde maskine”, hvordan ville vi vide nogen specifik foreslået maskine sker for at være “den mest magtfulde?”Eller er der bare forskellige typer computermaskiner til rådighed, og du skal vælge den rigtige til jobbet?
Turing Machines
så hvilken maskine er mere kraftfuld end en PDA?
som historien ville have det, blev der på omtrent samme tid foreslået to meget forskellige typer “maskiner”, der begge var beviseligt mere magtfulde end PDA ‘ er.
den ene var Alan Turings Turing-maskine. Den anden var ikke så meget en maskine som et smart sæt notationer udviklet af Alonso kirke, der tjente det samme formål som at udvikle en maskine. Af disse to” maskiner ” er Turing-maskinen konceptuelt lettere at undervise, så det er normalt den maskine, der undervises i et Beregningsteori-kursus.
Turing-maskiner er sjove små teoretiske maskiner, der har et læse – /skrivehoved og et (hypotetisk) papirbånd, som det kan læse fra eller skrive til. Baseret på, hvad Turing-maskinen læser, sætter den Turing-maskinen i en handlingstilstand, der udfører en slags kombination af opgaver, der består af enten at flytte læse/skrivehovedet fremad eller bagud, læse fra en ny position på båndet eller skrive så en ny position på båndet. En Turing-maskine ser sådan ud:
Turing-maskiner og moderne computere
en ting af interesse er, at en Turing-maskine på trods af overfladeoptræden faktisk ligner en moderne computer. I en moderne computer svarer den centrale behandlingsenhed (CPU) til læse – /skrivehovedet på en Turing-maskine. Hukommelseschips (RAM eller ROM) ligner meget cellerne i det lange papirbånd, som drejemaskinen kan læse fra eller skrive til. Så moderne computere ser ud til at svare stort set til en Turing-maskine.
en moderne computer har en fordel i forhold til Turing-maskinen. En moderne computer behøver ikke at bevæge sig fra en celle i sin “hukommelse” i rækkefølge, som en Turing-maskine gør.
det faktum, at en Turing-maskine kun kan flytte en celle ad gangen, virker som en betydelig begrænsning, ikke? Vi så lige, hvordan nogle maskiner er logisk ‘mere magtfulde’ end andre: en PDA kan udføre beregningsopgaver, som en FDA ikke kan. Så måske er der maskiner, der er mere magtfulde end Turing-maskiner, der kan udføre opgaver, som Turing-maskiner ikke kan? Og måske kan moderne computer — på grund af deres evne til at hoppe rundt i hukommelsen i stedet for at skulle flytte fra celle til celle sekventielt-køre nogle programmer, som en Turing-maskine ikke kan?
faktisk har moderne computer faktisk mindre udtryksfuld kraft end en Turing-maskine i kraft af det faktum, at Turing-maskiner blev opfattet som havende et uendeligt langt papirbånd (dvs.uendelig hukommelse), hvor som en virkelig computer altid vil have endelig hukommelse. Men generelt gør dette meget lille forskel i, hvilke typer beregninger man kan udføre, da mennesker generelt ikke er alle interesserede i uendeligt lange beregninger, der giver uendeligt lange resultater. Derfor siger jeg, at moderne computere og Turing-maskiner er “omtrent” ækvivalente. Faktisk, så længe du antager en vilkårlig, men endelig størrelse af hukommelse, er de nøjagtigt ækvivalente med hensyn til, hvilke typer programmer de kan køre.
Kirkens Turing-afhandling: Turing Machine = maksimal logisk kraft
men hvad med den fattige Alonso Kirke? Hans stakkels lille “maskine” glemt, fordi Turing maskiner er lettere at undervise. Er hans maskine måske i stand til at udtrykke nogle beregninger /programmer, som en Turing-maskine ikke kan, eller omvendt?
ville det ikke være en fantastisk tilfældighed, hvis det bare skete, at Alan Turing og Alonso Kirke lige så skete for at skabe to helt forskellige typer teoretiske beregningsmaskiner, og det skete bare så, at de var nøjagtigt identiske med hensyn til hvilke typer beregninger de kunne udføre?
så forestil dig alles overraskelse, da Alan Turing var i stand til at fremlægge et bevis på, at ethvert program skrevet til en Turing-maskine også kunne skrives til en Kirkemaskine, og også et bevis på, at ethvert program skrevet til en Kirkemaskine også kunne skrives til en Turing-maskine.
faktisk er der en række foreslåede typer teoretiske beregningsmaskiner. For eksempel forsøgte teoretikere at lade en Turing-maskine have flere bånd at læse/skrive med. De forsøgte endda at tillade en Turing-maskine et 2-dimensionelt ‘ark’ at læse og skrive med. Teoretikere forsøgte alle mulige forbedringer af Turing-maskiner (og Kirkemaskiner).
og indtil videre har det været muligt at fremstille et bevis for hver enkelt af dem, at de svarer til en simpel Turing-maskine.
det virker som en vild tilfældighed, ikke? Og det ville være en vild tilfældighed, medmindre der er en øvre begrænset til, hvilke typer beregning der kan udføres.
hvis der er en sådan øvre grænse, ville det slet ikke være tilfældigt, at Turing-maskinen og Kirkemaskinen og alle andre beregningsmaskiner, der foreslås, bare tilfældigvis har den samme beregningskraft, da grunden til, at de alle er ækvivalente, er fordi vi har nået den øvre grænse for beregningskraft.
men kan vi bevise, at der ikke er nogen beregningsmaskine derude — en, som vi bare ikke har opdaget endnu — der har evnen til at udføre beregninger, som en Turing-maskine ikke kan?
hvordan ville vi producere et sådant bevis? Faktum er, at vi ikke kan bevise, at der ikke er noget mere magtfuldt end en Turing-maskine. Så hvem ved, måske er der.
men faktum er, at vi ikke kan finde (eller opfinde) sådanne maskiner.
så efter en betydelig indsats for at forsøge og undlade at finde en måde at forbedre kraften i Turing-maskiner, blev Kirke-Turing-afhandlingen endelig accepteret, selvom det ikke blev bevist at være sandt. Kirke-Turing-afhandlingen siger i det væsentlige noget som dette:
det er ikke muligt at komme med nogen form for beregningsmaskine, der kan udføre et logikprogram, som en almindelig gammel Turing-maskine ikke kan.
eller med andre ord:
Turing-maskiner og deres ækvivalenter er de mest kraftfulde mulige typer beregningsmaskiner, og der er ikke mere magtfulde derude, som vi bare ikke ved om endnu.
efter mange års forskning i denne afhandling holder denne afhandling stadig grundlæggende. Vi ser senere, at der har været noget af en ændring af afhandlingen med introduktionen af teoretiske kvantecomputere. Men dybest set gælder afhandlingen stadig i dag. Ingen har nogensinde fundet en måde at overgå Turing-maskiner, når det kommer til logisk udtryksevne. Turing-maskiner er stadig den regerende mester.
så nu forstår du Kirke-Turing-afhandlingen. Kirke-Turing-afhandlingen svarer imidlertid ikke helt til Turing-princippet. Så i et fremtidigt indlæg vil jeg udvikle, hvad forskellen er, og hvad det er filosofiske forgreninger er.
Noter
Turing-Princippet. Så navngivet af Roger Penrose, som ikke tror på det (i det mindste ikke i nuværende form). Det blev udviklet til Turing-Deutsch-princippet af David Deutsch, der tror på det, i det mindste i sin form for det.) (Se artiklen for flere detaljer)