Turingi masin

Allikas: Vikipeedia

Alan Turingi poolt 1937. aastal kirjeldatud niinimetatud Turingi masin on lihtne abstraktne automaat või kujuteldav arvuti, mida kasutatakse arvutatavuse ja selle piiride uurimiseks.

Turingi masin koosneb mõlemas suunas lõpmata pikast lindist, mis on jagatud ühesugusteks pesadeks. Iga pesa võib olla kahes asendis: märgiga või märgita. Turingi masinal on viis võimalikku operatsiooni: teha samm vasakule, teha samm paremale, kirjutada pessa märk, kustutada pesast märk ja kontrollida, kas pesas on märk.

Universaalse Turingi masina korral määrab lint ära ka teise Turingi masina. Algselt on sümbolid lõplikus hulgas pesades, ülejäänutes on tühikud. Sisemälu on igal ajahetkel mingis konkreetses seisundis ja taoliste seisundite hulk on lõplik.

Masina tegevusi juhtivad reeglid on deterministlikud ja on defineeritud seisunditabelis. Iga seisundi ja iga lindil oleva sümboli kohta on tabelis kirje masina poolse tegevuse ja järgmise seisundi kohta.

Kuna masina seisundite ja lindil olevate sümbolite arv on lõplik, siis on ka tabel lõpliku suurusega ja seda saab hoida lindil. Eksisteerib universaalne Turingi masin Mu, mis on võimeline jäljendama iga Turingi masinat, sealhulgas iseennast. Kui masina M seisunditabel on kirjutatud Mu lindile, siis teostab universaalne masin Mu samu operatsioone mis M. Universaalne masin teeb seda, leides masina M seisunditabeli järgi selle tegevused iga võimaliku sisendi korral.

[redigeeri] Vaata ka

[redigeeri] Välislingid

[redigeeri] Kirjandus

  • Reimo Palm, Rein Prank "Sissejuhatus matemaatilisse loogikasse", Tartu 1994