go-v.orgcodex
Menu
Page tools

codex · Philosophy

Basis theorem (computability)

In computability theory, there are a number of basis theorems. These theorems show that particular kinds of sets always must have some members that are, in terms of Turing degree, not too complicated. One family of basis theorems concern nonempty effectively closed sets (that is, nonempty Π10 sets in the arithmetical hierarchy); these theorems are studied as part of classical computability theory. Another family of basis theorems concern nonempty lightface analytic sets (that is, Σ11 in the analytical hierarchy); these theorems are studied as part of hyperarithmetical theory.

Wikipedia contributors, "Basis theorem (computability)", Wikipedia, revision 1232545569, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex