View source for Algorithm, representation of an

''coding of an algorithm''

A [[Constructive object|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118301.png" /> of a [[Normal algorithm|normal algorithm]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118302.png" /> over an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118303.png" /> (not containing the letters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118304.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118305.png" />) is defined as a word over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118306.png" /> which is obtained as follows [[#References|[1]]]. In each substitution formula of the scheme of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118307.png" /> the arrow is replaced by the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118308.png" />, the point (if any) by the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118309.png" />, and the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183010.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183011.png" />. In actual fact, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183012.png" /> is merely a scheme of the normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183013.png" />, 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 [[#References|[1]]], which is the result of translating the words of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183014.png" /> into some two-letter alphabet (usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183015.png" />). The coding of the program of a [[Turing machine|Turing machine]] can be carried out in a similar manner. The role of the coding of a [[Recursive function|recursive function]] is played by the Gödel number of the system of equations which define this function [[#References|[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|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, computational complexity of an]]; [[Algorithm, complexity of description of an|Algorithm, complexity of description of an]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Markov,   "Theory of algorithms" , Israel Program Sci. Transl.  (1961)  (Translated from Russian)  (Also: Trudy Mat. Inst. Steklov. 42 (1954))</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  S.C. Kleene,   "Introduction to metamathematics" , North-Holland &amp; Noordhoff  (1951)</TD></TR></table>