Mașina lui Minsky

Aparatul Minsky este o mașină Turing cu mai multe benzi , în care benzile din stânga nu se acumulează (limitate în lungime), toate celulele de bandă, cu excepția celor din stânga, sunt întotdeauna goale, iar stările celulelor din stânga sunt constantă [1] . Numit și mașină de înregistrare . Conceptul a fost introdus în știință de M. Minsky [2]

Sistem de comandă

Alfabetul extern (un set de simboluri înregistrate pe casete) al mașinii Minsky este format din simbolurile . Simbol de stare gol , toate celulele din stânga tuturor benzilor sunt în stare . $0,1$ $0$ $unu$

O descriere completă a aparatului de bandă Minsky este dată prin indicarea totalității tuturor stărilor sale interne și a programului mașinii, constând din comenzi de forma $n$ $q_{i},\i=1,\dots ,n$

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

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

Aceste comenzi înseamnă că, fiind în stare internă și percepând celulele benzilor în stările , mașina înlocuiește cu , după care deplasează benzile în direcții ( înseamnă, respectiv, deplasarea benzii cu o celulă către stânga, dreapta și lăsând banda nemișcată). $q_{i}$ $a_{1}\dots a_{s)$ $q_{i}$ $q_{\alpha )$ $T_{\alpha _{1}}\dots T_{\alpha _{s}}$ ${\displaystyle T_{-1},T_{1},T_{0))$

Deoarece există o stare a celulei din stânga, atunci inegalitatea trebuie să urmeze în comenzile de la . $unu$ $a_{\lambda}=1$ $\alpha _{\lambda}\neq -1$

Proprietăți

Pentru fiecare funcție parțial recursivă, există o mașină Minsky cu trei benzi care evaluează această funcție, adică trece de la configurație la configurare dacă este definită și rulează pentru totdeauna dacă nu este definită [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)$
Pentru fiecare funcție parțial recursivă, există o mașină Minsky cu două benzi care, pentru orice număr natural , convertește un număr într-un număr dacă este definit și rulează non-stop fără a trece la starea internă finală dacă nu este definit [1] $f(x)$ $X$ $2^{x}$ $2^{f(x))$ $f(x)$ $q_{0}$ $f(x)$
Pentru fiecare funcție parțial recursivă, există un algoritm operator care procesează în , al cărui program este format numai din ordine de forma [1] {{pb $f(x)$ $2^{2^{x))$ $2^{2^{f(x)))$ ${\overline {\underline {|\,{\times 2}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 3}\,| \,\alpha \,|}}},{\overline {\subline {|\,{\times 2}\,|\,\alpha \,|\,\beta \,|}}}.$

Înregistrează mașina

O mașină de registru (sau program) constă dintr-un număr finit de registre care stochează numere întregi nenegative și un bloc de program de control care efectuează operații asupra conținutului registrelor conform programului (o secvență ordonată de comenzi). Comenzile conțin informații despre operația efectuată, registru, numere ale uneia sau două alte comenzi [3] .

Pentru orice mașină Turing , este întotdeauna posibil să se construiască o mașină de registru echivalentă care folosește doi registre și efectuează patru operații [4] :

${\underline {\overline {|\,a^{0}\,|)))$ - se înscrie în registru ; $0$ $A$
${\underline {\overline {|\,a'\,|)))$ - adăugați la conținutul registrului și mergeți la noua comandă; $unu$ $A$
${\underline {\overline {|\,a^{-}(n)\,|)))$ - scădeți din conținutul registrului și treceți la următoarea comandă sau mergeți la comanda dacă aceasta conține deja ; $unu$ $A$ $n,$ $0$
${\underline {\overline {|\,n\,|)))$ - du-te la echipa . $n$

Aparatul cu două benzi a lui Minsky este complet echivalent cu o mașină de înregistrare cu două registre. Dacă lungimile benzilor de la capetele de citire până la capete sunt considerate ca reprezentări ale numerelor și , operațiile și deplasarea capetelor de la capete, și la capete, cu condiția ca capătul benzii să nu fie atins [5] ] , este complet echivalent cu o mașină de registru (software) cu două registre , în unul dintre registrele cărora este plasat zero, iar în celălalt numărul [6] . $m$ $n$ ${\displaystyle m^{+))$ ${\displaystyle n^{+))$ $m^{-}$ $n^{-}$ $2^{a}3^{m}5^{n}$

Vezi și

mașină Turing
Algoritmul operatorului

Note

↑ 1 2 3 4 Maltsev AI Algoritmi și funcții recursive. - M., Nauka, 1986. - p. 304-315
↑ Minsky ML Recursivă insolvabilitatea problemei lui Post a Tag și subiecte în teoria mașinilor Turing . - Ann. Math., 1961, 74, p. 437-455.
↑ Minsky, 1971 , p. 244.
↑ Minsky, 1971 , p. 304.
↑ Minsky, 1971 , p. 209.
↑ Minsky, 1971 , p. 311.306.

Literatură

Minsky M. Calcule și automate. — M .: Mir, 1971. — 360 p.