1.5.Операторные алгоритмические системы

1.5.1Общие положения

Одной из особенностей общей теории алгоритмов является неизменность набора допустимых средств, используемых для построения записи алгоритма при его выполнении.

Например, все частично рекурсивные функции получаются из некоторого фиксированного набора базисных функций с помощью трех операторов: подстановки, примитивной рекурсии, оператора наименьшего корня.

Элементарные акты при вычислении на МТ ограничиваются фиксированным набором операций, которые выполняет описываемый класс машин и т.п.

В то же время при изучении конкретных алгоритмов желательно, чтобы каждый алгоритм мог изучаться в терминах тех элементарных средств, которые наиболее удобны для его описания.

Например, алгоритмы линейной алгебры удобно описывать с помощью четырех арифметических действий, а алгоритмы вычисления функций алгебры логики – с помощью тех базисных логических операций, в терминах которых эти функции записаны.

Поэтому одним из требований, которое предъявляется к определению алгоритма при его практическом использовании, является то, чтобы как вид перерабатываемой информации, так и средства ее переработки выбирались в зависимости от класса рассматриваемых алгоритмов.

В каждой классической алгоритмической системе тем или иным способом вводится понятие выполнения алгоритма, то есть осуществления последовательности действий, производящих переход от исходных данных к конечному результату.

При этом характерно, что в каждом алгоритме список предписаний о выполнении элементарных актов – “команд” алгоритма фиксируется заранее и явно указывается в записи алгоритма. Например, в записи НА Маркова все применяемые формулы подстановки заранее указаны в записи алгоритма, список допустимых действий МТ при ее работе остается неизменным, ч.р.ф. задается фиксированной последовательностью уравнений.

В то же время допущение формирования команд алгоритма в процессе его реализации приводит к существенному сокращению и упрощению записи алгоритма. В связи с этим, следующим требованием, предъявляемым к понятию алгоритма, является допущение формирования команд алгоритма в процессе его выполнения.

Рассмотрение реальных алгоритмов показывает, что все элементарные операции распадаются на две группы: арифметические и логические.

Арифметические операции осуществляют непосредственное преобразование информации, а логические определяют последовательность выполнения арифметических операций.

Как правило, логические операции в классических алгоритмических системах носят тривиальный характер. Во многих случаях такая тривиальность сильно усложняет построение конкретных алгоритмов. Поэтому следующим требованием к описанию алгоритма является допущение более универсальных логических элементарных операций, которые имеются в абстрактной теории алгоритмов.

В той или иной мере этим требованиям отвечают так называемые операторные алгоритмические системы.

1.5.2. Операторные алгоритмы Ван-Хао

Операторный алгоритм Ван-Хао задается последовательностью команд специального вида: каждая команда имеет определенный номер и содержит указания какую операцию следует выполнить над заданным объектом и команду с каким номером следует далее выполнять над результатлм данной операции.

Общий вид:

I:

W

a

b

I – номер команды

W- элементарная операция над объектом

a,b - номера некоторых команд.

Выполнить команду I над числом Х в операторном алгоритме – значит найти число W(X) и далее перейти к выполнению над W(X) команды с номером a. Если же W(X) не определено, то перейти к выполнению над числом Х команды с номером b.

Кроме обычных команд существует заключительная команда вида:

I:

стоп

Если в процессе выполнения алгоритма не возникает указания на заключительный оператор, то результатом переработки Х будет “неопределенное значение”.

Если функция W всюду определена, то символ b не оказывает влияния на процесс вычислений и поэтому команда имеет вид:

I:

W

a

Говорят, что операторный алгоритм А с программой (Х) вычисляет частичную функцию f(x), если алгоритм А перерабатывает каждое натуральное число Х в f(x) .

В частности, если f(x) неопределена, то процесс переработки Х должен быть бесконечным. Природа функций, вычислимых посредством операторных алгоритмов Ван-Хао зависит от того, какие функции Wi входят в записи команд. Имеет место следующая теорема:

Для того, чтобы частичная функция f(x) была вычислимой с помощью алгоритма, программа которого содержит лишь ч.р.ф. Wi(x) с рекурсивной областью определенности, необходимо и достаточно, чтобы f(x) была частично рекурсивной.

Предлагаю ознакомиться с аналогичными статьями: