Машина Минского
Машина Минского — многоленточная машина Тьюринга, у которой ленты слева не надстраиваются (ограничены по длине), все ячейки лент, за исключением самых левых, всегда пусты, а состояния самых левых ячеек постоянны[1]. Также называется регистровая машина. Понятие ввёл в науку М. Минский[2]
Система команд
Внешний алфавит (совокупность символов, записанных на лентах) машины Минского состоит из символов [math]\displaystyle{ 0, 1 }[/math]. Символ пустого состояния [math]\displaystyle{ 0 }[/math], все самые левые клетки всех лент находятся в состоянии [math]\displaystyle{ 1 }[/math].
Полное описание [math]\displaystyle{ n }[/math] — ленточной машины Минского задаётся указанием совокупности всех её внутренних состояний [math]\displaystyle{ q_i,\ i = 1, \dots, n }[/math] и программы машины, состоящей из команд вида
- [math]\displaystyle{ q_i a_1 \dots a_s \to q_\alpha T_{\alpha_1} \dots T_{\alpha_s}, }[/math]
где [math]\displaystyle{ i = 1, \dots, n }[/math]; [math]\displaystyle{ a_\lambda = 0, 1 }[/math]; [math]\displaystyle{ \alpha = 0, 1, \dots, n }[/math]; [math]\displaystyle{ \alpha_\lambda = 0, 1, -1 }[/math].
Эти команды означают, что, находясь во внутреннем состоянии [math]\displaystyle{ q_i }[/math] и воспринимая ячейки лент в состояниях [math]\displaystyle{ a_1 \dots a_s }[/math], машина заменяет [math]\displaystyle{ q_i }[/math] на [math]\displaystyle{ q_\alpha }[/math], после чего сдвигает ленты в направлениях [math]\displaystyle{ T_{\alpha_1} \dots T_{\alpha_s} }[/math] ([math]\displaystyle{ T_{-1}, T_1, T_0 }[/math] означают соответственно сдвиг ленты на одну ячейку влево, вправо и оставление ленты неподвижной).
Так как [math]\displaystyle{ 1 }[/math] есть состояние самой левой ячейки, то в командах из [math]\displaystyle{ a_\lambda = 1 }[/math] должно следовать неравенство [math]\displaystyle{ \alpha_\lambda \neq -1 }[/math].
Свойства
- Для каждой частично рекурсивной функции [math]\displaystyle{ f(x) }[/math] существует трёхленточная машина Минского, вычисляющая эту функцию, то есть переходящая из конфигурации [math]\displaystyle{ {10}^{x-1} q_1 0 q_1 1 q_1 1 }[/math] в конфигурацию [math]\displaystyle{ {10}^{f(x)-1} q_0 0 q_0 1 q_0 1 }[/math], если [math]\displaystyle{ f(x) }[/math] определено, и работающая вечно, если [math]\displaystyle{ f(x) }[/math] не определено[1].
- Для каждой частично рекурсивной функции [math]\displaystyle{ f(x) }[/math] существует двухленточная машина Минского, которая для любого натурального [math]\displaystyle{ x }[/math] перерабатывает число [math]\displaystyle{ 2^x }[/math] в число [math]\displaystyle{ 2^{f(x)} }[/math], если [math]\displaystyle{ f(x) }[/math] определено, и работающая безостановочно, не переходя в заключительное внутреннее состояние [math]\displaystyle{ q_0 }[/math], если [math]\displaystyle{ f(x) }[/math] не определено[1]
- Для каждой частично рекурсивной функции [math]\displaystyle{ f(x) }[/math] существует операторный алгоритм, перерабатывающий [math]\displaystyle{ 2^{2^x} }[/math] в [math]\displaystyle{ 2^{2^{f(x)}} }[/math], программа которого состоит лишь из приказов вида[1]{{pb
- [math]\displaystyle{ \overline{\underline{|\, {\times 2} \,|\, \alpha \,|}}, \overline{\underline{|\, {\times 3} \,|\, \alpha \,|}}, \overline{\underline{|\, {\times 2} \,|\, \alpha \,|\, \beta \,|}}. }[/math]
Регистровая машина
Регистровая (или программная) машина состоит из конечного числа регистров, хранящих неотрицательные целые числа и управляющий программный блок, который выполняет операции над содержимым регистров согласно программе (упорядоченной последовательности команд). Команды содержат сведения о выполняемой операции, регистре, номерах одной или двух других команд[3].
Для всякой машины Тьюринга всегда можно построить эквивалентную ей регистровую машину, использующую два регистра и выполняющую четыре операции[4]:
- [math]\displaystyle{ \underline{\overline{|\, a^0 \,|}} }[/math] — занести [math]\displaystyle{ 0 }[/math] в регистр [math]\displaystyle{ a }[/math];
- [math]\displaystyle{ \underline{\overline{|\, a' \,|}} }[/math] — добавить [math]\displaystyle{ 1 }[/math] к содержимому регистра [math]\displaystyle{ a }[/math] и перейти к новой команде;
- [math]\displaystyle{ \underline{\overline{|\, a^{-}(n) \,|}} }[/math] — вычесть [math]\displaystyle{ 1 }[/math] из содержимого регистра [math]\displaystyle{ a }[/math] и перейти к следующей команде или перейти к команде [math]\displaystyle{ n, }[/math] если в нём уже содержится [math]\displaystyle{ 0 }[/math];
- [math]\displaystyle{ \underline{\overline{|\, n \,|}} }[/math] — перейти к команде [math]\displaystyle{ n }[/math].
Двухленточная машина Минского полностью эквивалентна регистровой машине с двумя регистрами. Если длины лент от считывающих головок до концов рассматривать как представления чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math], операции [math]\displaystyle{ m^+ }[/math] и [math]\displaystyle{ n^+ }[/math] сдвигают головки в сторону от концов, а [math]\displaystyle{ m^- }[/math] и [math]\displaystyle{ n^- }[/math] к концам, при условии, что не достигнут конец ленты[5], полностью эквивалентна регистровой (программной) машине с двумя регистрами, в один из регистров которой помещается нуль, а в другой число [math]\displaystyle{ 2^a 3^m 5^n }[/math][6].
См. также
Примечания
- ↑ 1,0 1,1 1,2 1,3 Мальцев А. И. Алгоритмы и рекурсивные функции. — М., Наука, 1986. — с. 304—315
- ↑ 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.
- ↑ Минский, 1971, с. 244.
- ↑ Минский, 1971, с. 304.
- ↑ Минский, 1971, с. 209.
- ↑ Минский, 1971, с. 311,306.
Литература
- Минский М. Вычисления и автоматы. — М.: Мир, 1971. — 360 с.