Shahada ya kwanza (juu)ComputationImepangwa
Computability
Turing machines and other models of computation, the Church–Turing thesis, decidable and recursively enumerable sets, the undecidability of the halting problem, reductions and Rice's theorem.
math.comp.computability
Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.
Inajengwa juu ya
Masharti ya awali ya lazima 21 (hadi chini kabisa)
Utajifunza
- 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.
Fasili
- 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.
Nadharia
- 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.
Mawazo potofu ya kawaida
- 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.
Inaelekea kwa
Ugunduzi wa hiari
- The λ-calculus Church's λ-calculus computes exactly the same functions as Turing machines.
- ← Repetition and decisions
- ← First-order logic
Njia za kujifunza
Usomaji zaidi
- Michael Sipser, Introduction to the Theory of Computation (1996)
- George S. Boolos, John P. Burgess and Richard C. Jeffrey, Computability and Logic