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

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

уреди

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

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

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

Литература

уреди
  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