Turingmaskin

Ei turingmaskin er ein matematisk modell av eit dataprogram. Ei turingmaskin er ein type tilstandsmaskin med eit endeleg sett med reglar, men uendeleg stort minne, og kvar turingmaskin er i stand til å kjenna att eit spesifikt formelt språk. Turingmaskiner vart oppfunne av Alan Turing på midten av 1930-talet og vart berømte for å vere ein veldig enkel modell som kan representere alle slags algoritmar.

Definisjonar

Ei turingmaskin M er i si enklaste form oppbygd av dei fylgjande deler:

• Eit endeleg alfabet Σ, som inneheld mengda av teikn som maskina kan skrive og lese
• Eit blankt teikn, som òg kan lesast og skrivast av maskina, men som ikkje kan vere del av inndata. Det blanke teiknet er ekvivalent
• Eit uendeleg langt band, som er delt opp i felt. Kvart felt kan innehalde eitt teikn
• Ein peikar til eitt felt på bandet
• Ei endeleg mengd Q av tilstandar. Alle turingmaskiner inneheld to spesielle tilstandar q_godta og q_avslå, i tillegg til ei mengd med andre tilstandar q₁, …, q_p
• Og ein overgangsfunksjon $\delta :Q\times \Sigma \rightarrow Q\times \Sigma \times \{V,H\}$

Det finst variasjonar på denne lista. Ei turingmaskin kan operere med to alfabet, der inndata må verte skrive i det minste av dei to alfabeta. Det finst òg turingmaskiner med to eller fleire band (og peikarar), og såkalla ikkje-deterministiske turingmaskiner, der δ ikkje er ein funksjon, men ein meir generell relasjon. Sjølv om desse variantane verkar kraftigare, kan den mest grunnleggjande varianten utføre alle oppgåver som dei kraftigare variantane kan.

Korleis turingmaskiner fungerer

Inndata (altså, ein tekststreng som skal prosesserast av maskina) er i byrjinga skrive inn på ein seksjon av bandet. Peikaren er stilt på det fyrste teiknet av inndata (dvs. det teiknet som ligg lengst til venstre på bandet), og maskina står i tilstanden q₁. Deretter køyrer maskina ei rekke steg. Kva maskina gjer i kvart steg er bestemt av overgangsfunksjonen δ. Paret (q,x), beståande av maskina sin noverande tilstand q og teiknet x som peikaren peikar til, er input til funksjonen δ. Utputen δ(q,x) er ein trippel (q',x',r), der q' er den nye tilstanden maskina skal gå inn i, x' er det nye teiknet som skal skrivast inn i feltet som peikaren peikar på, og r avgjer kva for ei retning peikaren skal svive: Viss r = V, så skal peikaren svive ein plass mot venstre, og viss r = H, så skal peikaren svive ein plass mot høgre. Når det nye teiknet er skrive inn på bandet (viss det stod eit teikn der frå før, vert det overskrive), peikaren har svive over til eit nytt felt, og maskina har endra tilstand, då er ho klar til å utføre eit nytt steg. Maskina fortset slik heilt til ho kjem inn i ein av tilstandane q_godta eller q_avslå; på det tidspunktet stoggar ho.

Me kan sjå at det einaste som får oppførselen åt maskina M til å variere, er inndata. Kvar tekststreng som får M til å stogge på q_godta når han vert gjeven som inndata, er sagt å vere godteken av M. Me seier at M kjenner att språket L som inneheld alle strengene over Σ som vert godtekne av M. Viss M stoggar på q_avslå på alle andre strenger, seier me at M kan avgjere språket L. Ikkje alle turingmaskiner er i stand til å avgjere eit språk; det hender at ei turingmaskin aldri vil nå nokon av dei to tilstandane på gjeve inndata, og i slike tilfelle vil maskina fortsetje å køyre i all æve.

Turingmaskiner og reknbarheit

Mengda av alle språka som kan kjennast att av (minst) ei turingmaskin, vert kalla dei rekursivt nummererbare språka. Dette er dei same språka som kan genererast av ein formell grammatikk. Språka som kan avgjerast av turingmaskiner er kalla rekursive språk. Enkelte språk kan kjennast att, men ikkje avgjerast: Turing beviste at stoppeproblemet ikkje er avgjerbart. Ikkje alle språk kan kjennast att heller: Det finst ei teljeleg mengd turingmaskiner, men ei uteljeleg mengd språk (gjeve definisjonen av eit språk som ei vilkårleg mengd av strenger), så dei aller fleste språk kan faktisk ikkje kjennast att av turingmaskiner.

Å avgjere eit språk kan seiast å vere ekvivalent med å svare på eit ja/nei-spørsmål om inndata, eit såkalla avgjerdsproblem: strengene som vert godtekne får svaret JA, og strengene som vert avslegne får svaret NEI. Det er difor me i innleiinga kan seie at turingmaskina er som eit abstrakt dataprogram; både maskina og programmet løyser eitt spesifikt problem. Church-Turing-tesa er ei formodning i matematikken som påstår at viss det i det heile teke er mogleg å løyse eit problem (m.a. eit avgjerdsproblem) med ein algoritme, så kan ei turingmaskin løyse problemet. Det er vanskeleg å definere nøyaktig kva ein algoritme er, men ingen har klart å kome på ein måte å manipulere data på som kan løyse problem som turingmaskiner ikkje kan. Ei turingmaskin er dermed rekna som synonym med ein algoritme. Datamaskiner kan òg løyse alle problem som turingmaskiner kan løyse (iallfall om dei er gjevne vilkårleg stort minne). Datamaskiner vert difor kalla turingkomplette

Universelle turingmaskiner

Turingmaskiner er ikkje berre ein modell av dataprogram, dei kan òg vere ein modell av datamaskiner. Som eitkvart endeleg matematisk objekt, kan ei turingmaskin skildrast ved ein tekststreng. Ei (skildring av ei) turingmaskin kan difor inngå som del av inndata til ei anna turingmaskin. Ei universell turingmaskin U er ei turingmaskin som vert gjeve ei skildring av ei anna turingmaskin M, pluss ein tekststreng X. Den spyttar då ut det same svaret som M ville gjort, gjeve X som inndata (det er medteke at viss M køyrer i all æve gjeve X, så køyrer U òg i all æve gjeve M og X. U er dermed som ei datamaskin som køyrer dataprogrammet M. Turing beviste at universelle turingmaskiner finst.

Kjelder

Bibliografi

• Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. Sjå Chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
• Roger Penrose (1990) [1989]. The Emperor's New Mind (2. utg.). Oxford University Press, New York. ISBN 0-19-851973-7. 
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Chapter 3: The Church–Turing Thesis, s. 125–149.
• Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1. utg.). New York: McGraw–Hill Book Company. ISBN 0-07-061726-0. 
• Peter van Emde Boas 1990, Machine Models and Simulations, s. 3–66, in Jan van Leeuwen, red., Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, [place?], ISBN 0-444-88071-2 (Volume A). QA76.H279 1990.