Saltar al contenido ForoHackers

Computability: start here

Computabilidad
#3401 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder