Minského auto

Stroj Minsky je vícepáskový Turingův stroj , ve kterém se pásky nalevo neshromažďují (omezená délka), všechny buňky pásky, kromě těch nejvíce vlevo, jsou vždy prázdné a stavy buněk nejvíce vlevo jsou konstantní [1] . Také se nazývá registrační stroj . Pojem zavedl do vědy M. Minsky [2]

Příkazový systém

Vnější abeceda (soubor symbolů zaznamenaných na páskách) stroje Minsky se skládá ze symbolů . Prázdný státní symbol , všechny buňky zcela vlevo na všech páskách jsou ve stavu . $0.1$ $0$ $jeden$

Úplný popis páskového stroje Minsky je dán uvedením souhrnu všech jeho vnitřních stavů a programu stroje, který se skládá z příkazů ve tvaru $n$ $q_{i},\ i=1,\tečky ,n$

q_{i}a_{1}\tečky a_{s}\to q_{\alpha }T_{\alpha _{1))\tečky T_{\alpha _{s)),

kde ; ; ; . $i = 1, \tečky, n$ $a_{\lambda }=0,1$ $\alpha =0,1,\tečky ,n$ $\alpha _{\lambda }=0,1,-1$

Tyto příkazy znamenají, že v interním stavu a vnímání buněk pásek ve stavech stroj nahradí znakem , načež posune pásky ve směrech ( znamenají tedy posunutí pásky o jednu buňku do doleva, doprava a ponechání pásky nehybné). $Qi}$ ${\displaystyle a_{1}\tečky a_{s))$ $Qi}$ ${\displaystyle q_{\alpha ))$ $T_{\alpha _{1}}\dots T_{\alpha _{s}}$ ${\displaystyle T_{-1},T_{1},T_{0))$

Vzhledem k tomu , že existuje stav buňky zcela vlevo, pak musí nerovnost následovat v příkazech z . $jeden$ $a_{\lambda }=1$ $\alpha _{\lambda }\neq -1$

Vlastnosti

Pro každou částečně rekurzivní funkci existuje třípáskový stroj Minsky, který tuto funkci vyhodnocuje, tj. přechází od konfigurace ke konfiguraci , pokud je definována, a běží navždy, pokud není definována [1] . $f(x)$ ${10}^{x-1}q_{1}0q_{1}1q_{1}1$ ${10}^{f(x)-1}q_{0}0q_{0}1q_{0}1$ $f(x)$ $f(x)$
Pro každou částečně rekurzivní funkci existuje dvoupáskový Minsky stroj, který pro jakékoli přirozené číslo převede číslo na číslo , pokud je definováno, a běží nepřetržitě bez přechodu do konečného vnitřního stavu , pokud není definován [1] $f(x)$ $X$ $2^{x}$ ${\displaystyle 2^{f(x)))$ $f(x)$ $q_{0}$ $f(x)$
Pro každou částečně rekurzivní funkci existuje operátorský algoritmus zpracování do , jehož program se skládá pouze z řádů tvaru [1] {{pb $f(x)$ $2^{2^{x))$ $2^{2^{f(x)))$ ${\overline {\underline {|\,{\times 2}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 3}\,| \,\alpha \,|}}},{\overline {\podtržení {|\,{\times 2}\,|\,\alpha \,|\,\beta \,|}}}.$

Registrovat stroj

Registrový (nebo programový) stroj se skládá z konečného počtu registrů, které ukládají nezáporná celá čísla , a bloku řídicího programu, který provádí operace s obsahem registrů podle programu (uspořádaná sekvence příkazů). Příkazy obsahují informace o prováděné operaci, registr, čísla jednoho nebo dvou dalších příkazů [3] .

Pro jakýkoli Turingův stroj je vždy možné zkonstruovat ekvivalentní registrační stroj, který používá dva registry a provádí čtyři operace [4] :

${\displaystyle {\underline {\overline {|\,a^{0}\,|))))$ - zapsat se do registru ; $0$ $A$
${\displaystyle {\podtržení {\overline {|\,a'\,|))))$ - přidat do obsahu registru a přejít na nový příkaz; $jeden$ $A$
${\displaystyle {\underline {\overline {|\,a^{-}(n)\,|))))$ - odečtěte od obsahu registru a přejděte na další příkaz nebo přejděte na příkaz , pokud již obsahuje ; $jeden$ $A$ $n,$ $0$
${\displaystyle {\podtržení {\overline {|\,n\,|))))$ - jít do týmu . $n$

Minského dvoupáskový stroj je zcela ekvivalentní registračnímu stroji se dvěma registry. Jsou-li délky pásek od čtecích hlav ke koncům považovány za znázornění čísel a , operace a posunutí hlav od konců a ke koncům za předpokladu, že nedosáhne konce pásky [5 ] , je zcela ekvivalentní registračnímu (softwarovému) stroji se dvěma registry , v jednom z nich je umístěna nula a ve druhém čísle [6] . $m$ $n$ ${\displaystyle m^{+))$ ${\displaystyle n^{+))$ $m^{-}$ $n^{-}$ ${\displaystyle 2^{a}3^{m}5^{n))$

Viz také

Turingův stroj
Algoritmus operátora

Poznámky

↑ 1 2 3 4 Maltsev AI Algoritmy a rekurzivní funkce. - M., Nauka, 1986. - str. 304-315
↑ Minsky ML Rekurzivní neřešitelnost Postova problému Tag a témat teorie Turingových strojů . — Ann. Math., 1961, 74, str. 437-455.
↑ Minsky, 1971 , str. 244.
↑ Minsky, 1971 , str. 304.
↑ Minsky, 1971 , str. 209.
↑ Minsky, 1971 , str. 311,306.

Literatura

Minsky M. Výpočty a automaty. — M .: Mir, 1971. — 360 s.