Módulo 23. Complejidad algorítmica, computacional y estadística
222.1. Una definición precisa puede no ofrecer un procedimiento
La complejidad algorítmica de una cadena finita es la longitud del programa más corto que la produce y termina, respecto de una máquina de referencia. La definición parece invitar a una búsqueda que enumere programas, los ejecute y conserve el más breve que reconstruya la cadena.
El obstáculo aparece cuando un programa no termina. Tal vez esté a un paso de producir la salida; tal vez necesite una cantidad enorme de trabajo; tal vez continúe indefinidamente. Observar que todavía sigue ejecutándose no permite distinguir estas posibilidades en general.
Podemos encontrar una descripción válida sin resolver ese problema. Basta ejecutar un programa que termine y comprobar su salida. Certificar que ninguna descripción más corta funcionará requiere una afirmación mucho más fuerte sobre todos los candidatos pendientes.
Conviene separar existencia, descubrimiento y certificación. Una descripción mínima existe porque hay al menos un programa que imprime literalmente la cadena y las longitudes posibles son enteros no negativos. Podemos descubrir descripciones progresivamente mejores. Sin embargo, no existe un algoritmo que entregue siempre el valor exacto de esa longitud mínima para cualquier cadena.
La afirmación no depende de que las computadoras actuales sean lentas. Vale para cualquier procedimiento algorítmico que prometa terminar con una respuesta correcta en todos los casos. Una mejora del procesador puede ampliar búsquedas concretas, pero no transforma un problema indecidible en uno decidible.
Tampoco significa que ninguna instancia pueda resolverse. Algunos programas terminan de manera evidente; otros contienen un ciclo cuya repetición podemos demostrar.
En este capítulo usaremos la complejidad simple, escrita C, para mantener la continuidad con el anterior. La referencia universal óptima quedará fija. Los razonamientos sobre imposibilidad conciernen solo a esa medida; los formatos de compresión comerciales y los lenguajes deliberadamente limitados quedan fuera de su alcance.
En un resultado aplicado, encontrar el archivo más corto entre veinte compresores es una optimización finita, mientras que encontrar el programa más corto entre todos los programas posibles es otro problema.
Una medida puede ser conceptualmente fecunda aunque no sea calculable de forma exacta y general. Sus teoremas permiten distinguir lo que una observación demuestra de lo que solo sugiere. El trabajo práctico consiste en formular sustitutos operacionales con un alcance explícito, sin atribuirles las garantías de una cantidad inaccesible.
222.2. Decidir si un programa termina
El problema de la parada pregunta si un programa dado, ejecutado con una entrada determinada, acabará deteniéndose. No pregunta cuánto tiempo parece razonable esperar ni si normalmente termina con entradas similares.
Una demostración por contradicción muestra por qué no existe un decisor universal. Supongamos que un procedimiento H recibe un programa y su entrada, termina siempre y responde correctamente si esa ejecución se detendrá.
Construimos entonces un programa D que recibe el código de un programa q. Primero consulta H sobre la ejecución de q con su propio código como entrada. Si H responde que terminará, D entra en un ciclo infinito. Si responde que no terminará, D se detiene.
Ahora ejecutamos D con su propio código. Si H anuncia que esa ejecución terminará, la definición de D hace que no termine. Si anuncia que no terminará, D termina. Ambas respuestas contradicen la corrección supuesta de H.
La conclusión es que no puede existir un procedimiento con todas esas propiedades. No prohíbe analizadores parciales que resuelvan algunos casos, ni herramientas que admitan una respuesta indeterminada, ni sistemas que funcionen dentro de una clase restringida de programas.
El argumento usa la posibilidad de representar programas como datos y ejecutar una descripción sobre otra. No necesita que una máquina tenga conciencia de sí misma; la autorreferencia es una relación formal entre códigos finitos.
El trabajo de Turing sobre computabilidad estableció el marco histórico para estos límites. La presentación diagonal anterior es una formulación moderna del problema de la parada, distinta de una transcripción literal de sus definiciones originales sobre máquinas y secuencias.
Una variante pregunta si un programa sin entrada termina desde una configuración inicial fijada. La dificultad persiste, porque cualquier entrada particular puede incorporarse al código de un programa que simule la ejecución correspondiente.
También debemos distinguir terminar de producir algún símbolo. Un programa puede escribir una cadena y continuar indefinidamente. Si nuestra definición exige una salida finita completa seguida de parada, ese comportamiento no es una descripción válida.
En la práctica, un límite de tiempo crea una tercera categoría, la de las ejecuciones no resueltas dentro del presupuesto. Etiquetarlas como no terminantes cambia una incertidumbre operacional por una afirmación matemática injustificada.
La respuesta correcta después de agotar el presupuesto es que no se observó la terminación bajo esas condiciones. Esa frase es menos rotunda, pero conserva exactamente la evidencia disponible y permite reanudar o complementar el análisis después.
222.3. Por qué no podemos calcular siempre la descripción mínima
Podemos demostrar la incomputabilidad de C sin construir un compresor particular. Supongamos que existe un algoritmo que recibe cualquier cadena y devuelve su complejidad exacta respecto de la referencia fijada.
Con ese algoritmo podríamos definir un procedimiento que recibe un entero n y busca una cadena cuya complejidad sea mayor que n. Enumera cadenas por longitud y, dentro de cada longitud, por orden lexicográfico; calcula C para cada una y se detiene ante la primera que supera el umbral.
La búsqueda terminaría. Hay infinitas cadenas y solo un número finito de programas de longitud menor o igual que n. Por tanto, esos programas no pueden describir todas las cadenas.
Llamemos x a la cadena encontrada. Por la condición de búsqueda, su complejidad sería mayor que n. Sin embargo, acabamos de describir un programa que la produce mediante una rutina fija y una codificación del entero n.
Podemos codificar n de manera autodelimitada usando una cantidad de bits que crece proporcionalmente a su logaritmo. El programa de búsqueda tiene longitud fija porque el supuesto algoritmo para C también es fijo.
Para n suficientemente grande, la suma de esa constante y el costo de codificar n es menor que n. Hemos construido entonces una descripción de x más corta que el límite que x debía superar. La contradicción invalida la existencia del algoritmo supuesto.
El razonamiento formaliza una idea cercana a las paradojas de descripción, según la cual identificar efectivamente el primer objeto que no admite una descripción breve es ya una descripción breve.
No hay contradicción en afirmar que existen cadenas de alta complejidad. El conteo del capítulo anterior lo demuestra. Lo imposible es convertir esa existencia en el procedimiento total de selección que acabamos de suponer.
Tampoco hay contradicción en definir matemáticamente aquella primera cadena. La definición usa C, que precisamente no tenemos disponible como algoritmo. Una expresión finita en lenguaje matemático no es automáticamente un programa ejecutable; definibilidad y computabilidad son nociones distintas. Podemos especificar una propiedad de manera inequívoca sin poseer un procedimiento general que decida si un candidato la cumple.
El argumento descarta el cálculo exacto universal de C. No establece que todas las aproximaciones sean inútiles ni que ninguna cota inferior pueda demostrarse. Esas conclusiones más amplias requerirían argumentos diferentes y, formuladas sin condiciones, serían incorrectas.
Lo imposible, en sentido preciso, es un algoritmo que termine siempre y entregue el mínimo correcto para todas las cadenas finitas.
222.4. Mejorar cotas desde arriba
Aunque C no sea computable, podemos aproximarla desde arriba. Comenzamos con una descripción literal conocida y conservamos su longitud como cota. Después buscamos programas más cortos que produzcan exactamente la cadena y terminen.
No debemos ejecutar cada candidato hasta que termine antes de pasar al siguiente. Un único programa que no se detenga bloquearía toda la búsqueda. Podemos repartir el trabajo mediante una simulación entrelazada.
En una primera ronda damos un paso a un conjunto inicial de programas. En rondas sucesivas incorporamos más candidatos y avanzamos las simulaciones activas. Cada programa de longitud finita acaba recibiendo tantos pasos como necesite, si la búsqueda continúa indefinidamente.
Cuando una ejecución termina y su salida coincide con el objetivo, actualizamos la mejor longitud encontrada. La sucesión de cotas nunca aumenta. Si existe un programa mínimo (y existe), alguna ronda acabará ejecutándolo hasta su terminación.
Desde ese momento la cota será exacta. El problema es que el procedimiento no tiene una señal general que indique que ese momento ha llegado.
Esta propiedad, la existencia de una aproximación computable mediante valores que descienden hasta el valor verdadero, se denomina semicomputabilidad superior. El adjetivo «superior» indica que las aproximaciones son cotas por encima del mínimo.
Para una cadena concreta, la sucesión entera solo puede disminuir un número finito de veces. Sin embargo, los intervalos entre mejoras pueden ser muy largos y no tenemos una regla computable general que certifique cuánto falta para la última.
Imaginemos una búsqueda que encuentra primero una descripción de quinientos bits, después una de ciento veinte y más tarde una de ochenta. Esos descubrimientos son válidos si las ejecuciones se verificaron. Un millón de rondas sin mejora no convierte ochenta en un mínimo demostrado.
La incertidumbre recae sobre la optimalidad; la reconstrucción puede quedar a salvo. Podemos estar completamente seguros de que la descripción de ochenta bits funciona y seguir sin saber si existe otra de setenta.
Esta asimetría orienta el lenguaje de los resultados. Es legítimo informar la mejor descripción encontrada bajo un procedimiento y un presupuesto determinados. Es distinto afirmar que se midió la complejidad algorítmica exacta.
El registro de búsqueda debe conservar también las descripciones, el decodificador, las salidas verificadas y el costo de los elementos auxiliares. Una cifra aislada no permite reconstruir la evidencia que la convierte en cota.
La aproximación desde arriba permite un progreso real, aunque carece de un certificado universal de finalización.
222.5. Qué cambia al imponer un presupuesto
Una búsqueda acotada puede ser completamente decidible. Fijemos un límite máximo de longitud L y un máximo de T pasos por programa. Hay un número finito de candidatos y cada ejecución se observa durante un tiempo finito.
Podemos simular todos los programas de longitud no mayor que L durante T pasos, conservar los que terminan con la salida buscada y escoger el más corto. Si ninguno funciona, informamos que no hubo candidato dentro de ambos límites.
Ese resultado es exacto para el problema acotado. No responde automáticamente al problema sin límites. Un programa más breve podría terminar después del paso T y uno excluido por longitud podría ser relevante para otro criterio de costo.
El número de cadenas binarias de longitud no mayor que L, incluyendo la vacía, se obtiene sumando los tamaños de todas las longitudes permitidas
Con L igual a veinte hay 2.097.151 candidatos. Si asignáramos un millón de pasos a cada uno, el presupuesto bruto superaría dos billones de pasos simulados, antes de contar detalles de administración.
Estos números ilustran una dificultad de recursos, diferente de la imposibilidad anterior. El procedimiento finito existe, aunque pueda resultar inviable. Reducir L o T hace el experimento más barato y cambia su alcance.
Podemos definir variantes de complejidad restringidas por tiempo. Para que la búsqueda de su mínimo sea un algoritmo finito hay que especificar también cómo se limita el espacio de programas o disponer de una cota efectiva suficiente sobre las descripciones candidatas.
Una opción transparente es trabajar con un lenguaje finito de modelos y una ejecución garantizada. Otra consiste en fijar simultáneamente longitud y tiempo, como acabamos de hacer. No debemos ocultar estas decisiones dentro de una etiqueta universal.
El lenguaje del capítulo anterior es un caso sencillo. Si solo permitimos descripción literal, constante o repetición de un bloque, podemos enumerar las opciones compatibles con una cadena finita y hallar la más corta dentro de ese formato.
La optimalidad obtenida es relativa a esas instrucciones. Agregar una instrucción para progresiones aritméticas puede cambiar el ganador sin invalidar el cálculo anterior.
El presupuesto debe medir tanto el esfuerzo del investigador para encontrar el código como la ejecución del decodificador. Son recursos diferentes y pueden moverse en direcciones opuestas.
Una búsqueda costosa puede descubrir una descripción que se ejecuta rápidamente. Una descripción fácil de escribir puede iniciar un cálculo interminablemente largo en términos prácticos.
222.6. Un límite de espera que tampoco puede calcularse
Consideremos todos los programas de longitud no mayor que L que efectivamente terminan en una referencia fija. Como son un conjunto finito, sus tiempos de terminación tienen un máximo, siempre que el conjunto no esté vacío.
Definamos B(L) como ese máximo y usemos cero cuando no haya ningún programa terminante. Cada valor es un entero finito bien definido. Sin embargo, no existe un algoritmo general que calcule B para todos los límites L.
Si pudiéramos calcularlo, decidiríamos la parada de cualquier programa p sin entrada. Bastaría calcular B para la longitud de p y simularlo durante ese número de pasos. Si no hubiera terminado, sabríamos que nunca lo hará.
Eso produciría el decisor universal que ya demostramos imposible. Por tanto, la función de máximos tiempos no puede ser computable.
La construcción pertenece a la familia de las funciones del castor ocupado, que introdujo Radó. Su formulación clásica usa máquinas de Turing con un número fijo de estados y maximiza cantidades como símbolos escritos o pasos; aquí usamos una variante por longitud de programa.
No debemos mezclar valores numéricos de variantes distintas. Cambiar el alfabeto, el número de estados, la definición de paso o la codificación modifica el problema.
La finitud no garantiza una accesibilidad algorítmica uniforme. Para cada L existe un mayor tiempo de parada entre los programas pertinentes, pero no tenemos un procedimiento que lo encuentre para cualquier L.
Un dispositivo físico con memoria estrictamente limitada requiere otra consideración. Si su evolución es determinista y tiene un número finito conocido de configuraciones completas, una configuración repetida demuestra que la ejecución futura también se repetirá. En ese modelo podemos decidir la parada simulando hasta observar una terminación o una repetición. La configuración debe abarcar todos los componentes relevantes, también los que no aparecen en la pantalla.
No hay conflicto con el teorema general. La computación de Turing permite usar memoria sin una cota fija previa, aunque cada paso emplee recursos finitos. El dispositivo acotado resuelve una clase diferente de ejecuciones. Con todo, enumerar todas sus configuraciones puede ser impracticable; la decidibilidad de ese caso no garantiza eficiencia.
Podemos demostrar cotas para casos particulares, analizar exhaustivamente clases pequeñas o justificar que ciertos programas no terminan. Nada de eso contradice la inexistencia de un método general.
Esta distinción ayuda a interpretar búsquedas experimentales. Si un programa pequeño tarda muchísimo antes de detenerse, produce una cota inferior sobre el máximo correspondiente. No demuestra que ese máximo haya sido alcanzado.
Para certificarlo, habría que resolver el comportamiento de todos los candidatos restantes, con argumentos válidos para cada uno. Sin esos argumentos, una simulación prolongada deja abiertas las ejecuciones que todavía continúan.
El ejemplo también muestra por qué no podemos convertir un plazo muy generoso en una garantía universal. Para cualquier regla computable que pretendiera fijar un plazo suficiente para todos los programas de cada longitud, la misma reducción a la parada produciría una contradicción.
Los plazos siguen siendo útiles para gestionar recursos. Su utilidad operacional no requiere atribuirles una propiedad matemática que no pueden tener.
222.7. Probar complejidad dentro de un sistema formal
La pregunta sobre descripciones mínimas también tiene una dimensión deductiva. Podemos intentar demostrar, dentro de un sistema de axiomas, que una cadena concreta necesita más de cierta cantidad de bits.
Los resultados de incompletitud informacional de Chaitin muestran límites para esa empresa. Una formulación prudente considera un sistema formal efectivamente axiomatizado, capaz de expresar las afirmaciones relevantes y correcto respecto de las cotas inferiores de complejidad que demuestra.
Exigimos corrección porque un sistema que permite demostrar afirmaciones falsas sobre C podría anunciar cotas arbitrariamente grandes sin que esas demostraciones fueran evidencia válida sobre la complejidad real.
La idea puede verse mediante otra búsqueda descriptiva. Si pudiéramos enumerar las demostraciones del sistema, buscaríamos una prueba de que alguna cadena tiene complejidad superior a un umbral n y devolveríamos esa cadena.
El enumerador del sistema tiene una descripción fija. Añadir el umbral requiere describir un entero. Si el sistema demostrara cotas individuales arbitrariamente grandes, esa búsqueda produciría una cadena supuestamente más compleja que el propio procedimiento que la encuentra.
Para umbrales suficientemente grandes aparecería una contradicción con la corrección asumida. Por eso un sistema fijo de esas características no puede certificar cotas inferiores arbitrariamente altas para cadenas individuales identificadas explícitamente.
El límite depende del sistema formal y de la máquina de referencia. No es un número universal que valga para cualquier texto, teoría científica o cerebro.
Tampoco implica que el sistema no pueda demostrar que existen cadenas de complejidad elevada. El argumento de conteo puede establecer su abundancia sin señalar una cadena concreta y certificar su alta complejidad.
Se ve aquí la diferencia entre demostrar existencia y exhibir un ejemplo certificado. Sabemos que ciertos objetos deben existir y, al mismo tiempo, enfrentamos restricciones para identificarlos mediante pruebas de determinado tipo.
Podemos fortalecer un sistema incorporando nuevos axiomas. Eso modifica las posibilidades deductivas y sus límites, pero no produce un sistema efectivo y correcto que elimine todas las restricciones de una vez.
Estos límites se identifican precisamente mediante razonamiento formal, que así muestra qué promesas resultan incompatibles. Los teoremas delimitan el alcance de una herramienta y permiten usarla con mayor precisión.
Al trasladar estas ideas a otros campos, conviene conservar sus hipótesis. Un estudio incompleto, una teoría discutible y un teorema de incompletitud son fenómenos distintos; compartir una palabra no establece una equivalencia.
222.8. Aleatoriedad, evidencia y objetos individuales
El conteo demuestra que la mayoría de las cadenas suficientemente largas no admiten grandes ahorros descriptivos. Sin embargo, esa afirmación colectiva no da un detector universal que certifique la complejidad de cada muestra.
Una cadena puede pasar muchas pruebas estadísticas y ser producida por un programa corto. Basta pensar en un generador determinista, cuyo algoritmo, semilla y longitud de salida forman ya una descripción.
En sentido inverso, una prueba puede detectar una desviación particular sin describir completamente la cadena. Una frecuencia inusual puede orientar un modelo, aunque no siempre conduce por sí sola a un compresor eficaz.
Debemos especificar qué pregunta responde cada prueba. Un contraste de frecuencias evalúa la compatibilidad con una hipótesis probabilística; un compresor demuestra una longitud alcanzable; una cota de complejidad es una afirmación sobre todos los programas de una referencia.
Si obtenemos una cadena mediante lanzamientos independientes de una moneda ideal, el argumento de conteo permite asignar una probabilidad alta a que no sea muy compresible. Eso no convierte el mecanismo supuesto en una prueba deductiva de la complejidad de la realización concreta.
La validez probabilística depende además del modelo de generación. Si el dispositivo repite una cadena almacenada, una apariencia estadística convincente puede ocultar una descripción breve.
Esta observación exige distinguir la evidencia sobre el proceso generador de las propiedades matemáticas absolutas del objeto producido, sin obligar a desconfiar indiscriminadamente de todo dato.
Las secuencias infinitas introducen nociones adicionales de aleatoriedad algorítmica, con condiciones sobre todos sus prefijos y sobre pruebas efectivas. No trasladaremos aquí resultados de esas nociones a una cadena finita sin especificar la traducción.
En aplicaciones, la palabra «aleatorio» suele condensar varias preguntas (ausencia de patrón detectado, imprevisibilidad bajo recursos limitados, compatibilidad con independencia o alta complejidad descriptiva). Esas propiedades pueden relacionarse, pero no son intercambiables.
Una redacción cuidadosa informa qué pruebas se hicieron, qué regularidades podían detectar y qué alternativas siguen abiertas. Declarar ese alcance hace más útil el resultado.
Por ejemplo, decir que una cadena no se comprimió con un algoritmo y una configuración determinados permite reproducir la observación. Afirmar que carece de toda estructura computable excede con mucho lo que ese experimento estableció.
La incomputabilidad explica por qué esa distancia no puede cerrarse mediante un único detector universal, aunque muchos métodos parciales sigan dando evidencia útil.
222.9. Cómo informar una búsqueda de descripciones
Un informe reproducible puede organizarse alrededor del objeto, el lenguaje, la búsqueda y la garantía. Primero debe quedar claro qué cadena se reconstruye, con qué alfabeto, orden y resolución.
Después se especifica el lenguaje descriptivo. Si usamos un compresor, necesitamos identificar el formato, los parámetros y los datos auxiliares disponibles para el decodificador. Un diccionario entrenado con información externa no desaparece del costo por permanecer en otro archivo.
La búsqueda requiere declarar el conjunto de candidatos y el criterio de detención. Un límite de tiempo, una profundidad máxima de programa y una colección de modelos producen resultados distintos.
La garantía debe expresarse sobre ese conjunto. Podemos haber encontrado el mínimo entre candidatos enumerados, una solución aproximada dentro de una familia o simplemente la mejor descripción observada hasta el momento.
Imaginemos una cadena de mil símbolos analizada mediante instrucciones literales, constantes y repeticiones de bloques. Enumeramos todos los divisores de la longitud y verificamos qué bloques reproducen exactamente la cadena.
Si calculamos correctamente los costos de cada opción, podemos certificar el mínimo del formato. La búsqueda es finita y cada candidato termina. No necesitamos resolver la parada de programas generales.
Ahora ampliamos el lenguaje con programas arbitrarios y conservamos el mismo plazo de ejecución. El resultado deja de ser una certificación completa sobre todos los candidatos breves, porque algunos pueden seguir pendientes.
El informe debe registrar esa diferencia aunque el número final de bits coincida.
Una certificación relativa puede incluir como testigo adicional la lista de opciones descartadas y el motivo de cada descarte. Para una repetición de bloques basta localizar una discrepancia entre el bloque propuesto y la cadena. Para un programa general pendiente, no haber observado todavía la salida no cumple ese papel. Esta diferencia explica por qué algunos espacios de modelos admiten auditorías exhaustivas sencillas, mientras que otros exigen restricciones más fuertes antes de dar una garantía comparable.
También conviene conservar una prueba de reconstrucción exacta. Si el código devuelve solo una aproximación, el experimento pertenece a la compresión con pérdida y necesita un criterio de distorsión.
Cuando comparamos condiciones, las reglas de codificación deben mantenerse consistentes. Modificar el lenguaje para favorecer cada muestra puede introducir costos ocultos y hacer que la comparación pierda significado.
Un análisis de sensibilidad puede mostrar cuánto depende la conclusión del formato o del presupuesto. Si varios procedimientos independientes detectan una regularidad semejante, aumenta la evidencia operacional sobre esa regularidad, aunque no se obtenga un valor exacto de C.
Esta documentación traduce una limitación abstracta en una práctica concreta, que consiste en presentar cotas verificables, distinguir búsquedas completas de incompletas y conservar los elementos necesarios para repetir la decodificación.
222.10. Lo que permanece posible
La incomputabilidad de la descripción mínima establece una frontera específica. No impide construir compresores útiles, descubrir regularidades, comparar modelos ni demostrar resultados sobre familias restringidas.
Podemos calcular longitudes de códigos explícitos, probar que ciertos formatos son óptimos dentro de una clase y estudiar su comportamiento asintótico para fuentes probabilísticas bajo hipótesis declaradas.
También podemos mejorar cotas mediante búsquedas que continúan encontrando programas más breves. Cada mejora verificada conserva su valor, aunque no sepamos si será la última.
La imposibilidad general aparece cuando pretendemos combinar universalidad, exactitud y terminación garantizada para cualquier objeto. Renunciar a una de esas exigencias produce problemas diferentes, algunos completamente tratables.
Un método puede restringir la familia de programas; otro, devolver una aproximación; otro, permitir una respuesta indeterminada. La elección debe responder al objetivo científico y declararse de forma explícita.
En la investigación empírica, rara vez necesitamos la descripción mínima absoluta para responder una pregunta útil. Puede bastar comparar qué modelo predice mejor datos nuevos o qué regularidad persiste entre registros.
Sin embargo, sustituir la pregunta requiere explicarlo. Un resultado sobre compresión práctica no se transforma automáticamente en una medición de organización, significado o capacidad adaptativa.
Un código breve puede necesitar una ejecución enorme y un procedimiento rápido puede almacenar muchos detalles literalmente. Los próximos capítulos tratarán por separado la longitud de la descripción y el tiempo de ejecución.
Las aproximaciones de Lempel–Ziv, procedimientos concretos con reglas verificables y propiedades demostradas bajo condiciones precisas, son un puente instructivo. Su utilidad no depende de resolver la incomputabilidad de C.
Trabajar dentro de límites explícitos permite saber qué parte del resultado procede de una demostración, cuál de un experimento y cuál permanece como hipótesis.
Una descripción encontrada prueba que cierto ahorro es posible. Un mínimo certificado dentro de un formato prueba optimalidad relativa. La inexistencia de un algoritmo universal impide confundir ambos logros con una solución general que la teoría descarta.
Referencias
- Turing, A. M. (1936–1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1), 230–265. Recibido y presentado en 1936; el registro editorial del volumen indica 1937. DOI: 10.1112/plms/s2-42.1.230. Texto del artículo.
- Turing, A. M. (1938). On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. Proceedings of the London Mathematical Society, s2-43(6), 544–546. DOI: 10.1112/plms/s2-43.6.544.
- Radó, T. (1962). On Non-Computable Functions. Bell System Technical Journal, 41(3), 877–884. DOI: 10.1002/j.1538-7305.1962.tb00480.x.
- Chaitin, G. J. (1974). Information-Theoretic Limitations of Formal Systems. Journal of the ACM, 21(3), 403–424. DOI: 10.1145/321832.321839.