Skip to the content ForoHackers
Log inJoin

Computabilidad: por dónde empezar

Computability
#3402 · · Quote · Report

La computabilidad pregunta qué se puede calcular, sin importar el tiempo ni la memoria. Su respuesta es una frontera precisa: algunos problemas bien definidos no tienen ningún algoritmo, jamás. El problema de la parada es el más conocido. Conocer la frontera explica por qué no pueden existir cazadores de errores, detectores de virus ni verificadores de programas perfectos.

Conceptos clave

  • Modelos de computación: las máquinas de Turing, el cálculo lambda y las funciones recursivas definen el mismo conjunto de funciones computables.
  • Tesis de Church-Turing: la afirmación de que esos modelos capturan todo lo que un algoritmo puede hacer.
  • Indecidibilidad: el problema de la parada no tiene algoritmo; la prueba usa la diagonalización.
  • Reducciones: demostrar que un problema nuevo es indecidible convirtiendo en él el problema de la parada.
  • Teorema de Rice: toda pregunta no trivial sobre lo que hace un programa es indecidible.

Vocabulario

  • Decidible: existe un algoritmo que siempre termina con un sí o un no correcto.
  • Semidecidible: un algoritmo termina con las respuestas afirmativas, pero puede no acabar nunca con las negativas.
  • Máquina universal: una máquina que ejecuta cualquier otra a partir de su descripción, antepasada de la computadora de programa almacenado.
  • Diagonalización: construir un objeto que difiere del elemento i de una lista en su posición i.

Qué estudiar, en orden

  1. Simula una máquina de Turing en unas pocas decenas de líneas y escribe una que sume dos números.
  2. Lee el argumento diagonal de que los reales no son numerables y luego la misma idea aplicada a la parada.
  3. Demuestra que el problema de la parada es indecidible y reproduce la prueba con tus palabras.
  4. Usa reducciones para mostrar que otros problemas son indecidibles, como la equivalencia de programas.
  5. Conoce el cálculo lambda y entiende por qué calcula las mismas funciones.

Etiquetas relacionadas

#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