Computability theory

From Wiki @ Karl Jones dot com
Revision as of 11:40, 29 February 2016 by Karl Jones (Talk | contribs) (See also)

Jump to: navigation, search

Computability theory, also called recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

Discussion

The basic questions addressed by recursion theory are:

The answers to these questions have led to a rich theory that is still being actively researched.

Universal Turing machine

Invention of the central combinatorial object of recursion theory, namely the Universal Turing machine, predates and predetermines the invention of modern computers.

Early applications

Historically, the study of algorithmically undecidable sets and functions was motivated by various problems in mathematics that turned to be undecidable; for example, word problem for groups and the like.

Early applications include:

Other applications

There are several applications of the theory to other branches of mathematics that do not necessarily concentrate on undecidability.

Recent applications

The field has since grown to include the study of generalized computability and definability.

The more recent applications include algorithmic randomness, results of Soare et al. who applied recursion-theoretic methods to solve a problem in algebraic geometry, and the very recent work of Slaman et al. on normal numbers that solves a problem in analytic number theory.

Related fields

Recursion theory 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 the Turing Machine.

Recursion theorists in mathematical logic often study the theory of relative computability, reducibility notions and degree structures described in this article.

This contrasts with the theory of subrecursive hierarchies, formal methods and formal languages that is common in the study of computability theory in computer science.

There is a considerable overlap in knowledge and methods between these two research communities; however, no firm line can be drawn between them.

For instance, parametrized complexity was invented by a complexity theorist Michael Fellows and a recursion theorist Rod Downey.

See also

External links