Saltar al contenido ForoHackers

Computabilidad: por dónde empezar

Computabilidad
#896 · Ophuscado · · Denunciar

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

Inicia sesión o únete para responder.