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]
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 .
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.
hol ; ; ; .
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).
Mivel a bal szélső cella állapota van, ezért az egyenlőtlenségnek következnie kell a parancsokban .
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] :
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ó .