View source for Universal normal algorithm

A [[Normal algorithm|normal algorithm]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956901.png" /> which in a sense (made precise below) models the work of any normal algorithm over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956902.png" />. A normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956903.png" /> over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956904.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956905.png" /> does not contain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956906.png" />) is called universal for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956907.png" /> if for every normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956908.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u0956909.png" /> and any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569010.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569011.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569012.png" /></td> </tr></table>

Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569013.png" /> is a representation of the normal algorithm (cf. [[Algorithm, representation of an|Algorithm, representation of an]]), and the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569014.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569015.png" /> plays the role of dividing sign. The existence of a universal normal algorithm was proved by A.A. Markov (cf. [[#References|[1]]]). An important characteristic of a universal normal algorithm is its complexity, i.e. the length of its representation (cf. also [[Algorithm, complexity of description of an|Algorithm, complexity of description of an]]). A universal normal algorithm of minimal complexity as a function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569016.png" /> (the number of symbols in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569017.png" />) has been obtained, differing only by an additive constant from lower and upper bounds of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095690/u09569018.png" /> (cf. [[#References|[2]]]).

====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">  V.G. Zharov,   "The complexity of a universal normal algorithm" , ''Theory of algorithms and mathematical logic'' , Moscow  (1974)  pp. 34–54  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.A. Markov,   N.M. [N.M. Nagornyi] Nagorny,   "The theory of algorithms" , Kluwer  (1988)  pp. Chapt. V  (Translated from Russian)</TD></TR></table>