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