Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Computability Theory (Definition)

The study of what problems can be solved by algorithms and models of computation.
📜

The statement of the theorem

Let N\mathbb{N} be the set of natural numbers. A partial function f:Nk→Nf: \mathbb{N}^k \to \mathbb{N} is defined to be partial recursive\text{partial recursive} (or computable) if and only if it can be computed by a Turing Machine MM. Formally, the set of all partial recursive functions is denoted R\mathcal{R}.\n\nR\mathcal{R} is the smallest class of functions containing the initial functions (zero function, successor function, and projection functions) and closed under composition and the μ\mu-operator (minimization).\n\nFor a set A⊆NA \subseteq \mathbb{N}, AA is recursively enumerable\text{recursively enumerable} (r.e.) if and only if AA is the domain of a partial recursive function, or equivalently, if AA is Σ1\Sigma_1 definable in the arithmetic hierarchy. The theory of Computability Theory investigates the structure and limitations of the class R\mathcal{R} and the corresponding Σ1\Sigma_1 sets, specifically addressing questions such as:\n\n1. **Decidability:** Determining if a set AA is recursive (i.e., both AA and N∖A\mathbb{N} \setminus A are r.e.).\n2. **Completeness:** Characterizing the limits of R\mathcal{R}, exemplified by the Halting Problem, which demonstrates that the set K={⟨e,x⟩∣Me(x) halts}K = \{ \langle e, x \rangle \mid M_e(x) \text{ halts} \} is r.e. but not recursive.\n\nMathematically, the theory establishes the equivalence between the following formalisms:\n\nPartial Recursive Functions  ⟺  Turing Computable Functions  ⟺  Lambda Definable Functions\text{Partial Recursive Functions} \iff \text{Turing Computable Functions} \iff \text{Lambda Definable Functions}