Turingmaskin

Ei turingmaskin er ein matematisk modell av eit dataprogram. Ei turingmaskin er ein type tilstandsmaskin med eit endeleg sett med reglar,Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".  men uendeleg stort minne,Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed". og kvar turingmaskin er i stand til å kjenna att eit spesifikt formelt språk. Turingmaskiner vart oppfunne av Alan Turing på midten av 1930-taletMinsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols," also Stone 1972:8 where the word "machine" is in quotation marks.  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 qgodta og qavslå, i tillegg til ei mengd med andre tilstandar q1, …, qp
 Og ein overgangsfunksjon 

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 q1. 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 qgodta eller qavslå; 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å qgodta 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å qavslå 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."

  Chapter 3: The Church–Turing Thesis, s. 125–149.

 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.

Kategori:Formelle språk
Kategori:Informatikk