Namespaces
Variants
Actions

Universal algorithm

From Encyclopedia of Mathematics
Jump to: navigation, search

for a given class of algorithms

An algorithm depending on an input parameter $p$ which for different admissible values of $p$ models the work of any algorithm of a given class. Different formalizations of computability correspond to different refinements of the notion of a universal algorithm: for recursive functions (cf. Recursive function) it is the universal partial recursive function (cf. Universal function), for Turing machines it is the universal Turing machine, for normal algorithms it is the universal normal algorithm, etc.

References

[1] V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[2] A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[3] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
How to Cite This Entry:
Universal algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Universal_algorithm&oldid=32703
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article