Recursive function theory

Recursive function theory
Name	Recursive function theory
Established	1930s
Notable figures	Alonzo Church, Alan Turing, Kurt Gödel, Emil Post, Stephen Kleene, A. A. Markov, Harvey Friedman, Richard M. Friedberg, Solomon Feferman, Hilary Putnam, Michael O. Rabin, Dana Scott, Gerald Sacks, Robert Soare, C. S. J. Karp, Juraj Hromkovič

Recursive function theory Recursive function theory is the branch of mathematical logic and theoretical computer science that studies computable functions, decidability, and the formal properties of definability via effective procedures. It develops formal classifications of functions and sets according to algorithmic computability, relates syntactic formalisms to machine models, and analyzes hierarchies of unsolvability and reducibility. The subject historically connected foundational work in the 1930s with later advances in degree theory, proof theory, and applications to complexity and algebra.

History and origins

Early genesis arose from interactions among logicians working on the Entscheidungsproblem and formal systems in the 1930s: Alonzo Church proposed the lambda calculus and Church's thesis, while Alan Turing introduced his Turing machine model. Kurt Gödel's incompleteness results motivated study of effectively calculable functions, and Emil Post developed decision problems and recursion as a formal notion. The school of Stephen Kleene formalized partial and general recursive functions, influenced by work of A. A. Markov and the Moscow school, and later contributions from Harvey Friedman and Richard M. Friedberg expanded priority methods and recursion-theoretic constructions.

Definitions and classes of recursive functions

Fundamental definitions distinguish total recursive (computable) functions from partial recursive functions and primitive recursive functions; these classes were formalized by Stephen Kleene and compared to lambda-definable and Turing-computable functions in the work of Alonzo Church and Alan Turing. Primitive recursive functions are generated from initial functions by composition and primitive recursion, while general recursive (partial recursive) functions add the minimization operator studied by Kurt Gödel and Emil Post. Recursively enumerable (r.e.) sets, many-one reducibility, and m-completeness emerged through investigations by Emil Post and further structural results by Gerald Sacks and Robert Soare.

Relationship to computability and Turing machines

Equivalence theorems show that recursive definitions, the lambda calculus of Alonzo Church, and the Turing machine model of Alan Turing capture the same class of computable functions, forming the core of Church–Turing thesis discussions involving Kurt Gödel's perspectives. Connections to automata and complexity were deepened by work of Michael O. Rabin and Dana Scott on finite automata and decision procedures, and by later investigations into resource-bounded variants influenced by Juraj Hromkovič and others. The correspondence between syntactic recursion-theoretic notions and machine models enables reductions, completeness results, and comparisons with complexity classes studied by researchers such as C. S. J. Karp.

Degrees of unsolvability and reducibility

Degree theory classifies Turing degrees and many-one degrees, with seminal contributions from Emil Post initiating the Post problem and the concept of r.e. degrees, and later solutions by Richard M. Friedberg and Andrey Muchnik using priority arguments. The structure of the Turing degrees was explored by Gerald Sacks and Robert Soare, while notions of truth-table reducibility, weak truth-table reducibility, and jump operators were formalized in work connected to Harvey Friedman and Hilary Putnam. Advanced topics include the arithmetical hierarchy and the analytical hierarchy, building on techniques from Kurt Gödel and later expansions by Solomon Feferman.

Recursion theory in mathematical logic and proof theory

Recursive function theory interfaces with proof theory through representability of computable functions in formal systems studied by Kurt Gödel and formalizability in systems like Peano arithmetic investigated by Solomon Feferman and Gerald Sacks. Results on provability, provable computability, and reverse mathematics connect to definability hierarchies examined by Harvey Friedman and contributors in the reverse mathematics program. The analysis of models of arithmetic, degree spectra of relations, and automorphisms of the computability-theoretic structures involve researchers such as Robert Soare and Gerald Sacks.

Applications and related areas

Recursive function theory underpins decidability results in algebra and number theory studied by logicians linked to Hilbert's problems, informs complexity-theoretic reductions used in algorithmic research driven by investigators like C. S. J. Karp, and influences formal verification methods developed in communities around Michael O. Rabin and Dana Scott. Interactions with modal logic, set theory, and constructive mathematics occur through work of Solomon Feferman and Hilary Putnam, while computable model theory and algorithmic randomness connect recursion-theoretic methods to contemporary research by scholars including Gerald Sacks and Robert Soare.

Category:Mathematical logic