recursion theory

Recursion theory, a branch of logic and theoretical computer science, deals with functions that are defined by applying a procedure repeatedly to known values. Developed in the 20th century, it emerged from efforts to avoid paradoxes associated with infinite classes by specifying functions without reference to infinite sets.1

Key concepts include:
* Effective Computability: The idea of a function that can be calculated by a mechanical or algorithmic procedure. This is often formalized using concepts like Turing machines.23
* Recursive Functions: Functions that are effectively computable. Different definitions of these functions, developed independently by logicians like Alonzo Church and Alan Turing, were found to be equivalent, supporting Church's thesis that they capture the intuitive notion of effective calculability.23
* Decision Problem: A fundamental problem in recursion theory, particularly for first-order logic, asking if there's an algorithm to determine if any given formula is logically true. This problem, and others like it concerning Diophantine equations, have been shown to be recursively unsolvable.42

Recursion theory has laid foundations for theoretical computer science and explores questions about the limits of computation and the nature of mathematical thinking.53