Регистровая машина - NiNa.Az

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

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

Внешний алфавит (совокупность символов, записанных на лентах) машины Минского состоит из символов ${\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}}$.

См. также

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

Примечания

1. Мальцев А. И. Алгоритмы и рекурсивные функции. — М., Наука, 1986. — с. 304—315
2. Minsky M. L. Recursive unsolvalibility of Post’s problem of Tag and topics in theory of Turing machines (англ.). — Ann. Math., 1961, 74, p. 437—455.
3. Минский, 1971, с. 244.
4. Минский, 1971, с. 304.
5. Минский, 1971, с. 209.
6. Минский, 1971, с. 311,306.

Литература

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