Computability

يعتمد على

عدد المتطلبات السابقة الإلزامية (حتى الأساس): 21

ستتعلّم

• Design simple Turing machines and simulate them.
• Prove that the halting problem is undecidable by a diagonal argument.
• Use reductions to prove undecidability, and state Rice's theorem.

تعريف

• A Turing machine is a finite-state machine with an unbounded tape that it can read, write and move along.
• A set is decidable if some algorithm always halts and correctly decides membership, and recursively enumerable if some algorithm halts exactly on its members.
• The Church–Turing thesis states that every effectively computable function is computable by a Turing machine.

مبرهنة

• The halting problem is undecidable (Turing, 1936).
• A set is decidable if and only if both it and its complement are recursively enumerable.
• Rice's theorem: every non-trivial property of the functions computed by programs is undecidable.
• There are only countably many Turing machines, so most functions ℕ → ℕ are not computable.

مفاهيم خاطئة شائعة

• Treating the Church–Turing thesis as a theorem; it concerns the informal notion of effective computability and is supported by the equivalence of many models.
• Thinking undecidability means no instance can be solved; it means no single algorithm solves every instance.

يقود إلى

اكتشافات اختيارية

• The λ-calculus Church's λ-calculus computes exactly the same functions as Turing machines.
• ← Repetition and decisions
• ← First-order logic

مسارات التعلّم

• Computer science and formal methods

قراءات إضافية

• Michael Sipser, Introduction to the Theory of Computation (1996)
• George S. Boolos, John P. Burgess and Richard C. Jeffrey, Computability and Logic