Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Theories of Computational Complexity (Annals of Discrete Mathematics, Volume 35)
Автор: Calude C.
During the 1890’s, when PEANO’s five axioms were set afloat, a great effort was done to establish what functions are or are not what we
call today algorithmically computable functions. DEDEKIND and PEANO
have been the fvst to use functions defined by induction, an important
preliminary stage of the recursive function theory. The foundational prob-
lems arising from CANTOR’S development of the set theory have led to an
increasing interest in the two millenia old intuitive notion of algorithm.
Some forms close to the modern use of algorithms can be found in the
works written in the fvst quarter of the 20th century by BOREL and
WEYL. Around 1930’s, GODEL, CHURCH, KLEENE and TURING have
provided different, but equivalent, formalisms for characterizing the
number-theoretic functions computable by algorithms, i.e . the algorithmi-
cally computable (effectively calculable) functions.