Univerzalni stroj

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Univerzalni stroj je tak Turingov stroj U, da velja za vsak Turingov stroj T in vsak trak t:

  • če se T z začetnim trakom t ustavi in je vsebina traku na koncu t', potem se U z začetnim trakom opis(T),t ustavi in je vsebina traku na koncu t'.
  • če T z začetnim trakom t divergira ali blokira, potem tudi U z začetnim trakom opis(T),t divergira ali blokira.

Zapis opis(T),t pomeni, da na trak najprej zapišemo opis stroja T, nato pa še vsebino traku t.

Povedano z drugimi besedami, univerzalni stroj je tak stroj, ki zna simulirati poljuben stroj (tudi samega sebe). Moderni osebni računalniki so univerzalni von Neumannovi stroji.

Glej tudi

Osebna orodja