Namespaces
Variants
Actions

Universal normal algorithm

From Encyclopedia of Mathematics
Revision as of 08:27, 6 June 2020 by Ulf Rehmann (talk | contribs) (tex encoded by computer)
Jump to: navigation, search


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)

Comments

References

[a1] A.A. Markov, N.M. [N.M. Nagornyi] Nagorny, "The theory of algorithms" , Kluwer (1988) pp. Chapt. V (Translated from Russian)
How to Cite This Entry:
Universal normal algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Universal_normal_algorithm&oldid=14613
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article