Computability theory

https://en.wikipedia.org/wiki/Computability_theory

Computability theory (CT), aka Recursion theory (RT), studies computable functions and classifies algorithms and problems according to their solvability.

CT is a major branch of Theory of Computation (ToC). It originated in the 1930s through the work of Godel, Turing, Church et al., when it became apparent that some fundamental math problems cannot be solved by a computer (despite computing devices being merely theoretical at the time). (see effective method)

Computability Theory has expanded to include the study of generalized computability and definability, and in these areas, it overlaps with proof theory and effective descriptive set theory.

Computability Theory's central questions:

• the meaning of computability for a function on the natural numbers

• hierarchy of noncomputable functions based on their noncomputability

Although there is considerable overlap in terms of knowledge and methods, computability theory is studied in both math and CS, with different goals:

• math: theory of relative computability, reducibility notions, degree structs

• CS: theory of subrecursive hierarchies, formal methods, formal languages

The central issue of computability theory, when it was known as the recursion theory, was whether an arbitrary math statement is true or false.

Before such problems were addressed, the notions of computer, algorithm and computation had to be formally defined. The theoretical models that were proposed to understand computable (solvable) and incomputable (unsolvable) problems led to the development of computers.