Murova mašina

U teoriji izračunljivosti, Murova mašina je konačan automat čije trenutne izlazne vrednosti su određene samo njenim trenutnim stanjem. Ovo je u suprotnosti sa Milijevom mašinom, čije su izlazne vrednosti određene i njenim trenutnim stanjem i vrednostima njenih ulaza. Kao i druge mašine konačnog stanja, u Murovim mašinama, ulaz obično utiče na sledeće stanje. Dakle, ulaz može indirektno uticati na sledeće izlaze, ali ne i na trenutni ili naredni izlaz. Murova mašina je dobila ime po Edvardu F. Muru, koji je predstavio koncept u radu iz 1956. „Misaoni-eksperimenti na sekvencijalnim mašinama."^[1]

Formalna definicija

Murova mašina se može definisati kao 6-torka (S, S0, Σ, O, δ, G) 0 koja se sastoji od sledeći:

Konačan skup stanja S
Početno stanje (koji se naziva i početno stanje) S0 koji je element S
Konačan skup koji se naziva ulazna alfabet Σ
Konačan skup koji se zove izlazna alfabet O
Prelazna funkcija δ : S × Σ → S mapiranje stanja i ulaznog alfabeta u sledeće stanje
Izlazna funkcija G : S → O mapiranje svakog stanja u izlazni alfabet

Murova mašina se može smatrati ograničenim tipom pretvarača konačnog stanja. ^[2]

Literatura

^ Moore, Edward F (1956). "Gedanken-experiments on Sequential Machines". Automata Studies, Annals of Mathematical Studies. Princeton, N.J.: Princeton University Press (34): 129–153.
^ L.Nađ, M.Damnjanović (2006). Skripta iz digitalne elektronike

[1] Moore, Edward F (1956). "Gedanken-experiments on Sequential Machines". Automata Studies, Annals of Mathematical Studies. Princeton, N.J.: Princeton University Press (34): 129–153.

[2] L.Nađ, M.Damnjanović (2006). Skripta iz digitalne elektronike

[1]

[2]