View source for Universal normal algorithm

<!--
u0956901.png
$#A+1 = 18 n = 0
$#C+1 = 18 : ~/encyclopedia/old_files/data/U095/U.0905690 Universal normal algorithm
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A [[Normal algorithm|normal algorithm]]  $  \mathfrak B $
which in a sense (made precise below) models the work of any normal algorithm over the alphabet  $  A = \{ a _ {1} \dots a _ {n} \} $. 
A normal algorithm  $  \mathfrak B $
over the alphabet  $  B \supset A \cup \{ \alpha , \beta , \gamma , \delta \} $(
where  $  A $
does not contain  $  \alpha , \beta , \gamma , \delta $) 
is called universal for  $  A $
if for every normal algorithm  $  \mathfrak A $
over  $  A $
and any word  $  P $
over  $  A $,

$$ 
\mathfrak B ( \mathfrak A  ^ {I} \delta P)  \simeq  \mathfrak A ( P).
$$

Here  $  \mathfrak A  ^ {I} $
is a representation of the normal algorithm (cf. [[Algorithm, representation of an|Algorithm, representation of an]]), and the symbol  $  \delta $
in  $  B $
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  $  n $(
the number of symbols in the alphabet  $  A $) 
has been obtained, differing only by an additive constant from lower and upper bounds of the form  $  5n + C $(
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>