Мурова машина

У теорији израчунљивости, Мурова машина је коначан аутомат чије тренутне излазне вредности су одређене само њеним тренутним стањем. Ово је у супротности са Милијевом машином, чије су излазне вредности одређене и њеним тренутним стањем и вредностима њених улаза. Као и друге машине коначног стања, у Муровим машинама, улаз обично утиче на следеће стање. Дакле, улаз може индиректно утицати на следеће излазе, али не и на тренутни или наредни излаз. Мурова машина је добила име по Едварду Ф. Муру, који је представио концепт у раду из 1956. „Мисаони-експерименти на секвенцијалним машинама."^[1]

Формална дефиниција

Мурова машина се може дефинисати као 6-торка (S, S0, Σ, O, δ, G) 0 која се састоји од следећи:

Коначан скуп стања S
Почетно стање (који се назива и почетно стање) S0 који је елемент S
Коначан скуп који се назива улазна алфабет Σ
Коначан скуп који се зове излазна алфабет О
Прелазна функција δ : S × Σ → S мапирање стања и улазног алфабета у следеће стање
Излазна функција Г : S → О мапирање сваког стања у излазни алфабет

Мурова машина се може сматрати ограниченим типом претварача коначног стања. ^[2]

Литература

^ 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]