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

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

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

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

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

$q_i{a}_1\dots a_s\to q_{\alpha }{T}_{{\alpha }_1}\dots T_{{\alpha }_s},$

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

Эти команды означают, что, находясь во внутреннем состоянии $q_i$ и воспринимая ячейки лент в состояниях $a_1\dots a_s$, машина заменяет $q_i$ на $q_{\alpha }$, после чего сдвигает ленты в направлениях $T_{{\alpha }_1}\dots T_{{\alpha }_s}$ ($T_{-1},T_1,T_0$ означают соответственно сдвиг ленты на одну ячейку влево, вправо и оставление ленты неподвижной).

Так как $1$ есть состояние самой левой ячейки, то в командах из $a_{\lambda }=1$ должно следовать неравенство ${\alpha }_{\lambda }\ne -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)$ не определено.
• Для каждой частично рекурсивной функции $f(x)$ существует двухленточная машина Минского, которая для любого натурального $x$ перерабатывает число $2^x$ в число $2^{f(x)}$, если $f(x)$ определено, и работающая безостановочно, не переходя в заключительное внутреннее состояние $q_0$, если $f(x)$ не определено
• Для каждой частично рекурсивной функции $f(x)$ существует операторный алгоритм, перерабатывающий $2^{2^x}$ в $2^{2^{f(x)}}$, программа которого состоит лишь из приказов вида{{pb

  $\overline{\underset{\_}{|\times 2|\alpha |}},\overline{\underset{\_}{|\times 3|\alpha |}},\overline{\underset{\_}{|\times 2|\alpha |\beta |}}.$

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

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

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

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

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

См. также

• Машина Тьюринга
• Операторный алгоритм

Литература

• Шаблон:Книга