UDC 51.01:518.5

MATHEMATICS

N. P. TER-ZAKHARYAN

ON SOME QUANTITATIVE CHARACTERISTICS OF ALGORITHMIC LANGUAGES

(Presented by Academician P. S. Novikov, 5 VI 1969)

This note considers characteristics of algorithmic languages connected with how briefly it is possible to encode various algorithms in these languages. In connection with this, a certain classification of algorithmic languages is introduced, and the place of some concrete languages in this classification is investigated.

We shall use the terminology and concepts introduced in the work \((^1)\). Everywhere below, n.a. is an abbreviation for the expression normal algorithm.

1. By a natural number we shall mean an arbitrary word in the alphabet \(\{0, |\}\). Here, in the role of the successor operation, there will figure an n.a. \(f\) over \(\{0, |\}\) such that for any word \(P\) in \(\{0, |\}\) one has

\[ f(\Lambda) \simeq 0, \qquad f(P0) \simeq P|, \qquad f(P|) \simeq f(P)0. \]

Let \(A_j\) and \(A_i\) be alphabets; \(\square \notin A_i \cup A_j\); \(\Omega\) a recursive set of words in \(A_i\); \(U\) an n.a. over \(A_i \cup A_j\) such that, for every word \(P\) in \(A_j\) and word \(X\) from \(\Omega\), if \(!U(X \square P)\), then \(U(X \square P)\) is a word in \(A_j\). A list

\[ \mathcal{Y} \leftrightharpoons \langle A_j, A_i, \Omega, U\rangle, \tag{1} \]

satisfying the conditions stated above, will be called an algorithmic language, and every word from \(\Omega\) a message of this language.

Let \(\mathcal{Y}_1 \leftrightharpoons \langle A_{j_1}, A_{i_1}, \Omega_1, U_1\rangle\) and \(\mathcal{Y}_2 \leftrightharpoons \langle A_{j_2}, A_{i_2}, \Omega_2, U_2\rangle\) be two languages, and let an n.a. \(\theta\) over \(A_{j_1} \cup A_{j_2}\) be a fixed one-to-one mapping of the set of words in \(A_{j_1}\) onto the set of words in \(A_{j_2}\). We shall call an n.a. \(T\) over \(A_{i_1} \cup A_{i_2} \cup \square\) a translator from \(\mathcal{Y}_1\) to \(\mathcal{Y}_2\) if it is applicable to every message \(X\) of the language \(\mathcal{Y}_1\), with \(T(X) \in \Omega_2\), and for every word \(P\) in \(A_{j_1}\)

\[ \theta(U_1(X \square P)) \simeq U_2(T(X) \square \theta(P)). \]

We shall say that \(\mathcal{Y}_1\) is reducible to \(\mathcal{Y}_2\) if there exists a translator \(T\) from \(\mathcal{Y}_1\) to \(\mathcal{Y}_2\).

Renumber all messages of the language \(\mathcal{Y}\) in the order of increasing lengths. Let an n.a. \(\mathfrak{C}\) over \(A_{i_1} \cup \{0, |\}\) transform each message of the language \(\mathcal{Y}_1\) into its number. An n.a. \(L_1\) over \(A_{i_1} \cup \{0, |\}\) will be called a complexity criterion of the language \(\mathcal{Y}_1\) if, for every message \(X\) of the language \(\mathcal{Y}_1\), one has

\[ !L_1(X) \ \&\ L_1(X) \simeq [\mathfrak{C}(X)]^0, \]

and \(L_1(X)\) will be called the complexity of the message \(X\).

Let \(L_1\) (respectively, \(L_2\)) be a complexity criterion of the language \(\mathcal{Y}_1\) (respectively, \(\mathcal{Y}_2\)), and let an n.a. \(T\) be a translator from \(\mathcal{Y}_1\) to \(\mathcal{Y}_2\). We shall say that \(T\) is an additively bounded (respectively, multiplicatively bounded) translator if there exist constants \(c\) and \(d\) such that, for every message \(X\) of the language \(\mathcal{Y}_1\), the inequality

\[ L_2(T(X)) \leq L_1(X) + c \]

holds (respectively,

\[ L_2(T(X)) \leq cL_1(X) + d \]

).

We shall say that \(T\) is an asymptotically bounded translator if for every natural \(n\) one can construct an \(m_0\) such that, whatever the natural number \(m\) and the message \(X\) of the language \(\mathcal{Y}_1\) may be, the following holds:

\[ m > m_0 \& L_1(X) \leq m \supset L_2(T(X)) \leq (1+2^{-n})m. \]

We shall say that an algorithmic language \(\mathcal{Y}\) is universal if every other language is reducible to it.

A universal language \(\mathcal{Y}\) will be called additively optimal (respectively, asymptotically optimal, multiplicatively optimal) if for every language \(\mathcal{Y}_1\) one can construct an additively bounded (respectively, asymptotically bounded, multiplicatively bounded) translator from \(\mathcal{Y}_1\) into \(\mathcal{Y}\).

It is obvious that every additively optimal language is asymptotically optimal, and every asymptotically optimal language is multiplicatively optimal. It is also easy to prove that additively optimal languages exist, and that there exist universal languages which are not multiplicatively optimal.

1. Language of normal algorithms (LNA). Let \(A_p\) be some alphabet; \(\alpha,\beta,\gamma,a,b\) distinct letters not contained in \(A_p\); \(\Xi\) the set of descriptions of n.a. in the alphabet \(A_p \cup \{a,b\}\) (see (1)); \(V\) a universal n.a. over the alphabet \(A_p \cup \{\alpha,\beta,\gamma,a,b,\square\}\) for n.a. in \(A_p \cup \{a,b\}\). The list

\[ \langle A_p, A_p \cup \{\alpha,\beta,\gamma,a,b\}, \Xi, V\rangle, \]

whose elements satisfy the conditions described above, is a language. We shall call it LNA.

Theorem 1. Every LNA is asymptotically optimal.

1. Messages \(X\) and \(Y\) of the language (1) will be called equivalent if, for every word \(P\) in \(A_j\), the following holds:

\[ U(X \square P) \simeq U(Y \square P). \]

It is obvious that for every natural \(m\) there quasi-exists a sequence of pairwise nonequivalent messages of the language (1)

\[ X_1, X_2,\ldots,X_h \tag{2} \]

of complexity \(\leq m\) such that, for every message \(X\) of complexity not exceeding \(m\), there quasi-exists an \(i\) such that \(1 \leq i \leq h\) and \(X_i\) is equivalent to \(X\). The sequence (2) will be called the \(m\)-th section of the language.

We shall say that a rational number \(e\) is an entropic upper estimate of an algorithmic language if there is a natural number \(m_0\) such that, for every \(m\)-th section (2) of the language (1), where \(m > m_0\), the following holds:

\[ [h^\partial/(m+1)] < e. \]

Theorem 2. If a rational number \(e\) is an entropic upper estimate of an LNA, then \(e \geq 1\).

Corollary. If a rational number \(e\) is an entropic upper estimate of some asymptotically optimal language, then \(e \geq 1\).

1. Language of recursive functions (LRF). Let us describe a certain set \(\Sigma\) of words in the alphabet \(R \leftrightarrows \{Q,S,\tau,\sigma,\eta,\mu\}\) as follows:

1) \(Q \in \Sigma\).
2) \(S \in \Sigma\).
3) If \(A \in \Sigma,\ B \in \Sigma\), then: a) \(\sigma AB \in \Sigma\), b) \(\tau AB \in \Sigma\), c) \(\eta A \in \Sigma\), d) \(\mu A \in \Sigma\).

Let the normal algorithm \(W\) over the alphabet \(R \cup \{0, |, \square\}\) satisfy the following conditions:

1) \(W(S \square n) \simeq n + 1\).

2) \(W(Q \square n) \simeq n \div [\sqrt n]^2\).

3) \(W(\tau AB \square n) \simeq W(A \square W(B \square n))\).

4) \(W(\sigma AB \square n) \simeq W(A \square n) + W(B \square n)\).

5)
\[ W(\eta A \square n) \simeq \begin{cases} 0, & \text{if } n = 0,\\ W(A \square W(\eta A \square n \div 1)), & \text{if } n \ne 0. \end{cases} \]

6) \(W(\mu A \square n) \simeq \mu m\bigl(W(A \square c(n,m)) \simeq 0\bigr)\).

Here \(c(n,m)\) is the Cantor number of the pair of natural numbers \(n\) and \(m\) (see, for example, (²)). The list

\[ \langle \{0, |\}, R, \Sigma, W\rangle, \]

whose elements satisfy the conditions written above, is a language. We shall call it YaRF.

Theorem 3. There exists a rational number \(e < 1\) that is an entropic upper estimate for YaRF.

Corollary. YaRF is not asymptotically optimal.

Theorem 4. YaRF is multiplicatively optimal.

In conclusion, I consider it my pleasant duty to express deep gratitude to A. A. Markov and I. D. Zaslavsky for posing the problem and for their constant attention to the work.

CITED LITERATURE

¹ A. A. Markov, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 42 (1954).

² A. I. Mal’tsev, Algorithms and Recursive Functions, Moscow, 1965.