Машина Минского

---

Машина Минского — многоленточная машина Тьюринга, у которой ленты слева не надстраиваются (ограничены по длине), все ячейки лент, за исключением самых левых, всегда пусты, а состояния самых левых ячеек постоянны^[1]. Также называется регистровая машина. Понятие ввёл в науку М. Минский^[2]

Внешний алфавит (совокупность символов, записанных на лентах) машины Минского состоит из символов ${\displaystyle 0,1}$. Символ пустого состояния ${\displaystyle 0}$, все самые левые клетки всех лент находятся в состоянии ${\displaystyle 1}$.

Полное описание ${\displaystyle n}$ — ленточной машины Минского задаётся указанием совокупности всех её внутренних состояний ${\displaystyle q_{i},\ i=1,\dots ,n}$ и программы машины, состоящей из команд вида

где ${\displaystyle i=1,\dots ,n}$; ${\displaystyle a_{\lambda }=0,1}$; ${\displaystyle \alpha =0,1,\dots ,n}$; ${\displaystyle \alpha _{\lambda }=0,1,-1}$.

---