Skip to the content ForoHackers
Log inJoin

Computability: start here

Computability
#3401 · · Quote · Report

Computability asks what can be computed at all, whatever the time or memory. Its answer is a precise boundary: some well-defined problems have no algorithm, ever. The halting problem is the famous one. Knowing the boundary tells you why perfect bug finders, virus detectors and program verifiers cannot exist.

Key concepts

  • Models of computation: Turing machines, the lambda calculus and recursive functions define the same set of computable functions.
  • Church-Turing thesis: the claim that these models capture everything an algorithm can do.
  • Undecidability: the halting problem has no algorithm; the proof uses diagonalisation.
  • Reductions: showing a new problem undecidable by turning the halting problem into it.
  • Rice's theorem: every non-trivial question about what a program does is undecidable.

Vocabulary

  • Decidable: some algorithm always halts with a correct yes or no.
  • Semi-decidable: an algorithm halts on yes answers but may run forever on no answers.
  • Universal machine: a machine that runs any other machine from its description, the ancestor of the stored-program computer.
  • Diagonalisation: building an object that differs from the i-th item of a list in its i-th place.

What to study, in order

  1. Simulate a Turing machine in a few dozen lines and write a machine that adds two numbers.
  2. Read the diagonal argument for the uncountability of the reals, then the same idea for halting.
  3. Prove the halting problem undecidable and reproduce the proof in your own words.
  4. Use reductions to show other problems undecidable, such as program equivalence.
  5. Meet the lambda calculus and see why it computes the same functions.

Related tags

#complexity #automata #logic #functional-programming

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply