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

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

Система командПравить

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

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

$q_i{a}_1\dots <!--\; \dots \; -->a_s\to <!--\; \to \; -->q_{\mathrm{\alpha <!--\; \alpha \; -->}}{T}_{{\mathrm{\alpha <!--\; \alpha \; -->}}_1}\dots <!--\; \dots \; -->T_{{\mathrm{\alpha <!--\; \alpha \; -->}}_s},$$q_{i}a_{1}\dots a_{s}\to q_{\alpha }T_{\alpha _{1}}\dots T_{\alpha _{s}},$ 

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

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

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

СвойстваПравить

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

  $\stackrel{¯<!--\; ¯\; -->}{\underset{\_<!--\; \_\; -->}{|\times <!--\; \times \; -->2|\mathrm{\alpha <!--\; \alpha \; -->}|}},\stackrel{¯<!--\; ¯\; -->}{\underset{\_<!--\; \_\; -->}{|\times <!--\; \times \; -->3|\mathrm{\alpha <!--\; \alpha \; -->}|}},\stackrel{¯<!--\; ¯\; -->}{\underset{\_<!--\; \_\; -->}{|\times <!--\; \times \; -->2|\mathrm{\alpha <!--\; \alpha \; -->}|\mathrm{\beta <!--\; \beta \; -->}|}}.$${\overline {\underline {|\,{\times 2}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 3}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 2}\,|\,\alpha \,|\,\beta \,|}}}.$ 

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

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

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

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

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

См. такжеПравить

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

ЛитератураПравить

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