MATHEMATICS

D. SKORDEV

SOME SIMPLE EXAMPLES OF UNIVERSAL FUNCTIONS

(Presented by Academician P. S. Novikov, 7 VII 1969)

For any positive natural number \(m\), consider the polynomial

\[ v_m(x,y)=\frac{1}{2}m(x+y)(x+y+1)+x-(m-1)y. \]

By direct computation one verifies the equalities

\[ \begin{aligned} v_m(0,0)&=0,\\ v_m(0,x+1)&=v_m(x,0)+1,\\ v_m(x+1,y)&=v_m(x,y+1)+m. \end{aligned} \]

With the help of these equalities it is easy to see that at points with natural-number coordinates the polynomial \(v_m\) takes natural values, and at distinct points—distinct ones.

Theorem 1. Let \(m\) be a positive natural number and let \(\omega\) be a (partial) arithmetical function of two variables such that, for any natural \(x,y,z\), the equalities

\[ \omega(v_m(y,0),z)\simeq v_m(y,z), \tag{1} \]

\[ \omega(v_m(0,x+1),z)\simeq x, \tag{2} \]

\[ \omega(v_m(y+1,x+1),z)\simeq \omega(\omega(x,z),\omega(y,z)). \tag{3} \]

hold.

Under these assumptions \(\omega\) is a recursively complete arithmetical operation in the sense of \((^3)\), i.e., there exist natural numbers \(P,Q,R\), and \(S\) such that the following 4 conditions are satisfied for any natural \(x,y,z\):

a) \(\omega(P,x)\simeq x+1\);

b) \(\omega(Q,x+1)\simeq x\);

c)

\[ \omega(\omega(\omega(R,x),y),z)\simeq \begin{cases} y, & \text{if } x=0,\\ z, & \text{if } x\ne 0; \end{cases} \]

d) \(\omega(\omega(S,x),y)\) is defined and

\[ \omega(\omega(\omega(S,x),y),z)\simeq \omega(\omega(x,z),\omega(y,z)). \]

On the basis of the results proved in \((^3)\), it follows from this that

Theorem 2. Under the assumptions of Theorem 1 one may assert:

a) if \(\varphi\) is a one-place arithmetical function that is \(\mu\)-recursive relative to \(\omega\), then there exists a natural number \(p\) such that for every natural \(z\) the equality

\[ \varphi(z)\simeq \omega(p,z); \]

holds;

b) if \(n\) is a positive natural number and \(\varphi\) is an \((n+1)\)-place arithmetical function that is \(\mu\)-recursive relative to \(\omega\), then there exists a natural number \(p\) such that, for any natural \(z_1,z_2,\ldots,z_n,z_{n+1}\), the equality

\[ \varphi(z_1,z_2,\ldots,z_n,z_{n+1}) \simeq \omega(\omega(\ldots\omega(\omega(p,z_1),z_2),\ldots,z_n),z_{n+1}), \]

moreover the expression \(\omega(\ldots \omega(\omega(p,z_1),z_2),\ldots,z_n)\) is meaningful for any natural \(z_1,z_2,\ldots,z_n\).

Corollary. Under the hypotheses of Theorem 1 and under the additional assumption that the function \(\omega\) is partially recursive, one may assert that \(\omega\) is a principal universal function (in the sense of (4)) for partially recursive functions of one argument.

Using the recursion theorem, for every positive natural \(m\) one can construct a corresponding partially recursive function \(\omega\) for which equations (1), (2), and (3) are identically satisfied. Each such function will be a principal universal function for partially recursive functions of one argument.

Let \(\omega_0\) be that function which is obtained from the recursion theorem for \(m=1\), i.e., that one of the functions \(\omega\) satisfying equations (1), (2), and (3) for \(m=1\) which has the smallest domain of definition. According to what has been said, \(\omega_0\) will be a principal universal function for one-place partially recursive functions. Denote by (e) the following system of equalities of the formalism of recursive functions ((\(^{1}\), § 54):

\[ \begin{aligned} h(0,0,0,d)&=d,\\ h(a',0,c',d)&=h(a,c,0,d),\\ h(a',b',c,d)&=h(a,b,c',d),\\ f(a,b)&=h(a,c,0,h(d,c,b,d)),\\ f(a,b)&=h(a,0,c',c),\\ f(a,b)&=h(a,d',c',f(f(c,b),f(d,b))). \end{aligned} \tag{e} \]

Theorem 3. The system (e) recursively defines the function \(\omega_0\).

Corollary. If \(\varphi\) is an arbitrary partially recursive function, then a system of 7 equalities of the formalism of recursive functions can be constructed which recursively defines \(\varphi\).

One can construct a relatively simple normal algorithm which, in a certain sense, computes the function \(\omega_0\). We have constructed a normal algorithm \(\mathfrak A\) in the alphabet \(|f0abc\), possessing the following properties (for the terminology see (\(^{2}\))):

1) For any natural \(v\) and \(z\) the equality holds

\[ \mathfrak A\bigl[\,|^{v+1}0|^{z+1}\,\bigr]\simeq |^{\omega_0(v,z)+1}. \]

2) The scheme of the algorithm \(\mathfrak A\) consists of 18 substitution formulas.

3) All formulas in the scheme of the algorithm \(\mathfrak A\) are simple.

4) The length of the representation of the algorithm \(\mathfrak A\) is equal to the number 128.

From the existence of the normal algorithm \(\mathfrak A\) with properties 1), 2), and 3) it follows that, for any one-place partially recursive function \(\varphi\), one can construct a normal algorithm \(\mathfrak B\) over the alphabet \(|\), possessing the following properties:

A. For any natural \(z\) the equality is true

\[ \mathfrak B\bigl[\,|^{z}\,\bigr]\simeq |^{\varphi(z)}. \]

B. The scheme of the algorithm \(\mathfrak B\) consists of 20 substitution formulas.

By applying Theorem 2 for \(m=2\), one can obtain certain results concerning relative partial recursiveness. We formulate here one of them:

Theorem 4. If \(\varphi\) and \(\psi\) are partial arithmetical functions and \(\varphi\) is partially recursive relative to \(\psi\), then one can construct a system of 8 equalities of the formalism of recursive functions, recursively defining \(\varphi\) through \(\psi\).

Sofia University
Sofia, Bulgaria

Received
15 V 1969

CITED LITERATURE

\(^{1}\) S. K. Kleene, Introduction to Metamathematics, Moscow, 1957.
\(^{2}\) A. A. Markov, Theory of Algorithms, Moscow, 1954.
\(^{3}\) D. Skordev, Dokl. Bolgarsk. AN, 16, No. 5, 465 (1963).
\(^{4}\) V. A. Uspenskii, Lectures on Computable Functions, Moscow, 1960.