Algorithm, representation of an

coding of an algorithm

A constructive object of a certain kind (as a rule, a natural number or a word) containing complete information about the algorithm, coded in accordance with the rules laid down for this type of algorithm. A coding of an algorithm is usually so defined that the procedures for obtaining the coding of the original algorithm and obtaining the original algorithm from its coding are as simple as possible.

The coding $ \mathfrak A ^ {I} $ of a normal algorithm $ \mathfrak A $ over an alphabet $ A $( not containing the letters $ \alpha , \beta $ and $ \gamma $) is defined as a word over the alphabet $ A \alpha \beta \gamma $ which is obtained as follows [1]. In each substitution formula of the scheme of $ \mathfrak A $ the arrow is replaced by the letter $ \alpha $, the point (if any) by the letter $ \beta $, and the letter $ \gamma $ is written at the end of the word thus formed. The resulting words are then written out, one after the other, in the same sequence as that of their respective substitution formulas in the scheme of $ \mathfrak A $. In actual fact, $ \mathfrak A ^ {I} $ is merely a scheme of the normal algorithm $ \mathfrak A $, written in a somewhat different form — viz. as a word. For reasons connected with the technical details of the definition of a normal algorithm, another type of coding of a normal algorithm is somewhat more convenient — the so-called record of a normal algorithm [1], which is the result of translating the words of $ \mathfrak A ^ {I} $ into some two-letter alphabet (usually $ \{ 0, 1 \} $). The coding of the program of a Turing machine can be carried out in a similar manner. The role of the coding of a recursive function is played by the Gödel number of the system of equations which define this function [2].

In any formalization of the general concept of an algorithm, its coding is so defined that it (in fact, the algorithm coded by it) might be included in the inputs for the algorithms of this type. This makes it possible to demonstrate the so-called "theorems on universal algorithms" , dealing with the realizability of algorithms whose codings model the operation of any algorithm of this type.

If a coding of an algorithm is a permissible input for the algorithm, this algorithm is called self-applicable if it is applicable to its own coding, and not self-applicable otherwise. It is possible to show, with the aid of a variant of the Russell paradox (cf. Antinomy), which is applicable to this situation, that the algorithmic problem which then arises — to wit, how to recognize self-applicable algorithms among other algorithms of this type — is not solvable by an algorithm of this type. This result forms the base of numerous theorems on the unsolvability of algorithmic problems.

The length of the code of an (encoding of an) algorithm is a natural measure of the complexity of an algorithm (the amount of memory which is required to remember the program of the algorithm) (cf. Algorithm, computational complexity of an; Algorithm, complexity of description of an).

References

[1]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2]	S.C. Kleene, "Introduction to metamathematics" , North-Holland & Noordhoff (1951)