Computability theory Study Guide

📖 Core Concepts Church–Turing Thesis – Any function that can be calculated by a clear step‑by‑step procedure (an algorithm) can be computed by a Turing machine. Computable (Decidable) Set / Function – A Turing machine halts with output 1 for members (or the correct value) and 0 for non‑members. Computably Enumerable (c.e.) Set – A set that a Turing machine can list (output all its elements) even if it may run forever on non‑members. Non‑Computable Set – No Turing machine decides membership; classic example: the halting problem set. Oracle Turing Machine – A TM that can ask instantaneous “membership” queries to a fixed set (the oracle). Turing Reducibility (≤ₜ) – Set A ≤ₜ B if an oracle TM with oracle B decides A. Many‑One Reducibility (≤ₘ) – A ≤ₘ B if a total computable function f satisfies x∈A ⇔ f(x)∈B. Turing Degree – Equivalence class of sets that are mutually Turing‑reducible; measures “how uncomputable” a set is. Turing Jump (A′) – Given a set A, A′ encodes the halting problem for oracle machines with oracle A; always a strictly higher degree. Post’s Problem – Are there c.e. sets of intermediate degree between computable sets and the halting problem? Answer: yes (Friedberg–Muchnik). Priority Method – Construction technique that meets an infinite list of requirements ordered by priority; used to build intermediate‑degree sets. Rice’s Theorem – Any non‑trivial semantic property of the language recognized by a TM is undecidable. Recursion Theorem – Every computable transformation has a program that can obtain its own code and apply that transformation to itself. --- 📌 Must Remember Decidable = computable = recursive (TM halts on every input). c.e. ≠ decidable: a c.e. set may be non‑decidable (e.g., the halting set). c.e. ⇔ range of a computable function. Countability: Only countably many computable sets vs. uncountably many subsets of ℕ. Many‑one ⇒ Turing reducible, but not conversely. Turing jump raises degree: A < A′ < A′′ … Rice’s theorem: To prove a property undecidable, show it is non‑trivial (holds for some TM languages and fails for others). Post’s theorem: Levels of the arithmetical hierarchy correspond to iterated Turing jumps. --- 🔄 Key Processes Testing Decidability Show a TM that halts with correct yes/no answer → decidable. Show reduction from a known undecidable problem (e.g., halting) → undecidable. Constructing a c.e. Set via Priority Method List requirements R₀, R₁, … (e.g., “avoid being computable”). Assign a priority order (lowest index = highest priority). Stage s: satisfy the highest‑priority unsatisfied requirement while preserving lower‑priority commitments. Continue indefinitely; the limit set meets all requirements. Performing a Many‑One Reduction Define a total computable function f. Prove: ∀x (x∈A ⇔ f(x)∈B). Conclude A ≤ₘ B and thus A ≤ₜ B. Applying the Recursion Theorem Given computable transformation Φ(e), obtain index e₀ such that program e₀ computes Φ(e₀). Use to embed self‑reference in constructions (e.g., fixed‑point proofs). --- 🔍 Key Comparisons Decidable vs. c.e. Decidable: TM halts on all inputs (yes/no). c.e.: TM halts only on members (produces a list). Turing Reducibility vs. Many‑One Reducibility Turing: Oracle answers may be adaptive; uses any number of queries. Many‑one: Single total computable function, no queries. Oracle TM with Computable Oracle vs. Non‑computable Oracle Computable oracle adds no power (still decidable). Non‑computable oracle can compute sets beyond the standard TM (e.g., halting problem). Strong Reducibility (e.g., truth‑table) vs. Turing Strong: Reduction must produce a total answer using a fixed finite query pattern. Turing: May use unbounded, adaptive queries. --- ⚠️ Common Misunderstandings “c.e. = decidable” – False; many c.e. sets (halting problem) are undecidable. “All non‑computable sets are of the same difficulty” – Wrong; Turing degrees distinguish levels of uncomputability (intermediate degrees exist). “If A ≤ₘ B then A is easier than B” – Many‑one reduction guarantees Turing reducibility, but the converse need not hold; some problems are Turing‑reducible without a many‑one reduction. “Rice’s theorem proves every property of TM languages is undecidable” – Only semantic (non‑trivial) properties; syntactic properties (e.g., “has exactly three states”) can be decidable. --- 🧠 Mental Models / Intuition Halting Problem as a “black box” – Think of an oracle that instantly tells you whether any program halts; adding this box strictly enlarges what you can compute (the Turing jump). Degree Ladder – Visualize degrees as rungs on a ladder: computable at the bottom, halting problem one rung up, its jump another rung up, etc. Priority as “traffic rules” – Higher‑priority requirements have the right‑of‑way; lower‑priority ones must adjust when conflicts arise. --- 🚩 Exceptions & Edge Cases Complement of a c.e. set – May be non‑c.e.; a set is computable iff both it and its complement are c.e. (Lattice of c.e. sets). Many‑one reducibility does not imply invertibility – Even if A ≤ₘ B, there need not be a reduction from B to A. Truth‑table reducibility requires a uniform bound on the number of oracle queries; some Turing reductions cannot be converted to truth‑table reductions. --- 📍 When to Use Which Prove undecidability → Reduce from the halting problem (Turing reduction) or apply Rice’s theorem if the property is semantic. Classify a set’s degree → Show mutual Turing reductions with known sets; use the Turing jump to move up a level. Show a set is c.e. → Exhibit a TM that enumerates its elements or present it as the range of a computable function. Demonstrate intermediate degree → Use the priority method (Friedberg–Muchnik construction). Compare two problems → Use many‑one reduction for a clean, single‑function mapping; use Turing reduction when adaptive queries are needed. --- 👀 Patterns to Recognize “Enumerate → c.e.” – Whenever a construction lists elements without guaranteeing termination on non‑members, you have a c.e. set. “Self‑reference → Recursion Theorem” – Problems that require a program to know its own code usually invoke the recursion theorem. “Non‑trivial property of TM language → Rice’s theorem” – Look for statements like “the language is regular” or “contains a prime number” – these are semantic and undecidable. “Jump → higher‑level arithmetical hierarchy” – Each application of the Turing jump corresponds to moving up one quantifier alternation in the hierarchy. --- 🗂️ Exam Traps Confusing “c.e.” with “decidable” – Test writers may list a set that is enumerable but not decidable; remember the halting set is the canonical counter‑example. Assuming many‑one reducibility is symmetric – It is not; only Turing equivalence is symmetric. Misapplying Rice’s theorem to syntactic properties – Properties like “the TM has exactly three states” are decidable; only semantic properties trigger Rice. Treating the Turing jump as a function on numbers – It operates on sets (or oracles), not on individual natural numbers. Overlooking the “strong” requirement in truth‑table reducibility – Forgetting the need for a total, bounded‑query reduction leads to incorrect claims of equivalence with Turing reducibility. ---