Operations and compositions in transrecursive operators. (English. Russian original) Zbl 0830.03017

Burgin, M. S.; Borodyanskij, Yu. M.

Russ. Acad. Sci., Dokl., Math. 49, No. 3, 572-576 (1994); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 336, No. 6, 727-729 (1994).

Earlier, the authors introduced classes of alphabetic operators that have greater computational possibilities than classical algorithms. In Dokl. Akad. Nauk SSSR 321, No. 5, 876-879 (1991), they gave a uniform procedure for obtaining such alphabetic operators, which will be called transrecursive operators in what follows. It was proved that transrecursive operators give the most general algorithmic scheme for mappings of sets of words.
In this article we give a precise definition of such a procedure and consider operations on transrecursive operators that are similar to operations obtained in the theory of algorithms [V. M. Glushkov, Kibernetika 1965, No. 5, 1-9 (1965; Zbl 0156.018)]: sequential composition, \(\alpha\)-composition, and \(\alpha\)-iteration. In the class of transrecursive operators the given operations differ essentially in a number of aspects. For example, they can have various types and forms.

MSC:

03D20	Recursive functions and relations, subrecursive hierarchies
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

algorithm theory; iteration; alphabetic operators; transrecursive operators; composition