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

Операторный алгоритм — последовательность приказов, каждый из которых имеет определённый номер и содержит указания: какую операцию выполнить над заданным объектом и приказ с каким номером следует далее выполнять над результатом данной операции^[1]. Понятие ввёл в науку Ван Хао^[2].

Приказ

Обычно в качестве объектов используются натуральные числа и для них используются приказы вида:

${\displaystyle i:{\overline {\underline {\mid w\mid \alpha \mid \beta \mid }}}}$

где: ${\displaystyle i}$ - номер приказа, ${\displaystyle w}$ - символ фиксированной одноместной частичной функции, ${\displaystyle \alpha ,\beta }$ - номера некоторых приказов. Выполнить данный приказ над числом ${\displaystyle x}$ - значит найти число ${\displaystyle w(x)}$ и далее перейти к выполнению над ${\displaystyle w(x)}$ приказа с номером ${\displaystyle \alpha }$ ; если же ${\displaystyle w(x)}$ не определено, то перейти к выполнению над числом ${\displaystyle x}$ приказа с номером ${\displaystyle \beta }$ . Результат выполнения приказа над числом ${\displaystyle x}$ обычно изображают парой ${\displaystyle (z,\gamma )}$ , где ${\displaystyle z}$ - полученное число, ${\displaystyle \gamma }$ - номер приказа, который должен выполняться далее над ${\displaystyle z}$ .

Программа операторного алгоритма

Программой операторного алгоритма называется последовательность приказов вида:

${\displaystyle 0:{\overline {\underline {\mid Stop\mid }}},i:{\overline {\underline {\mid w_{1}\mid \alpha _{1}\mid \beta _{1}\mid }}},...s:{\overline {\underline {\mid w_{s}\mid \alpha _{s}\mid \beta _{s}\mid }}}}$

где ${\displaystyle w_{1}(x),...,w_{s}(x)}$ - заданные частичные функции, ${\displaystyle \alpha _{1},\beta _{1},...,\alpha _{s},\beta _{s}}$ - какие-то натуральные числа из последовательности ${\displaystyle 0,1,...,s}$ .

Обработка произвольного числа ${\displaystyle x}$ согласно указанной программе состоит из следующих шагов:

• Шаг 1. Вычисляем ${\displaystyle w_{1}(x)}$ . Если ${\displaystyle w_{1}(x)}$ определено, то результатом первого шага будет пара чисел ${\displaystyle (w_{1}(x),\alpha _{1})}$ . Если ${\displaystyle w_{1}(x)}$ не определено, то результатом первого шага будет пара чисел ${\displaystyle (x,\beta _{1})}$ .

....

• Шаг ${\displaystyle k}$ . Пусть пара ${\displaystyle (x_{k-1},\gamma )}$ есть результат предыдущего шага. Выполняем над ${\displaystyle x_{k-1}}$ приказ с номером ${\displaystyle \gamma }$ , то есть вычисляем ${\displaystyle w_{\gamma }(x_{k-1})}$ . Если ${\displaystyle w_{\gamma }(x_{k-1})}$ определено, то результатом ${\displaystyle k}$ -го шага будет пара чисел ${\displaystyle (w_{\gamma }(x_{k-1}),\alpha _{\gamma })}$ . Если ${\displaystyle w_{\gamma }(x_{k-1})}$ не определено, то результатом ${\displaystyle k}$ -го шага будет пара чисел ${\displaystyle (x_{k-1},\beta _{\gamma })}$ .

....

Если на ${\displaystyle n}$ -м шаге получится пара вида ${\displaystyle (a,0)}$ , то по определению на этом процесс обрывается и число ${\displaystyle a}$ называется результатом переработки числа ${\displaystyle x}$ согласно программе. Если же пара вида ${\displaystyle (a,0)}$ ни на каком шаге не возникает, то результатом переработки ${\displaystyle x}$ будет "неопределенное значение".

Свойства

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

${\displaystyle {\overline {\underline {\mid Stop\mid }}},{\overline {\underline {\mid \times c\mid \alpha _{1}\mid \mid }}},{\overline {\underline {\mid :d\mid \alpha _{1}\mid \beta _{1}\mid }}}}$

где ${\displaystyle c=2,3,5,d=2*3*5}$ , для любого ${\displaystyle x}$ перерабатывающий ${\displaystyle 2^{x}}$ в ${\displaystyle 2^{f(x)}}$ ^[1].

Обобщения

Имеются многочисленные обобщения понятия операторного алгоритма. Простейшее обобщение состоит в том, что рассматриваются приказы вида ${\displaystyle {\overline {\underline {\mid w\mid \varphi \mid \psi \mid }}}}$ . Обрабатывая заданное число ${\displaystyle x}$ , следует найти ${\displaystyle w(x)}$ . Если ${\displaystyle w(x)}$ определено, то перейти к выполнению над числом ${\displaystyle w(x)}$ приказа с номером ${\displaystyle \varphi (x)}$ , если нет, то перейти к выполнению над числом x приказа с номером ${\displaystyle \psi (x)}$ . Известно обобщение операторного алгоритма, перерабатывающее графы^[3]. При всех подобных обобщениях класс вычислимых функций совпадает с классом частично рекурсивных функций.

См. также

• Нормальный алгоритм

Примечания