Saltar al contenido ForoHackers

Computabilidad: por dónde empezar

Computabilidad
#3402 · · Citar · 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

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