WikiSort.ru - Не сортированное

Эта страница требует существенной переработки. Возможно, её необходимо викифицировать, дополнить или переписать. Пояснение причин и обсуждение — на странице Википедия:К улучшению/20 февраля 2019.

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

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

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

Полное описание ${\displaystyle n}$ - ленточной машины Минского задаётся указанием совокупности всех её внутренних состояний ${\displaystyle q_{i},i=1,...n}$ и программы машины, состоящей из команд вида:

${\displaystyle q_{i}a_{1}...a_{s}\rightarrow q_{\alpha }T_{\alpha _{1}}...T_{\alpha _{s}}}$

где: ${\displaystyle i=1,...n;a_{\lambda }=0,1;\alpha =0,1,...,n;\alpha _{\lambda }=0,1,-1}$ ,

Эти команды означают, что, находясь во внутреннем состоянии ${\displaystyle q_{i}}$ и воспринимая ячейки лент в состояниях ${\displaystyle a_{1}...a_{s}}$ , машина заменяет ${\displaystyle q_{i}}$ на ${\displaystyle q_{\alpha }}$ , после чего сдвигает ленты в направлениях ${\displaystyle T_{\alpha _{1}}...T_{\alpha _{s}}}$ (${\displaystyle T_{-1},T_{1},T_{0}}$ означают, соответственно, сдвиг ленты на одну ячейку влево, вправо и оставление ленты неподвижной).

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

Свойства

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

${\displaystyle {\overline {\underline {\mid \times 2\mid \alpha \mid }}},{\overline {\underline {\mid \times 3\mid \alpha \mid }}},{\overline {\underline {\mid \times 2\mid \alpha \mid \beta \mid }}}}$

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

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

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

• ${\displaystyle {\underline {\overline {\mid a^{0}\mid }}}}$ занести ${\displaystyle 0}$ в регистр ${\displaystyle a}$ ;
• ${\displaystyle {\underline {\overline {\mid a'\mid }}}}$ добавить ${\displaystyle 1}$ к содержимому регистра a и перейти к новой команде;
• ${\displaystyle {\underline {\overline {\mid a^{-}(n)\mid }}}}$ вычесть ${\displaystyle 1}$ из содержимого регистра и перейти к следующей команде или перейти к команде ${\displaystyle n,}$ если в нем уже содержится ${\displaystyle 0}$ ;
• ${\displaystyle {\underline {\overline {\mid n\mid }}}}$ перейти к команде ${\displaystyle n}$ .

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

См. также

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

Примечания

Литература

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