Turingov stroj: opis in primeri Turingovih strojev

Turingov stroj je ena najbolj zanimivih in vznemirljivih intelektualnih odkritij 20. stoletja. To je preprost in uporaben abstraktni model računalništva (računalniškega in digitalnega), ki je povsem običajen za uresničitev katere koli računalniške naloge. Hvala za preprost opis in ravnanje matematična analiza tvori temelj teoretske informatike. Ta študija je privedla do poglobljenega poznavanja digitalnih računalnikov in računa, vključno z razumevanjem nekaterih računalniških problemov, ki jih ni mogoče rešiti na običajnih uporabniških računalnikih.

Kaj je in kdo je ustvaril

Alan Turing je skušal opisati najbolj primitivni model mehanske naprave, ki bi imela enake osnovne zmogljivosti kot računalnik. Turing je prvi opisal avto leta 1936 v članku "O izračunljivih številkah z aplikacijo za problem rešljivosti", ki se je pojavil v Zborniku London Mathematical Society.

Turingov stroj je računalniška naprava, ki je sestavljena iz glave za branje / pisanje (ali "skenerja") s papirnim trakom, ki gre skozi njega. Trak je razdeljen na kvadrate, od katerih vsak nosi en znak - "0" ali "1". Namen mehanizma je, da deluje kot sredstvo za vstop in izstop ter kot delovni spomin za shranjevanje rezultatov vmesnih faz izračunov.

Kaj sestavlja naprava

Vsaka taka naprava je sestavljena iz dveh komponent:

1. Neomejen trak. V obeh smereh je neskončen in razdeljen na celice.
2. Samodejno krmiljen program, skener glave za branje in pisanje podatkov. Lahko je v vsakem trenutku v eni od mnogih držav.

Vsak stroj povezuje dve končni seriji podatkov: abecedo dohodnih simbolov A = {a0, a1, ..., am} in abecedo stanj Q = {q0, q1, ..., qp}. Stanje q0 se imenuje pasivno. Domneva se, da naprava konča svoje delo, ko pade na njega. Stanje q1 se imenuje začetno - stroj začne s svojimi izračuni in je na začetku v njem. Vhodna beseda je na traku ena črka v vrstici v vsakem položaju. Na obeh straneh so le prazne celice.

Kako deluje mehanizem

Turingov stroj ima bistveno razliko od računalniških naprav - pomnilniška naprava ima neskončni trak, pri digitalnih napravah pa ima ta naprava trak določene dolžine. Vsak razred nalog rešuje samo en vgrajen Turingov stroj. Druge vrste nalog vključujejo pisanje novega algoritma.

Krmilna naprava, ki je v enem stanju, se lahko premika v katerikoli smeri vzdolž pasu. Piše v celice in od njih bere znake končne abecede. V procesu premikanja se izbere prazen element, ki zapolni pozicije, ki ne vsebujejo vhodnih podatkov. Algoritem za Turingov stroj določa prehodna pravila za nadzorno napravo. Glavo za branje in pisanje nastavijo na naslednje parametre: pisanje v celico novega znaka, preklop v novo stanje, premik levo ali desno vzdolž traku.

Mehanske lastnosti

Turingov stroj, tako kot drugi računalniški sistemi, ima svoje lastnosti in so podobne lastnostim algoritmov:

1. Diskretnost Digitalni stroj nadaljuje z naslednjim korakom n + 1 šele potem, ko je bil predhodni zaključen. Vsak zaključen korak dodeli, kaj bo n + 1.
2. Razumljivost Naprava izvede samo eno dejanje za isto celico. Vstavi znak iz abecede in naredi en premik: levo ali desno.
3. Determinizem. Vsak položaj v mehanizmu ustreza eni sami izvedbi določene sheme, na vsaki stopnji dejanja in zaporedju njihove izvedbe pa so nedvoumni.
4. Uspešnost. Točen rezultat za vsako stopnjo določa Turingov stroj. Program izvede algoritem in v končnem številu korakov vstopi v stanje q0.
5. Masa. Vsaka naprava je definirana nad veljavnimi besedami v abecedi.

Turingove funkcije stroja

Rešitev algoritmov pogosto zahteva izvedbo funkcije. Odvisno od možnosti pisanja verige za računanje, se ta funkcija imenuje algoritemsko rešljiva ali netopljiva. Kot množica naravnih ali racionalnih števil, besed v končni abecedi N za stroj, se upošteva zaporedje množice B - besed v binarni kodni abecedi B = {0.1}. Rezultat izračuna upošteva tudi »nedefinirano« vrednost, ki se pojavi, ko algoritem visi. Za uresničitev funkcije je pomembno, da je v končni abecedi formalni jezik in rešljivost problema prepoznavanja pravilnih opisov.

Program za napravo

Programi za Turingov mehanizem so sestavljeni iz tabel, v katerih prva vrstica in stolpec vsebujejo znake zunanje abecede in vrednosti možnih notranjih stanj avtomata - notranje abecede. Tabelarni podatki so ukazi, ki jih zazna Turingov stroj. Rešitev težav se pojavi na ta način: črka, ki jo bere glava v celici, v kateri se trenutno nahaja, in notranje stanje glave avtomata določa, kateri ukaz naj se izvede. Natančneje, tak ukaz se nahaja na presečišču simbolov zunanje abecede in notranjega, ki so v tabeli.

Komponente za izračune

Za izgradnjo Turingovega stroja za reševanje ene specifične naloge je potrebno določiti naslednje parametre.

Zunanja abeceda. To je nekaj končnih nizov simbolov, označenih z znakom A, katerih sestavni elementi se imenujejo črke. Eden od njih - a0 - mora biti prazen. Na primer, abeceda Turingove naprave, ki dela z binarnimi številkami, izgleda takole: A = {0, 1, a0}.

Neprekinjen niz alfanumeričnih znakov, zapisanih na trak, se imenuje beseda.

Samodejni stroj je naprava, ki deluje brez človeškega poseganja. V Turingovem stroju ima več različnih stanj za reševanje problemov in se pod določenimi pogoji premika iz enega položaja v drugega. Kombinacija takih stanj vozička je notranja abeceda. Ima črkovno oznako oblike Q = {q1, q2 ...}. Ena od teh določil - q1 - bi morala biti prvotna, to je tisto, kar zažene program. Drugi nujni element je stanje q0, ki je končno, to pomeni, da zaključi program in napravo postavi v položaj zaustavitve.

Tabela preusmeritev. Ta komponenta je algoritem za obnašanje nosilca naprave, odvisno od trenutnega stanja stroja in vrednosti simbola, ki ga berete.

Algoritem za avtomat

Prevažanje Turingove naprave med delovanjem nadzoruje program, ki med vsakim korakom izvede zaporedje naslednjih dejanj:

1. Pisanje zunanjega abecednega znaka na mesto, vključno s praznim, z zamenjavo elementa, ki je bil v njem, vključno s praznim.
2. Premaknite se za en korak v levo ali desno.
3. Spremenite svoje notranje stanje.

Tako je pri pisanju programov za vsak par znakov ali položajev treba natančno opisati tri parametre: _i - element iz izbrane abecede A, smer premika vozička ("←" na levo, "→" na desno, "točka" - brez gibanja) in q _k je novo stanje naprave, na primer, ukaz 1 "←" q2 je nastavljen na "zamenjava znaka z 1, premakne glavo nosilca v levo za eno stopenjsko celico in izvede prehod v stanje q ₂ ".

Turingov stroj: primeri

Primer 1. Glede na nalogo izdelati algoritem, ki doda eno na zadnjo številko dane številke na traku. Vhodni podatki - beseda - številke celotnega decimalnega števila, zapisane v zaporednih celicah na traku. V začetnem trenutku se naprava nahaja nasproti desnega simbola - števila številke.

Odločitev. Če je zadnja številka enaka 9, jo je treba zamenjati z 0 in nato dodati še enemu prejšnjemu znaku. Program v tem primeru za to Turingovo napravo lahko zapišemo takole:

Tu je q ₁ stanje spreminjanja števila, q ₀ je zaustavitev. Če v q ₁ avtomat določi element iz serije 0..8, ga nadomesti z enim od 1..9 oziroma nato preklopi v stanje q ₀ , to pomeni, da se naprava ustavi. Če nosilec določi število 9, ga nadomesti z 0, nato se premakne v levo in se ustavi v stanju q ₁ . To gibanje se nadaljuje, dokler naprava ne določi števke, ki je manjša od 9. Če so vsi znaki enaki 9, se nadomestijo z ničlami, 0 nadomesti z vodilnim elementom, nosilec se premakne v levo in zapiše 1 v prazno celico. Naslednji korak bo prehod v stanje q ₀ - stop.

Primer 2. Glede na vrsto znakov, ki označujejo odpiranje in zapiranje oklepajev. Potrebno je zgraditi Turingovo napravo, ki bo odstranila par vzajemnih oklepajev, to je elemente, ki so urejeni v vrsti - “()”. Na primer, začetni podatki: “) (() (()”, odgovor mora biti: “) .. ((”. Rešitev: mehanizem, ki je v q ₁ , analizira skrajni levi element v vrstici.

Navedite q ₁ : če se pojavi simbol „(“), nato premaknite desno in pojdite v položaj q ₂ ; če je definiran „a ₀ “, se ustavite.

Stanje q ₂ : analiza oklepaja “(” za prisotnost para se izvede, v primeru naključja se izkaže “)”. Če je element par, se vrnite na levo in pojdite na q ₃ .

Stanje q ₃ : najprej izbrišite simbol “(” in nato “)” in pojdite na q ₁ .