Universal normal algorithm

A 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), 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. [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). 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. [2]).

References

[1]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2]	V.G. Zharov, "The complexity of a universal normal algorithm" , Theory of algorithms and mathematical logic , Moscow (1974) pp. 34–54 (In Russian)

References

[a1]	A.A. Markov, N.M. [N.M. Nagornyi] Nagorny, "The theory of algorithms" , Kluwer (1988) pp. Chapt. V (Translated from Russian)