2008 | OriginalPaper | Buchkapitel
Elementary Algorithms and Their Implementations
verfasst von : Yiannis N. Moschovakis, Vasilis Paschalis
Erschienen in: New Computational Paradigms
Verlag: Springer New York
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the sequence of articles [3, 4, 5, 6, 7], Moschovakis has proposed a mathematical modeling of the notion of
algorithm
—a set-theoretic “definition” of algorithms, much like the “definition” of real numbers as Dedekind cuts on the rationals or that of random variables as measurable functions on a probability space. The aim is to provide a traditional foundation for the theory of algorithms, a development of it within axiomatic set theory in the same way as analysis and probability theory are rigorously developed within set theory on the basis of the set theoretic modeling of their basic notions. A characteristic feature of this approach is the adoption of a very abstract notion of algorithm that takes
recursion
as a primitive operation and is so wide as to admit “non-implementable” algorithms:
implementations
are special, restricted algorithms (which include the familiar
models of computation
, e.g., Turing and random access machines), and an algorithm is implementable if it is
reducible
to an implementation.