Minsky autója

A Minsky gép egy többszalagos Turing-gép , amelyben a bal oldali szalagok nem épülnek fel (korlátozott hosszban), minden szalagcella, a bal szélsők kivételével, mindig üres, a bal szélső cellák állapota pedig állandó [1] . Regisztrációs gépnek is nevezik . A koncepciót M. Minsky vezette be a tudományba [2]

Parancsrendszer

A Minsky gép külső ábécéje (szalagra rögzített szimbólumok halmaza) a szimbólumokból áll . Üres állapotszimbólum , az összes szalag bal szélső cellája állapotban van . $0.1$ $0$ $egy$

A Minsky szalagos gép teljes leírását az összes belső állapotának és a gépi programnak a megadásával adjuk meg, amely a következő típusú parancsokból áll. $n$ $q_{i},\ i=1,\dots ,n$

q_{i}a_{1}\dots a_{s}\to q_{\alpha }T_{\alpha _{1))\dots T_{\alpha _{s)),

hol ; ; ; . $i = 1, \pontok, n$ $a_{\lambda }=0,1$ $\alpha =0,1,\pontok ,n$ $\alpha _{\lambda }=0,1,-1$

Ezek a parancsok azt jelentik, hogy belső állapotban lévén, a szalagok celláit az állapotokban észlelve a gép helyettesíti a -val , majd a szalagokat irányokba tolja ( ezek azt jelentik, hogy a szalag egy cellával eltolódik a balra, jobbra és a szalagot mozdulatlanul hagyva). $q_{i}$ ${\displaystyle a_{1}\dots a_{s))$ $q_{i}$ ${\displaystyle q_{\alpha ))$ $T_{\alpha _{1}}\dots T_{\alpha _{s}}$ ${\displaystyle T_{-1},T_{1},T_{0))$

Mivel a bal szélső cella állapota van, ezért az egyenlőtlenségnek következnie kell a parancsokban . $egy$ $a_{\lambda }=1$ $\alpha _{\lambda }\neq -1$

Tulajdonságok

Minden részben rekurzív függvényhez van egy háromszalagos Minsky-gép, amely kiértékeli ezt a függvényt, azaz konfigurációról konfigurációra lép, ha definiálva van, és örökké fut, ha nincs megadva [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)$
Minden részben rekurzív függvényhez létezik egy kétszalagos Minsky-gép, amely bármely természetes szám esetén számmá alakítja a számot , ha definiált, és megállás nélkül fut anélkül, hogy átmenne a végső belső állapotba , ha nincs megadva [1] $f(x)$ $x$ $2^{x}$ ${\displaystyle 2^{f(x)))$ $f(x)$ $q_{0}$ $f(x)$
Minden részlegesen rekurzív függvényhez tartozik egy operátoralgoritmus -be való feldolgozás , melynek programja csak [1] {{pb formátumú parancsokból áll $f(x)$ $2^{2^{x))$ $2^{2^{f(x)))$ ${\overline {\underline {|\,{\times 2}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 3}\,| \,\alpha \,|}}},{\overline {\underline {|\,{\times 2}\,|\,\alpha \,|\,\beta \,|}}}.$

Gép regisztrálása

Egy regiszter (vagy program) gép véges számú, nem negatív egész számokat tároló regiszterből és egy vezérlő programblokkból áll, amely a programnak megfelelően műveleteket hajt végre a regiszterek tartalmán (parancsok rendezett sorozata). A parancsok információkat tartalmaznak az éppen végrehajtott műveletről, regiszterről, egy vagy két másik parancs számairól [3] .

Bármely Turing -géphez mindig létre lehet hozni egy ekvivalens regisztergépet, amely két regisztert használ és négy műveletet hajt végre [4] :

${\displaystyle {\underline {\overline {|\,a^{0}\,|))))$ - be kell írni a nyilvántartásba ; $0$ $a$
${\displaystyle {\underline {\overline {|\,a'\,|))))$ - adja hozzá a regiszter tartalmát, és lépjen az új parancsra; $egy$ $a$
${\displaystyle {\underline {\overline {|\,a^{-}(n)\,|))))$ - vonja le a regiszter tartalmát és lépjen a következő parancsra, vagy lépjen a parancsra , ha az már tartalmazza ; $egy$ $a$ $n,$ $0$
${\displaystyle {\underline {\overline {|\,n\,|))))$ - menj a csapathoz . $n$

Minsky kétszalagos gépe teljesen egyenértékű egy két regiszteres regisztergéppel. Ha a szalagok hosszát az olvasófejektől a végekig a számok és a számok reprezentációjának tekintjük , a műveletek és a fejek eltolása a végektől, és a végek felé, feltéve, hogy a szalag végét nem éri el [5 ] , teljesen egyenértékű egy két regiszterrel rendelkező regiszter (szoftver) géppel, amelynek egyik regiszterében nulla, a másikban pedig a [6] szám található . $m$ $n$ ${\displaystyle m^{+))$ $n^{+}$ $m^{-}$ $n^{-}$ $2^{a}3^{m}5^{n}$

Lásd még

Turing gép
Operátori algoritmus

Jegyzetek

↑ 1 2 3 4 Maltsev AI Algoritmusok és rekurzív függvények. - M., Nauka, 1986. - p. 304-315
↑ Minsky ML Post-probléma, a Tag és a Turing- gépek elméletének témakörének rekurzív megoldhatatlansága . — Ann. Math., 1961, 74, p. 437-455.
↑ Minsky, 1971 , p. 244.
↑ Minsky, 1971 , p. 304.
↑ Minsky, 1971 , p. 209.
↑ Minsky, 1971 , p. 311.306.

Irodalom

Minsky M. Számítások és automaták. — M .: Mir, 1971. — 360 p.