The notion of a program schema has been introduced in [7] and dealt with in all the references except [6] and . A program schema is a program (written in a very simple language) which is allowed to run on arbitrary structures of a given similarity type. It describes a procedure. Roughly speaking, a procedure 5P is an operator associating with each structure 9.I in its domain a function ~(9.1) from the universe of 9~ into itself. As the output of ~9~ depends solely on the properties of the input, a procedure is preserved by isomorphisms.
One of the goals of the field of program schemata is to study their power of expression independently of any specific properties of the structures on which they are run. Consequently, no restrictive assumptions are made on the relations belonging to these structures (except, of course, for the number of arguments which is supposed to be given). In particular, we should not allow the assumption that one of the binary relations is the equality relation. Thus, our language does not contain a symbol for the equality relation. Procedures described in this way are preserved by homomorphisms rather than just isomorphisms and we call them proper procedures (the name "Herbrand procedures" is used in ). The notions of procedure and proper procedure are defined in Section 1.
It has been pointed out in various ways (see especially [5 and i0]) that there are procedures which are obviously "effectively computable" but cannot be described by program schemata. Program schemata have been augmented in various ways by allowing the use of devices such as pushdown stores or of recursive definitions, etc. Various classes of programs have been thus defined and their relative strength studied (see all the references except [6, 7 and 9]). A natural problem which arose was to find a mathematical definition which would capture the intuitive notion of "effective procedure" and then to find classes of programs which are "universal" in the sense that they are able to describe any effective procedure. One suggestion for such a