Операторный алгоритм Ван Хао задается последовательностью приказов специального вида. Каждый приказ имеет определенный номер и содержит указания : какую операцию следует выполнить над заданным объектом и приказ с каким номером следует далее выполнить над результатом данной операции. Общий вид такого приказа :
i : | w | a | b |
i — номер приказа
w — элементарная операция над объектом
a,b — номера некоторых приказов
Природа функций, вычислимых посредством операторных алгоритмов Ван-Хао, зависит от того, какие функции wi входят в записи приказов. Имеет место следующая теорема, определяющая природу функций wi.
Теорема {3). Для того чтобы частичная функция f(х) была вычислимой с помощью операторного алгоритма, программа которого содержит лишь частично рекурсивные функции wi(х) с рекурсивной областью определенности, необходимо и достаточно, чтобы f(х) была частично рекурсивной.
Построенная программа для вычисления функции f(х) оказалась довольно тривиальной вследствие того, что запас функций, допустимых в приказах, был очень большой. Естественно, чем меньше запас, тем труднее строить нужные программы. Поэтому несомненный интерес представляет следующая теорема, которую мы приводим без доказательства.,
Теорема Минского (4). Для каждой частично рекурсивной функции f(х) существует операторный алгоритм, программа которого состоит из приказов вида
| стоп |
|*c | a |
| : d | a | b |
для любого х, перерабатывающий 2 в степени х в 2 в степени f(x) .
Иными словами, любая частично рекурсивная функция f(х) вычислима при помощи подходящего алгоритма, программа которого состоит из приказов приведенного вида, при условии, что значения аргумента и функции кодируются числами 2 в степени х в 2 в степени f(x).