Difference between revisions of "Universal algorithm"
From Encyclopedia of Mathematics
(Importing text file) |
(TeX) |
||
| Line 1: | Line 1: | ||
| + | {{TEX|done}} | ||
''for a given class of algorithms'' | ''for a given class of algorithms'' | ||
| − | An [[Algorithm|algorithm]] depending on an input parameter | + | An [[Algorithm|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|Recursive function]]) it is the universal partial recursive function (cf. [[Universal function|Universal function]]), for Turing machines it is the universal [[Turing machine|Turing machine]], for normal algorithms it is the [[Universal normal algorithm|universal normal algorithm]], etc. |
====References==== | ====References==== | ||
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR></table> | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR></table> | ||
Latest revision as of 15:10, 3 August 2014
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=18438
Universal algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Universal_algorithm&oldid=18438
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article