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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

Полное описание  — ленточной машины Минского задаётся указанием совокупности всех её внутренних состояний и программы машины, состоящей из команд вида

где ; ; ; .

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

Так как есть состояние самой левой ячейки, то в командах из должно следовать неравенство .

  • Для каждой частично рекурсивной функции существует трёхленточная машина Минского, вычисляющая эту функцию, то есть переходящая из конфигурации в конфигурацию , если определено, и работающая вечно, если не определено[1].
  • Для каждой частично рекурсивной функции существует двухленточная машина Минского, которая для любого натурального перерабатывает число в число , если определено, и работающая безостановочно, не переходя в заключительное внутреннее состояние , если не определено[1]
  • Для каждой частично рекурсивной функции существует операторный алгоритм, перерабатывающий в , программа которого состоит лишь из приказов вида[1]{{pb

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

[править | править код]

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

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

  •  — занести в регистр ;
  •  — добавить к содержимому регистра и перейти к новой команде;
  •  — вычесть из содержимого регистра и перейти к следующей команде или перейти к команде если в нём уже содержится ;
  •  — перейти к команде .

Двухленточная машина Минского полностью эквивалентна регистровой машине с двумя регистрами. Если длины лент от считывающих головок до концов рассматривать как представления чисел и , операции и сдвигают головки в сторону от концов, а и к концам, при условии, что не достигнут конец ленты[5], полностью эквивалентна регистровой (программной) машине с двумя регистрами, в один из регистров которой помещается нуль, а в другой число [6].

Примечания

[править | править код]
  1. 1 2 3 4 Мальцев А. И. Алгоритмы и рекурсивные функции. — М., Наука, 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 с.