COMPUTABILITY
THEORY
The basic questions addressed by recursion theory are what does it mean for a function on the natural numbers to be computable and how can non-computable functions be classified into a hierarchy based on their level of non-computability ? the answers to these questions have led to a richtheory that is still being actively researched. The field has since grown to include the study of generalized computability and definability.
Invention central combinatorial object of recursion theory namely The universal Turning machine, predates and predetermines the invention of modern computers. Historically the study of algorithmically undecidable sets and functions was motivated by various problems in maths that turned to be undecidablea.
Recursion overlaps with proof
theory
effective descriptive set theory, model theory, and
abstract algebra. Arguably computational
complexity theory is a child of recursion theory
both theories share the same technical tool,
namely turing machine. Recursion theorists in
mathematical locgic often study the theory of
relative computability, reducibility notions and
degree structures described in the article.
effective descriptive set theory, model theory, and
abstract algebra. Arguably computational
complexity theory is a child of recursion theory
both theories share the same technical tool,
namely turing machine. Recursion theorists in
mathematical locgic often study the theory of
relative computability, reducibility notions and
degree structures described in the article.
