Mathematical logic and foundations Computability theory Concept
Computable set
Summary
A computable set, also called a recursive or decidable set, is a set of natural numbers for which an algorithm decides membership. The algorithm must halt on every input and answer yes or no correctly. Computable sets are exactly the sets whose characteristic function is a total computable function. They are the bottom level of the hierarchies of complexity of sets in computability theory.
Where this leads
12 pages build on this one.
- Gödel numbering
- Rice's theorem
- Wang tile
- Turing degree
- Many-one reduction
- McKenzie's undecidability of the finite basis problem
- Word problem for groups
- Turing reduction
- Church's theorem on undecidability of first-order logic
- Hilbert's tenth problem
- Undecidability of the halting problem
- Word problem for free lattices
Further reading
About this page
| Tag | PPGD5KW8JC |
|---|---|
| URI | m2://PPGD5KW8JC |
| Kind | concept |
| Writing | W0 stub |
| MSC | 03D25, 03D20 |
| Specializes | Subset |
| Same as |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Gödel numbering
- Rice's theorem
- Turing degree
- Many-one reduction
- Word problem for groups
- Turing reduction
- Church's theorem on undecidability of first-order logic
- Hilbert's tenth problem
- Undecidability of the halting problem
- Word problem for free lattices