mine favorittforfattere (David Deutsch, Roger Penrose og Douglas Hofstadter) dykker alle inn I Kirkens Turing-Tesen om Beregningsteori og, enda viktigere, dens sterkeste tolkning: Turing-Prinsippet. I dette innlegget vil jeg først forklare Church-Turing Avhandling i lekmann vilkår.
Da Jeg jobbet på min datavitenskapsgrad, studerte Jeg Turingmaskiner og Kirketuringoppgaven i Min Intro Til Beregningsteori klasse. Da trodde jeg det var en stor sløsing med tid. Jeg ville bare programmere datamaskiner, og jeg kunne ikke bry meg mindre om Denne Langdøde Turing-fyren (heller ikke Denne Kirkefyren) eller hans dumme teoretiske maskiner.
Nå som jeg forstår De filosofiske konsekvensene Av Kirkens Turing-Tesen, skulle jeg ønske jeg hadde fulgt med i klassen! Fordi Church-Turing-Avhandlingen, hvis den er sann, har noen dype filosofiske forgreninger, og det kan også fortelle oss noe om virkelighetens dype og spesielle natur.
Finite Automata
alle tekster og klasser på Teorien Om Beregning starter med noe som kalles » Finite Automata.»Den grunnleggende ideen bak dem er ganske enkelt. Du bare forestille seg en enkel ‘maskin’ som er i stand til å gjøre valg og flytte mellom stater. Her er et eksempel på en veldig enkel som representerer «logikken» til en myntdrevet turnstile.
på vanlig engelsk, sier dette at hvis du prøver å presse gjennom en turnstile som er låst, kan du ikke hvis du ikke først har satt inn en mynt. Hvis du har satt i en mynt, men har ikke presset gjennom ennå, flere mynter bare la den i en ulåst tilstand. Hvis du har satt i en mynt, så kan du presse gjennom. Det låses deretter igjen for neste person.
det var sannsynligvis lettere å forstå fra diagrammet enn fra beskrivelsen.
Endelig Automat er i stand til å utføre langt mer komplisert logikk enn dette. Men dette bør gi deg en grunnleggende følelse for hvordan finite automata fungerer.
en ting å merke seg er at en endelig automat, som den ovenfor, er rent teoretisk fordi den bare eksisterer som en haug med bobler og linjer på et stykke papir. Det er ikke som om det er en liten «endelig automat maskin» inne i turnstile som gjør disse beslutningene. Eller kanskje jeg burde i stedet si at turnstile selv er den endelige automat-maskinen.
hvis vi virkelig ville, kunne vi sannsynligvis bygge en maskin i virkeligheten som ville være En Endelig Automat.Det er ingenting som hindrer noen fra å bygge den som en ekte maskin i virkeligheten og deretter installere den i turnstile. Det er bare ikke den billigste måten å gjøre det på.
så ethvert «program» du lager som tegning av en endelig automat, kan bli omgjort til en virkelighets «beregning» som virkelig fungerer. Betydningen av forskjellen mellom en beregningsmaskin som faktisk kan eksistere (som En Endelig Automat) og en som bare er hypotetisk og bryter fysikkens lover, blir viktig i et øyeblikk.
Mer Kraftige Maskiner
Etter hvert som en klasse i beregningsteori utvikler seg, blir studentene introdusert til stadig mer komplekse ‘maskiner’ som er kraftigere enn Endelig Automat. Som figuren til høyre viser, er Den nest kraftigste Pushdown Automata (PDA). EN PDA er egentlig bare EN DFA med tillegg av en slags «minne». Dette minnet tillater EN PDA å lage og kjøre beregninger (eller programmer) som EN DFA ikke kan.
nøkkelpunktet er bare at det finnes visse typer programmer som kan skrives for EN PDA som ikke kan skrives på EN DETERMINISTISK Endelig Automat (DFA). Med Andre ord Er Pdaer ‘kraftigere’ enn Dfaer fordi de kan uttrykke klasser av «programmer» Som Dfaer ikke kan.
Så Det er et forhold mellom Dfaer og Pdaer når det gjelder » beregningskraft.»Nemlig er det mulig å bevise at ethvert program skrevet på EN DFA også kan skrives på EN PDA, men at omvendt ikke er sant.
Beviset er I Beviset
beviset på at EN PDA kan kjøre alt som EN DFA kan gjøres ved å komme opp med et skjema hvor logikken til EN DFA kan tilordnes TIL EN PDA. Siden EN PDA bare er en dfa med minne, er dette ikke vanskelig å gjøre-bare bruk ikke «minnefunksjonen».
men hva med omvendt? Kan vi bevise at det er umulig å ta visse typer «programmer» skrevet FOR EN PDA og oversette dem til EN DFA? Det vil si, er det et bevis på At Pushdown Automata ikke kan kartlegges til En Endelig Automata? Eller antar vi bare At En Endelig Automat er mindre kraftig enn En Pushdown Automata fordi vi for øyeblikket ikke vet om en måte å kartlegge EN PDA tilbake til EN FDA? Kanskje det er en måte å kartlegge Pdaer Til Fda, og kanskje ingen har oppdaget hvordan man gjør det ennå? Er ikke det i det minste en mulighet?
Som det viser seg, er det mulig å bevise at EN PDA kan kjøre visse typer programmer som EN DFA ikke kan. Måten du vil gjøre det på, er at du vil finne en beregning (dvs. et program) som du kan bevise at EN DFA ikke kan beregne og deretter demonstrere at EN PDA kan beregne den.
Beregningskraft Av En Maskin
dette faktum-at det er kraftigere (PDA) og mindre kraftige (DFA) logiske maskiner — er interessant i seg selv.
men det fører Til et filosofisk spørsmål: er det noe slikt som en » mest kraftfulle databehandlingsmaskin?»
hvis det var en slik «mektigste maskin», hvordan ville vi vite at en bestemt foreslått maskin skjer for å være » den mektigste?»Eller er det bare forskjellige typer datamaskiner tilgjengelig, og du må velge den rette for jobben?
Turing Machines
så hvilken maskin er kraftigere enn EN PDA?
som historien ville ha det, ble det på omtrent samme tid foreslått to svært forskjellige typer «maskiner» som begge var beviselig kraftigere enn Pdaer.
En Var Alan Turings Turingmaskin. Den andre var ikke så mye en maskin som et smart sett med notater utviklet Av Alonzo Church som tjente samme formål som å utvikle en maskin. Av disse to «maskinene» Er Turing-maskinen konseptuelt lettere å undervise, så vanligvis er det maskinen som læres i Et Beregningsteori kurs.
Turing Maskiner Er morsomme små teoretiske maskiner som har et lese / skrive hode og et (hypotetisk) papirbånd som det kan lese fra eller skrive til. Basert på Hva Turingmaskinen leser, setter Den Turingmaskinen Inn I en handlingstilstand som utfører en slags kombinasjon av oppgaver som består av enten å flytte lese – / skrivehodet fremover eller bakover, lese fra en ny posisjon på båndet, eller skrive så en ny posisjon på båndet. En Turing-Maskin ser slik ut:
Turing Maskiner Og Moderne Datamaskiner
en ting av interesse er at En Turing Maskin er, til tross for overflaten utseende, faktisk ganske lik en moderne datamaskin. I en moderne datamaskin Er Sentralbehandlingsenheten (CPU) ekvivalent med lese – /skrivehodet Til En Turing-Maskin. Minnebrikkene (RAM eller ROM) ligner veldig på cellene i det lange papirbåndet som dreiemaskinen kan lese fra eller skrive til. Så moderne datamaskiner synes å være omtrent lik En Turing-Maskin.
en moderne datamaskin har en fordel over Turing-Maskinen. En moderne datamaskin trenger ikke å flytte fra en celle i sitt «minne» i sekvensiell rekkefølge som En Turing-Maskin gjør.
det faktum at En Turing-maskin bare kan flytte en celle om gangen virker som en betydelig begrensning, ikke sant? Vi så bare hvordan noen maskiner er logisk ‘kraftigere’ enn andre: EN PDA kan utføre beregningsoppgaver som EN FDA ikke kan. Så kanskje er det maskiner som er kraftigere enn Turing-maskiner som kan utføre oppgaver Som Turing-Maskiner ikke kan? Og kanskje moderne datamaskin-på grunn av deres evne til å hoppe rundt minnet i stedet for å flytte fra celle til celle i rekkefølge — kan kjøre noen programmer som En Turing-Maskin ikke kan?
faktisk har moderne datamaskiner faktisk mindre ekspressiv kraft enn En Turingmaskin i kraft Av At Turingmaskiner ble oppfattet som å ha et uendelig langt papirbånd (dvs. uendelig minne) hvor en virkelig datamaskin alltid vil ha begrenset minne. Men generelt gjør dette svært liten forskjell i hvilke typer beregninger man kan utføre, siden mennesker generelt ikke er alle som er interessert i uendelig lange beregninger som gir uendelig lange resultater. Det er derfor jeg sier at moderne datamaskiner og Turing-Maskiner er «omtrent» ekvivalente. Faktisk, så lenge du antar en vilkårlig, men endelig størrelse på minne, er de nøyaktig likeverdige når det gjelder hvilke typer programmer de kan kjøre.
Kirkens Turing-Avhandling: Turing Machine = Maks Logisk Kraft
men hva med stakkars Alonzo Kirke? Hans stakkars lille «maskin» glemt fordi Turing Maskiner er lettere å undervise. Er hans maskin kanskje i stand til å uttrykke noen beregninger /programmer som En Turing-Maskin ikke kan, eller omvendt?
Ville Det ikke være en fantastisk tilfeldighet hvis Det bare skjedde At Alan Turing og Alonzo Church bare skjedde for å skape to helt forskjellige typer teoretiske beregningsmaskiner, og det skjedde bare at de var nøyaktig identiske med hensyn til hvilke typer beregninger de kunne utføre?
så tenk deg alles overraskelse da Alan Turing var i stand til å produsere et bevis på at ethvert program skrevet for En Turing-Maskin også kunne skrives for En Kirkemaskin, og også et bevis på at ethvert program skrevet for En Kirkemaskin også kunne skrives for En Turing-maskin.
faktisk finnes det en rekke foreslåtte typer teoretiske beregningsmaskiner. For eksempel forsøkte teoretikere å tillate En Turing-Maskin å ha flere bånd å lese / skrive med. De prøvde å la En Turing Maskin en 2-dimensjonal ‘ ark ‘ å lese og skrive med. Teoretikere prøvde alle slags forbedringer Av Turing-Maskiner (Og Kirkemaskiner).
og så langt har det vært mulig å produsere et bevis for hver eneste av dem at de tilsvarer en enkel Turing-Maskin.
det virker som en vill tilfeldighet, ikke sant? Og det ville være en vill tilfeldighet med mindre det er en øvre begrenset til hvilke typer beregning som kan utføres.
hvis Det er en slik øvre grense, ville Det ikke være tilfeldig at Turing-Maskinen og Kirkemaskinen og alle andre beregningsmaskiner foreslo at alle bare tilfeldigvis har samme beregningskraft, siden faktisk grunnen til at de alle er likeverdige er fordi vi har nådd den øvre grensen for beregningskraft.
men kan vi bevise at det ikke er noen beregningsmaskin der ute — en som vi bare ikke har oppdaget ennå – som har evnen til å utføre beregninger som En Turing-Maskin ikke kan?
hvordan, nøyaktig, ville vi produsere et slikt bevis? Faktum er at vi ikke kan bevise at det ikke er noe kraftigere Enn En Turing-Maskin. Så, hvem vet, kanskje det er.
men faktum er at vi ikke kan finne (eller oppfinne) slike maskiner.
Så Etter betydelig innsats for å prøve og feile, for å finne en måte å forbedre Kraften Til Turing-Maskiner, ble Endelig Kirkens Turing-Tesen akseptert, selv om Det ikke ble bevist å være sant. Kirkens Turing-Avhandling sier i hovedsak noe slikt:
Det er ikke mulig å komme opp med noen form for beregningsmaskin som kan utføre et logisk program som en vanlig gammel Turing-Maskin ikke kan.
Eller med andre ord:
Turing Maskiner og deres ekvivalenter er de kraftigste mulige typer beregningsmaskiner, og det er ikke kraftigere der ute som vi bare ikke vet om ennå.
etter mange år med forskning på Denne Oppgaven, holder Denne Oppgaven fortsatt i utgangspunktet. Vi ser senere at det har vært noe av en modifikasjon Av Avhandlingen med innføring av teoretiske kvante datamaskiner. Men I utgangspunktet Gjelder Oppgaven fortsatt i dag. Ingen har noen gang kommet opp med en måte Å overgå Turing-maskiner når det gjelder logisk uttrykksevne. Turing Machines er fortsatt regjerende mester.
så nå forstår Du Kirkens Turing-Avhandling. Kirkens Turing-Tese er imidlertid ikke helt lik Turing-Prinsippet. Så I et fremtidig innlegg vil jeg utvikle hva forskjellen er og hva det er filosofiske forgreninger er.
Merknader
Turing-Prinsippet. Så navngitt Av Roger Penrose ,som ikke tror på det (i hvert fall ikke i nåværende form). Det ble utviklet Til Turing-Deutsch-prinsippet Av David Deutsch, som tror på Det, i hvert fall i sin form av det.) (Se artikkel I Wikipedia for flere detaljer)