Turingova mašina

Turingova mašina^[1][2] je matematički model koji je izumio britanski matematičar Alan Turing, za stvaranje klase od predvidljivih funkcija. Predstavio ju je David Hilbert 1920, specijalno za rješavanje problema u odlučivanju, u djelu On Computable Numbers, with an Application to the Entscheidungsproblem. Alan Turing je namjeravao stvoriti jedan model matematički radećeg čovjeka.

Turingova mašina se sastoji od:

• jedne neograničeno duge trake sa neograničeno mnogo polja. U svakom od tih polja se može snimiti jedan znak.
• jedne programski upravljanje čitače odnosno pisače glave, koja se po traki samo po jedno polje pokreće i znakove mijenja.

Turingova mašina modificira unos na traci po jednom datom programu. Ako je preračunavanje završeno, onda se rješenje nađe na traci. Tako se svakoj ulaznoj vrijednosti dodijeljuje izlazna. Turingova mašina ne mora za sve ulazne vrijednosti da staje. U tom slučaju je funkcija unosa nedefinisana.

Kao rješenje se nekad definiše redoslijed znakova, koji poslije zastavljanja na traci stoji. Turingova mašina se najčesće koristi (također sa mnogim drugim automatima) za probleme odlučivanja, znači za pitanja, koja se sa da ili ne mogu odovoriti. Pri tome se zaustavljanje Turingove mašine interpretira kao da, a ne zaustavljanje kao ne.

Primjer

Promjena stanja

Sljedeća deterministička jednotrakna turing mašina ${\displaystyle M}$ očekuje jedan niz od jedinica na traci. Ona udvostručuje broj jedinica pri čemu jedan prazan simbol ostaje u sredini. Iz "111" se naprimjer pravi "1110111". Pisaća, odnosno čitaća glava, se inicijalno nalazi na prvoj jedinici. Početno stanje je ${\displaystyle s1}$, a zadnje stanje je ${\displaystyle s6}$. Nula stoji za prazno mjesto i traka je sve do napisanih jedinica popunjena praznim znakovima.

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,s1,0,F)}$

* ${\displaystyle Q=\{s1,s2,s3,s4,s5,s6\}}$
* ${\displaystyle \Sigma =\{1\}}$
* ${\displaystyle \Gamma =\{1,0\}}$
* ${\displaystyle F=\{s6\}}$


 staro procit. pisa. novo  glava-   staro procit. pis. novo  Glava-
 stan. simbol    simbol stan. pravac   stan. simbol    simbol stan. pravac
 ------------------------------------   ------------------------------------  
  s1    1   ->    0     s2     R         s4    1   ->    1     s4     L 
  s1    0   ->    0     s6     0         s4    0   ->    0     s5     L
  s2    1   ->    1     s2     R         s5    1   ->    1     s5     L  
  s2    0   ->    0     s3     R         s5    0   ->    1     s1     R
  s3    0   ->    1     s4     L          
  s3    1   ->    1     s3     R

R - right(desno) L - left(lijevo) 0 - nema pomjeranja

${\displaystyle M}$ prolazi naprimjer kod unosa "11" u sljedeće stanje, pri čemu je trenutna pozicija glave debelo napisana:

  Korak Stanje Traka     Korak Stanje Traka
 -------------------    -------------------
    1    s1    11000      9     s2    10010 
    2    s2    01000      10    s3    10010
    3    s2    01000      11    s3    10010
    4    s3    01000      12    s4    10011
    5    s4    01010      13    s4    10011
    6    s5    01010      14    s5    10011
    7    s5    01010      15    s1    11011
    8    s1    11010      16    s6    -stani-

Također pogledajte

• Algoritam
• Claude E. Shannon
• Von Neumannova arhitektura

Reference

1. Minsky 1967:107 "U svom radu iz 1936. A. M. Turing je definisao klasu apstraktnih mašina koje sada nose njegovo ime. Tjuringova mašina je mašina konačnog stanja povezana sa posebnom vrstom okruženja - njenom trakom - u kojoj može da pohranjuje (i kasnije oporavi) nizove simbola", također Stone 1972:8 gdje je riječ "mašina" u navodnicima.
2. De Mol, Liesbeth (2021), Turing Machines (Winter 2021 izd.), Metaphysics Research Lab, Stanford University, pristupljeno 2024-08-20 CS1 održavanje: nepreporučeni parametar (link)

Vanjski linkovi

• https://www.britannica.com/technology/Turing-machine

Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva hijerarhija	Gramatike	Jezici	Minimalni automat
Tip 0	Neograničenih produkcija	Rekurzivno prebrojiv	Turingova mašina
n/a	(nema uobičajenog imena)	Rekurzivni	Odlučitelj
Tip 1	Kontekstno ovisna	Kontekstno ovisni	Linearno ograničen
n/a	Indeksirana	Indeksirani	Ugniježđenog stoga
Tip 2	Kontekstno neovisna	Kontekstno neovisni	Nedeterministički potisni
n/a	Deterministička kontekstno neovisna	Deterministički kontekstno neovisni	Deterministički potisni
Tip 3	Regularna	Regularni	Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.