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