El malentendido zombi de la informática teórica

El malentendido zombi de la informática teórica

Introducción

• El libro de texto "Introduction to the Theory of Computation" de Michael Sipser incluye un ejercicio perfecto
• Ejercicio: "Si la función f:{0,1}*→{0,1} devuelve 1 o 0 dependiendo de si Dios existe, ¿es computable f?"
• Respuesta: "Sí, f es computable" (porque las funciones constantes son computables)

El concepto de computabilidad

• La computabilidad se aplica a funciones o secuencias infinitas
• No se aplica a preguntas individuales de sí/no ni a enteros individuales
• La dificultad de escribir un programa no tiene relación con la computabilidad

El problema P vs NP

• El problema P vs NP es una pregunta individual de sí/no
• La NP-dureza se aplica a funciones o lenguajes
• El problema P vs NP no puede ser incomputable ni NP-duro

La función Busy Beaver

• La función Busy Beaver es incomputable
• Un entero individual como BB(6) es computable
• La función BB completa es incomputable

El malentendido zombi de la informática teórica

• Aplicar erróneamente a enteros individuales y problemas abiertos conceptos que se aplican a secuencias infinitas y funciones
• Confundir la incomputabilidad del problema de la parada con la incompletitud de Gödel

Pregunta para los lectores

• El autor pregunta a los lectores cómo se podría evitar este malentendido zombi

Resumen de GN⁺

• Este artículo aborda malentendidos que ocurren con frecuencia en la informática teórica
• La computabilidad se aplica a funciones o secuencias infinitas, y no a enteros individuales ni a preguntas de sí/no
• El problema P vs NP es una pregunta individual, por lo que no tiene relación con el concepto de NP-dureza
• La función Busy Beaver es incomputable, pero sus valores individuales sí son computables
• Este artículo ayudará a comprender con claridad los conceptos básicos de la informática teórica

[GN⁺]

Opiniones de Hacker News

• La cuestión de si existe un algoritmo para calcular la complejidad de Kolmogorov está relacionada con el infinito

  • No existe un algoritmo para calcular la complejidad de Kolmogorov de cadenas de longitud arbitraria
  • Pero sí existe un algoritmo para calcular la complejidad de Kolmogorov de cadenas de longitud menor que n
  • Esto es posible creando una enorme tabla de consulta para todas las cadenas posibles
  • Los problemas finitos siempre pueden resolverse con un programa, pero los infinitos no necesariamente

• Opinión de que las matemáticas constructivas encajan mejor con la intuición de las personas

  • Aún no hay evidencia de que exista un programa para el problema P=NP
  • Mark Braverman demostró que todos los conjuntos de Julia (cuadráticos) son computables, pero no de forma uniformemente computable
  • En las matemáticas constructivas, el plano complejo se divide en varias regiones y se demuestra que el conjunto de Julia dentro de cada región es compacto

• Por qué es difícil entender la indecidibilidad del problema de la parada

  • Uno de los programas, return true o return false, siempre da la respuesta correcta
  • La decidibilidad solo se vuelve indecidible cuando se extiende a combinaciones infinitas de máquina/entrada

• Expresión de problemas que requieren lógica modal

  • La pregunta "¿f es computable?" está mal planteada desde el punto de vista modal
  • La pregunta "¿podría f ser computable?" es más precisa
  • Esto es similar a una directiva del compilador o una pragma

• La representación confusa de la función f

  • La función f no bifurca según el valor de "God exists"
  • Sea que f sea 0 o 1, es computable
  • La confusión surge al meter una variable libre dentro de la condición de bifurcación

• Diferencias de significado entre decidibilidad, computabilidad y existencia

  • El significado cambia entre el contexto académico y el cotidiano
  • Los números grandes existen y son computables en sentido académico, pero en la práctica no caben en el universo

• El problema de las preguntas relacionadas con "God exists"

  • No está claro si "God exists" es verdadero o falso
  • Este es un problema que surge al mezclar lenguaje natural y matemáticas

• Por qué la informática teórica y la teoría de la complejidad son difíciles para estudiantes de licenciatura en CS

  • Términos como NP-hard se reemplazan por analogías e imaginaciones populares

• Queja sobre la forma en que el blog resalta el texto

  • El color de fondo del texto seleccionado no cambia, así que no resulta intuitivo

• Propuesta de reemplazar "God exists" por otra proposición matemática

  • "God exists" debería definirse claramente como verdadero o falso