Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Theories of Computational Complexity
Автор: 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 can today algorithmically computable functions. Dedekind and Peano have been the first to use functions defined by induction, an important preliminary stage of the recursive function theory. The foundational problem, 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 rust quarter of the 20th century by Borel and Weyl. Around 1930's, Godel, Church, Kleene and Turing have provided different, but equivalent, formalisms for characterising the number-theoretic functions computable by algorithms, i.e. the algorithmically computable (effectively calculable) functions.
The deep understanding of algorithmic computability as well as the spectacular growth of computer technology gave rise to a new, large and active field which basically refers to the question "how difficult to compute is a given algorithmically computable function"; this question was rust explicitly posed by Rabin in 1959-1960.