Turingov stroj

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Turingov stroj je matematični opis preprostega računskega stroja, ki sestoji iz:

Trak
Neskončen trak iz celic c_0, c_1, c_2, \ldots. Vsaka celica je prazna, kar označimo z znakom P, ali pa je v njej zapisana ničla 0 ali enica 1.
Bralno-pisalna glava
Stroj ima glavo, ki je v vsakem trenutku nad eno celico. Tako stroj lahko prebere vsebino celice, ali vanjo zapiše enega od znakov P, 0, 1. Stroj lahko glavo pomakne levo ali desno. Če jo pomakne levo od prve celice, se stroj ustavi.
Program
Končno zaporedje ukazov, ki povejo, kaj naj stroj počne (glej podrobnejši opis spodaj).
Trenutno stanje
Stroj ima končen nabor stanj S_0, \ldots, S_n. Na začetku je v stanju S0. Stanje se lahko ob izvršitvi ukaza zamenja.

Ukazi

Vsak ukaz je urejena četverica

SiduSj,

kjer sta Si in Sj stanji, d \in \{0,1,P\} je znak in u \in \{0,1,P,L,D\} ukaz. Tako četverica pomeni: če je stroj v stanju Si in je pod glavo zapisan znak d, izvedi ukaz u in nastavi stanje na Sj. Pomen ukaza u je:

  • 0: na trak zapiši ničlo
  • 1: na trak zapiši enico
  • P: na trak zapiši prazno (pobriši vsebino celice)
  • L: premakni glavo v levo
  • D: premakni glavo v desno

Izvajanje programa

(Pravila, kako se izvede program, kdaj stroj blokira, divergira in konča izvajanje.)

Program začnemo izvajati pri ukazu 0. Glava je na začetku skrajno levo.

Stroj se ustavi, če pomaknemo glavo levo od prve celice. Stroj blokira, če ni primernega naslednjega koraka ali pa jih je več.

Kaj dela stroj?

MOŽNOSTI:

         1) Računa in se ustavi.
         2) Računa in blokira.
         3) Se nikoli ne ustavi torej divergira.

Primer

Naslednji program izračuna funkcijo naslednik, pri čemer je število n na traku predstavljeno v "eniškem" zapisu kot zaporedje n enic in ničla:

S01DS0 (pomikaj se v desno dokler vidiš enice)
S001S1 (ko vidiš ničlo, zapiši enico, nato)
S11DS2 (se premakni v desno in)
S2P0S3 (zapiši ničlo ter)
S30LS3 (se pomikaj levo dokler ne prideš na začetek traku)
S31LS3

Glej tudi

Osebna orodja