---
tag: X14Y880PN5
kind: concept
name: Computability theory
msc: [03D99, 03D20, 03D25]
sources:
  - url: https://en.wikipedia.org/wiki/Computability_theory
same_as:
  wikidata: Q818930
  wikipedia: Computability theory
---

## Summary

Computability theory, also called recursion theory, studies which functions and sets of natural numbers can be computed by an algorithm.
Its basic objects are [[computable functions|KZSB5E471K]], defined through [[Turing machines|758EYCN27B]] or through [[general recursive functions|HBK5QHC1GC]].
It proves that some problems, such as the [[halting problem|Z7TN2B35B0]], have no algorithmic solution.
It then compares unsolvable problems by reductions, which leads to [[Turing degrees|P5N2ND3VCG]] and to hierarchies of definable sets.

## Explanations

### L1 human

An algorithm is a finite list of exact instructions that a machine can follow.
Computability theory asks which questions about numbers can be answered by such a list, with no limit on time or memory.
Checking whether a number is prime is computable: try all smaller divisors.
Deciding whether an arbitrary program stops on a given input is not computable, and this can be proved.
The theory also measures how far an unsolvable problem is from being solvable.