Computability theory - Wikipedia

Computability Theory Overview

• Definition: Also known as recursion theory, this field of mathematical logic and computer science studies computable functions, effective calculation, and the classification of noncomputable problems.
• Origins: Emerged in the 1930s through the work of Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post.
• Church–Turing Thesis: The foundational hypothesis stating that any function computable by an algorithm is a "computable function."
• Key Concepts:
  • Computable Set: A set of natural numbers for which a Turing machine can determine membership (also called decidable or recursive).
  • Computably Enumerable (c.e.): Sets that can be listed by a Turing machine (also called recursively enumerable or semidecidable).
  • Undecidability: Proof that certain problems cannot be solved by any algorithm, such as the Entscheidungsproblem (1936), the word problem for groups, and Hilbert's tenth problem.
  • Halting Problem: A classic example of a noncomputable set; it is c.e. but not decidable.
  • Busy Beaver Function ($\Sigma(n)$): A noncomputable function that grows faster than any computable function.
• Relative Computability:
  • Oracle Turing Machines: Hypothetical devices that can query an "oracle" set to solve problems beyond standard Turing machines.
  • Turing Degrees: A classification system measuring the "level of uncomputability" of a set.
  • Reducibility: Methods (many-one vs. Turing) used to compare the complexity of different sets.
• Post’s Problem: A major historical question regarding whether there exist computably enumerable sets with Turing degrees strictly between computable sets and the halting problem (proven to exist in 1954 by Kleene and Post).
• Terminology Note: The field uses various terms interchangeably due to historical development, including "recursive," "decidable," and "computable," with some variation in convention (e.g., partial vs. total recursive functions).