Phenquestions
Turing-maskinen er den sentrale teoretiske konstruksjonen innen informatikk. Turing-maskinen er en abstrakt matematisk beregningsmodell. Bruken av Turing-maskiner hjelper til med å forklare hva beregning er ved å avgrense de såkalte "beregningsfunksjonene.”
Alan Turings tidlige forskning om logikk fokuserte på et kjent uløst problem kjent som Entscheidungsproblem. Entscheidungsproblemet (grovt oversatt fra tysk som avgjørelsesproblemet) ble foreslått av filosofen og matematikeren David Hilbert i 1928. Problemet spurte om det var en algoritme som ville avgjøre alle utsagn på et formelt språk.
Et formelt språk er et system av aksiomer og slutningsregler som de som er i aritmetisk eller førsteordens logikk. Aksiomene kan være hvilke som helst symboler, og slutningsreglene kan være en hvilken som helst liste over regler for å manipulere disse symbolene. "Å avgjøre hver uttalelse" betydde enten å uttale om utsagnet var sant / usant eller å uttale om utsagnet var avledelig / underivabel. Kurt Godels fullstendighetssetning beviste at en algoritme som bestemmer for gyldighet tilsvarer en effektiv prosedyre som bestemmer for avledbarhet. Alan Turings papir fra 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem”, viste seg å være et negativt resultat, at det var umulig å algoritmisk bestemme hver uttalelse i et formelt system.
Alan Turing
For å bevise et negativt resultat for Entscheidungsproblemet, trengte Turing å formalisere forestillingen om en algoritme. Turing's formalisering av en algoritme var en matematisk datamaskinmodell som senere ble kjent som Turing-maskinen. En Turing-maskin har et endelig sett med tilstander som maskinen kan være i. Turing-maskinen har et uendelig langt bånd som er delt inn i firkanter. På hver firkant i båndet er det et symbol hentet fra et endelig sett med symboler. Når som helst i beregningen leser Turing-maskinen symbolet på den ene firkanten av båndet. Turing-maskinen kan erstatte dette symbolet med et annet symbol og flytte til enten firkanten til høyre eller firkanten til venstre. Handlingen Turing-maskinen tar bestemmes automatisk av tilstanden maskinen er i. Etter at erstatningssymbolet og flytting til en annen firkantet handling har funnet sted, kan Turing-maskinen overgå til en annen tilstand. Hver forskjellige stat har forskjellige regler om hvordan du bytter ut symboler og hvilken retning du skal bevege deg.
En sjelden fysisk implementering av Turing Machine Design (uten uendelig tape)
Den kanoniske formuleringen av Turing-maskinen består vanligvis av et binært alfabet på utelukkende 0s og 1s. Denne formuleringen samsvarer med intuisjonen til moderne dataprogrammerere, gitt at alle moderne datamaskiner bruker binær. Faktisk er Turing-maskiner nøytrale med hensyn til størrelsen på symbolets alfabet. En Turing-maskin kan også bruke hvilket som helst symbol, enten det er tall eller tegnet fra en hvilken som helst annen type alfabeter som billedsymboler eller det latinske alfabetet. Enhver formulering av ethvert mulig endelig alfabet kan beviselig reduseres til en binær Turing-maskin.
Turing-maskiner antar at det er uendelig mye minne tilgjengelig. Ingen reelle fysisk instanserte maskiner kan oppfylle dette kravet om å være en Turing-maskin. En Turing-maskin antar også at det kan brukes uendelig mye tid på å beregne funksjonen. Disse antagelsene ble laget for å generere den mest ekspansive klassen av mulige funksjoner for Turings definisjon av beregningsfunksjoner. Turings beregningsfunksjoner er alle funksjoner som kan beregnes av en Turing-maskin. Mange av disse beregningsfunksjonene kan aldri beregnes av noen fysisk instansert maskin fordi de krever for mye tid eller minne.
The Church-Turing Thesis hevder ekvivalensen av beregningsfunksjoner og funksjoner som kan beregnes av en Turing-maskin. Dette innebærer at alle funksjoner som ikke kan beregnes av Turing-maskiner, ikke kan beregnes etter noen annen metode. David Hilbert hadde forventet et positivt svar på Entscheidungsproblemet, noe som ville bety at alle problemer kan beregnes. Resultatet av Turing har ført til oppdagelsen av mange uberegnelige problemer.
Det mest berømte uberegnelige problemet er Halting Problem. Halting Problemet er problemet med å lage en algoritme som i det store og hele kan avgjøre om et dataprogram med inngangen skal stoppe eller fortsette for alltid. Selv om det er spesifikke tilfeller der Halting-problemet kan løses, kan det ikke løses for alle dataprogrammer med noen inngang. Dette resultatet har hatt viktige konsekvenser for dataprogrammering, ettersom dataprogrammerere må være klar over muligheten for uendelige sløyfer og umuligheten av å oppdage alle uendelige sløyfer før de kjører programmene sine.
En annen implikasjon av Turing-maskinen er muligheten for universelle Turing-maskiner. Implisitt i Turings design er konseptet med å lagre programmet som modifiserer dataene sammen med dataene det modifiserer. Dette foreslo muligheten for generelle og omprogrammerbare datamaskiner. Moderne datamaskiner er vanligvis universelle Turing-maskiner i den forstand at de kan programmeres til å kjøre hvilken som helst algoritme. Dette eliminerte behovet for forskjellig maskinvare for hvert potensielle dataprogram og introduserte skillet mellom maskinvare og programvare.
Turing-maskinmodellen førte direkte til oppfinnelsen av datamaskiner, men det er ikke den samme tegningen som ble brukt til å konstruere moderne datamaskiner. Von Neumann-arkitekturen brukt som en tegning for moderne datamaskiner bruker det lagrede programkonseptet implisitt i Turing-maskinmodellen, men er forskjellig fra resten av Turing-maskinmodellen på flere viktige måter. De største forskjellene er at von Neumann-arkitekturen ikke bruker et lese-skrivehode og i stedet inneholder flere registre, tilfeldig tilgangsminne, databusser, et lite sett med grunnleggende maskininstruksjoner og flere bitbehandlingsmuligheter. Von Neumann-arkitekturen tillater også eksplisitt spesialiserte inngangs- og utdataenheter som tastaturer og skjermer.
Turing-maskinmodellen var den første matematiske beregningsmodellen. Det førte direkte til oppfinnelsen av fysiske datamaskiner. Fysiske datamaskiner har alle de samme mulighetene som Turing-maskiner har, forutsatt at det er begrenset minne og tidsbegrensning på faktisk beregning. Turing-formuleringen spiller fortsatt en sentral rolle i studiet av beregning. Dataforskere er fortsatt aktivt involvert i å undersøke om spesifikke funksjoner kan beregnes av Turing-maskiner.
