Turingov stroj

Program Turingov stroj je namenjen simuliranju delovanja. Vanj vnesemo pravila in vhodne podatke, program pa simulira delovanje sistema.

Program

Primer delovanja

Poglejmo si primer naloge. Turingov stroj je podan z ukazi:

  • (1, 0, 0, 1, R)
  • (1, 1, 0, 2, R)
  • (2, 1, 1, 2, R)
  • (2, 0, 1, 1, R)

V kaj se preslikajo vrednosti 1,1,0,1,0,0?

Primer delovanja

Torej odgovor na zgornjo nalogo: … b, 0, 1, 1, 0, 1, 0, b …

Kaj sploh je Turingov stroj?

Turingov stroj je miselni stroj , abstrakten model, ki si ga je izmislil angleški matematik, logičar, računalničar… Alan Turing. Z njim lahko matematično opredelimo nek algoritem oz mehanski postopek.

Operacije so v stroju omejene na branje in pisanje po neskončnem traku. Po njem se premika glava ki bere/piše podatke. Kot je omenjeno je trak neomejen v levo in desno stran, kar mu omogoči neskončno veliko pomnilnika. Stroj je lahko v večih različnih stanjih kar pripomore k sledenju pravilom, ki jih definiramo.

Kako definiramo pravila?

Pravilo: (i, j, k, s, d)

Če je v stanju (i) in je prebran simbol (j) potem:
zapiši simbol (k) na trak
spremeni stanje v stanje (s)
premakni se (d/l)
ponovi.

Katere podatke lahko uporabimo?

Po dogovoru se za stanja uporabljajo števila, za simbole 1 in 0, za premik pa L (levo) in R (right).

Za simbole in stanja pa lahko uporabite tudi črke.

Potek izvajanja

  1. Pridobi trenutno stanje
  2. Preveri, če je trenutno stanje definirano v pravilih
  3. Če je, preberi polje na katerega kaže glava
  4. Preveri, če je v pravilih, kjer je definirano stanje tudi definiran simbol, ki mora biti prebran
  5. Potem zapiši simbol na trak
  6. Spremeni stanje v stanje, ki je definirano v pravilu
  7. Premakni se levo ali desno
  8. Ponovi dokler prideš do trenutka ko za stanje in prebran simbol ne najdeš pravila

Sistemske zahteve

  • . NET 4.5
  • Windows XP, Vista, 7, 8, 8.1, 10

Prenos

Setup.msi: tukaj.

TuringovStroj.zip: tukaj.