Машина Минского — многоленточная машина Тьюринга, у которой ленты слева не надстраиваются (ограничены по длине), все ячейки лент, за исключением самых левых, всегда пусты, а состояния самых левых ячеек постоянны[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 с.