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

Система команд

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

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

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

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

Эти команды означают, что, находясь во внутреннем состоянии ${\displaystyle q_{i}}$ и воспринимая ячейки лент в состояниях ${\displaystyle a_{1}\dots a_{s}}$ , машина заменяет ${\displaystyle q_{i}}$ на ${\displaystyle q_{\alpha }}$ , после чего сдвигает ленты в направлениях ${\displaystyle T_{\alpha _{1}}\dots T_{\alpha _{s}}}$ ( ${\displaystyle T_{-1},T_{1},T_{0}}$ означают соответственно сдвиг ленты на одну ячейку влево, вправо и оставление ленты неподвижной).

Так как ${\displaystyle 1}$ есть состояние самой левой ячейки, то в командах из ${\displaystyle a_{\lambda }=1}$ должно следовать неравенство ${\displaystyle \alpha _{\lambda }\neq -1}$ .

Свойства

• Для каждой частично рекурсивной функции ${\displaystyle f(x)}$ существует трёхленточная машина Минского, вычисляющая эту функцию, то есть переходящая из конфигурации ${\displaystyle {10}^{x-1}q_{1}0q_{1}1q_{1}1}$ в конфигурацию ${\displaystyle {10}^{f(x)-1}q_{0}0q_{0}1q_{0}1}$ , если ${\displaystyle f(x)}$ определено, и работающая вечно, если ${\displaystyle f(x)}$ не определено .
• Для каждой частично рекурсивной функции ${\displaystyle f(x)}$ существует двухленточная машина Минского, которая для любого натурального ${\displaystyle x}$ перерабатывает число ${\displaystyle 2^{x}}$ в число ${\displaystyle 2^{f(x)}}$ , если ${\displaystyle f(x)}$ определено, и работающая безостановочно, не переходя в заключительное внутреннее состояние ${\displaystyle q_{0}}$ , если ${\displaystyle f(x)}$ не определено
• Для каждой частично рекурсивной функции ${\displaystyle f(x)}$ существует , перерабатывающий ${\displaystyle 2^{2^{x}}}$ в ${\displaystyle 2^{2^{f(x)}}}$ , программа которого состоит лишь из вида {{pb

  ${\displaystyle {\overline {\underline {|\,{\times 2}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 3}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 2}\,|\,\alpha \,|\,\beta \,|}}}.}$

Регистровая машина

Регистровая (или программная) машина состоит из конечного числа регистров, хранящих неотрицательные целые числа и управляющий программный блок, который выполняет операции над содержимым регистров согласно программе (упорядоченной последовательности команд). Команды содержат сведения о выполняемой операции, регистре, номерах одной или двух других команд .

Для всякой машины Тьюринга всегда можно построить эквивалентную ей регистровую машину, использующую два регистра и выполняющую четыре операции :

• ${\displaystyle {\underline {\overline {|\,a^{0}\,|}}}}$ — занести ${\displaystyle 0}$ в регистр ${\displaystyle a}$ ;
• ${\displaystyle {\underline {\overline {|\,a'\,|}}}}$ — добавить ${\displaystyle 1}$ к содержимому регистра ${\displaystyle a}$ и перейти к новой команде;
• ${\displaystyle {\underline {\overline {|\,a^{-}(n)\,|}}}}$ — вычесть ${\displaystyle 1}$ из содержимого регистра ${\displaystyle a}$ и перейти к следующей команде или перейти к команде ${\displaystyle n,}$ если в нём уже содержится ${\displaystyle 0}$ ;
• ${\displaystyle {\underline {\overline {|\,n\,|}}}}$ — перейти к команде ${\displaystyle n}$ .

Двухленточная машина Минского полностью эквивалентна регистровой машине с двумя регистрами. Если длины лент от считывающих головок до концов рассматривать как представления чисел ${\displaystyle m}$ и ${\displaystyle n}$ , операции ${\displaystyle m^{+}}$ и ${\displaystyle n^{+}}$ сдвигают головки в сторону от концов, а ${\displaystyle m^{-}}$ и ${\displaystyle n^{-}}$ к концам, при условии, что не достигнут конец ленты , полностью эквивалентна регистровой (программной) машине с двумя регистрами, в один из регистров которой помещается нуль, а в другой число ${\displaystyle 2^{a}3^{m}5^{n}}$ .

См. также

• Машина Тьюринга

Примечания

Литература

• Минский М. Вычисления и автоматы. — М. : Мир, 1971. — 360 с.