💬 NLP

Turing or Cantor: That is the Question

Este artículo establece la dependencia de los logros de Alan Turing respecto a la teoría de conjuntos de Georg Cantor, propone una medida de indecidibilidad basada en la probabilidad de entrada y define tres nuevas clases de complejidad (U, D y H) para problemas indecidibles, demostrando que la clase U-complete no es equivalente a P.

Autores originales: Eugene Eberbach

Publicado 2026-04-14

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Eugene Eberbach

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

¡Hola! Imagina que este artículo es como un viaje de descubrimiento que nos lleva al corazón de cómo funcionan (y dónde fallan) las computadoras. El autor, Eugene Eberbach, quiere contarnos una historia sobre dos gigantes de las matemáticas: Alan Turing (el padre de la informática) y Georg Cantor (el maestro de los infinitos).

Aquí tienes la explicación, traducida a un lenguaje sencillo y con analogías divertidas:

1. El Gran Conflicto: ¿Quién es el verdadero abuelo de la informática?

La pregunta del título es: "¿Turing o Cantor: Esa es la cuestión?".

Imagina que la informática es un castillo enorme. Todos sabemos que Alan Turing construyó los cimientos y las paredes (las computadoras y los algoritmos). Pero el autor dice que olvidamos a Georg Cantor, quien trajo los planos de cómo funciona el "infinito".

La analogía: Imagina que Turing es el arquitecto que diseñó el coche más rápido del mundo. Pero Cantor fue quien le dijo: "Oye, hay carreteras que son tan largas que ningún coche, por rápido que sea, podrá recorrerlas todas". Sin Cantor, Turing no habría sabido que existían esos caminos imposibles.

2. El Problema de la "Lista Infinita" (La Prueba)

Turing demostró que hay problemas que ninguna computadora puede resolver. ¿Cómo lo hizo? Usando una idea de Cantor llamada "diagonalización".

La analogía: Imagina que tienes una biblioteca infinita con todos los libros posibles (todos los programas de computadora posibles). Turing intentó hacer un "índice maestro" (un programa que lee todos los otros programas).
- Cantor le dijo: "Espera, si intentas hacer una lista de todos los libros, siempre te faltará uno que tú mismo inventes al final".
- Turing usó esta idea para decir: "¡Exacto! Hay más problemas matemáticos (libros) que programas de computadora (índices) para resolverlos. Por lo tanto, siempre habrá problemas que las computadoras no podrán resolver".

3. Un Nuevo Medidor: ¿Qué tan "imposible" es un problema?

Hasta ahora, si un problema era "imposible" para una computadora, decíamos "fin de la historia". El autor propone algo nuevo: medir qué tan imposible es.

La analogía: Imagina que tienes un montón de llaves y un montón de cerraduras.
- Algunas cerraduras se abren con facilidad (problemas fáciles).
- Algunas se abren si tienes mucha paciencia (problemas difíciles).
- Algunas nunca se abren.
- El autor dice: "En lugar de solo decir 'no se puede abrir', contemos cuántas cerraduras de cada tipo hay". Si el 99% de las cerraduras son imposibles de abrir, el problema es "muy indecidible". Si solo el 1%, es "ligeramente indecidible".

4. Tres Nuevas Categorías de "Imposibilidad"

El autor crea tres nuevas clases para organizar los problemas que las computadoras no pueden resolver, inspirándose en cómo clasificamos los problemas difíciles (como los problemas NP-completos).

Imagina una escalera de "imposibilidad":

U-Completo (Universal): Son problemas que casi podemos resolver.
- La analogía: Es como intentar adivinar si un coche llegará a su destino. Si el coche llega, lo sabes enseguida. Pero si no llega, podrías estar esperando para siempre sin saber si se detuvo o si sigue conduciendo. Sabes que la respuesta existe, pero no sabes cuándo llegarás a ella. (Ejemplo: El problema de la parada).
D-Completo (Diagonalización): Son problemas más oscuros.
- La analogía: Aquí ni siquiera podemos saber si el coche llegó o no, ni siquiera con una lista infinita. Es como intentar encontrar una aguja en un pajar donde la aguja cambia de color cada vez que la miras. No hay forma de hacer una lista de todas las agujas posibles.
H-Completo (Hipercomputación): Son problemas que requieren magia o una computadora que no existe en nuestro universo.
- La analogía: Son problemas que ni siquiera una computadora con tiempo infinito podría resolver. Requieren un "oráculo" (una caja mágica que sabe la respuesta de todo). Para resolverlos, necesitarías una computadora que pueda hacer infinitos cálculos en un segundo, algo que va más allá de la física actual.

5. La Conclusión: Un Infinito de Infinitos

El autor termina diciendo que la jerarquía de problemas "imposibles" no termina aquí. Al igual que Cantor descubrió que hay infinitos más grandes que otros (infinitos de infinitos), también hay niveles de "imposibilidad" que nunca terminan.

El mensaje final: La informática actual se centra mucho en los problemas que sí podemos resolver (los fáciles y los difíciles). Pero el autor nos invita a mirar hacia el horizonte, hacia esos problemas que las computadoras actuales no pueden tocar, y a entender que la "imposibilidad" tiene sus propias reglas y grados, gracias a la genialidad de Cantor y Turing.

En resumen: Este paper nos dice que, aunque Turing nos dio las computadoras, fue Cantor quien nos dio el mapa para entender que hay territorios donde esas computadoras nunca podrán llegar, y ahora tenemos nuevas herramientas para medir cuán lejos están esos territorios.

Resumen Técnico: Turing o Cantor: Esa es la Cuestión

1. Planteamiento del Problema

El artículo aborda la limitación fundamental de las máquinas de Turing (MT) y la teoría de la computación clásica. Aunque Alan Turing es reconocido como el padre de la informática por demostrar la indecidibilidad del Entscheidungsproblem (problema de la decisión) de Hilbert y el problema de la parada, el autor argumenta que:

La teoría de la computación actual se centra excesivamente en problemas decidibles (recursivos) y en la complejidad de problemas intratables (NP), ignorando sistemáticamente la jerarquía de problemas indecidibles.
Existe una falta de definición explícita de clases de complejidad para problemas que no pueden ser resueltos por ninguna máquina de Turing.
Se subestima la contribución fundamental de Georg Cantor (teoría de conjuntos, cardinalidad infinita, argumento diagonal) como el "abuelo implícito" de la informática, ya que los resultados de Turing dependen directamente de las propiedades de los conjuntos infinitos demostradas por Cantor.

El problema central es cómo medir, clasificar y entender la "gravedad" de la indecidibilidad más allá de simplemente decir que un problema "no es resoluble".

2. Metodología

El autor emplea un enfoque teórico que combina la lógica matemática, la teoría de conjuntos y la teoría de la computación:

Revisión Histórica y Lógica: Analiza el trabajo original de Turing (1936) y lo contrasta con los fundamentos de Cantor (cardinalidad de los reales vs. enteros, argumento diagonal).
Prueba Reducida: Presenta una demostración más corta de la indecidibilidad del Entscheidungsproblem basándose directamente en la cardinalidad no numerable de los números reales (Cantor) en lugar de solo en la autorreferencia de Turing.
Extensión de Modelos: Propone extender la noción de las "máquinas oráculo" (o-máquinas) de Turing a toda una clase de modelos de hipercomputación (super-Turing).
Definición de Nuevas Clases: Introduce una taxonomía formal basada en la "medida de indecidibilidad" (la proporción de instancias de entrada indecidibles frente a decidibles) y la capacidad de reducción entre problemas.

3. Contribuciones Clave

A. La Primacía de Cantor en la Computación
El artículo establece que sin los resultados de Cantor sobre la diferencia entre infinitos numerables (enteros) y no numerables (reales), los resultados de Turing no existirían. Turing simplemente mapeó las máquinas a enteros y los problemas a reales; la imposibilidad de cubrir todos los problemas con un número enumerable de máquinas es una consecuencia directa de la teoría de Cantor.

B. Medida de Indecidibilidad
Se propone una nueva métrica cuantitativa para la indecidibilidad basada en la distribución de probabilidad de los datos de entrada:

0% de indecidibilidad: Problemas recursivos (decidibles).
>0% y <100%: Problemas recursivamente enumerables pero no recursivos (semi-decidibles).
100% de indecidibilidad: Problemas donde ninguna instancia es decidible por una MT.

C. Tres Nuevas Clases de Complejidad para Problemas Indecidibles
Inspiradas por la clase NP-completa de Cook/Levin, el autor define tres nuevas clases jerárquicas para problemas que las MT no pueden resolver:

U-completo (Universal Complete):
- Definición: Problemas semi-decidibles. Las palabras en el lenguaje se aceptan en un número finito de pasos, pero las palabras fuera del lenguaje pueden requerir un número infinito de pasos (o nunca detenerse).
- Ejemplos: El lenguaje de la Máquina de Turing Universal ( $L_u$ ), el Problema de Correspondencia de Post (PCP), el problema del "Busy Beaver".
- Relación: Corresponden a la clase $RE \setminus REC$ (Recursivamente Enumerables pero no Recursivos).
D-completo (Diagonalization Complete):
- Definición: Problemas indecidibles que no son ni siquiera recursivamente enumerables. Ninguna palabra (ni dentro ni fuera del lenguaje) puede ser decidida en un número finito de pasos.
- Ejemplos: El lenguaje de diagonalización ( $L_d$ ), el complemento del lenguaje universal.
- Relación: Corresponden a la clase no-RE (no recursivamente enumerables).
H-completo (Hypercomputation Complete):
- Definición: Problemas "hiper-indecidibles". Ni siquiera se pueden decidir en un número infinito de pasos (requieren recursos infinitos o lógica de orden superior).
- Ejemplos: Lenguaje de hiper-diagonalización ( $L_{hd}$ ).
- Relación: Corresponden a problemas que requieren modelos de hipercomputación (super-recursivos) para su resolución.

D. Jerarquía Infinita
El autor formula la hipótesis de que existe una jerarquía infinita de clases de complejidad para problemas indecidibles, análoga a la jerarquía de cardinalidades infinitas de Cantor ( $\aleph_0, \aleph_1, \aleph_2, \dots$ ) y a la jerarquía de lógicas de Turing basada en ordinales constructivos.

4. Resultados Principales

Prueba Simplificada: Se demuestra que el Entscheidungsproblem es indecidible mediante una reducción directa basada en la cardinalidad de Cantor: el conjunto de todos los problemas (reales) es estrictamente mayor que el conjunto de todas las máquinas de Turing (enteros).
Desigualdad de Lenguajes: Se prueba formalmente que para la clase U-completa, los lenguajes recursivos ($REC$) no son iguales a los lenguajes recursivamente enumerables pero no recursivos ( $RE \setminus REC$ ).
Respuesta Negativa a una Pregunta Análoga a P vs NP: Mientras que la pregunta $P \stackrel{?}{=} NP$ sigue abierta para problemas intratables, para la clase U-completa se responde negativamente: la clase de problemas decidibles (análogo a P) es estrictamente menor que la clase de problemas semi-decidibles (análogo a NP en este contexto de indecidibilidad).
Corolario de Cardinalidad: Se confirma que existen más problemas indecidibles (cardinalidad de los reales) que problemas decidibles (cardinalidad de los naturales).

5. Significado e Impacto

Reevaluación Histórica: El artículo busca reequilibrar la narrativa histórica, posicionando a Georg Cantor como un pilar fundamental, quizás incluso más básico que Turing, para la existencia de la teoría de la computación moderna.
Nueva Perspectiva en Complejidad: Al definir clases U, D y H completas, el autor llena un vacío teórico. La teoría de la complejidad actual se detiene en los problemas intratables (NP); este trabajo extiende el marco teórico para estudiar sistemáticamente los problemas que son imposibles de resolver con algoritmos clásicos.
Implicaciones para la Hipercomputación: El trabajo valida teóricamente la necesidad de modelos de computación más allá de la Máquina de Turing (redes neuronales, autómatas celulares, computación analógica, máquinas oráculo) para abordar problemas que caen en las clases D y H.
Medición de la Indecidibilidad: La propuesta de medir la indecidibilidad basándose en la distribución de probabilidad de las instancias de entrada ofrece una herramienta práctica para evaluar la "dureza" de un problema en contextos reales, donde quizás solo una fracción de las instancias sea indecidible.

En conclusión, el artículo no solo ofrece nuevas definiciones formales, sino que propone un cambio de paradigma: dejar de ver la indecidibilidad como un "lugar sin salida" y comenzar a clasificarla y estudiarla como una jerarquía estructurada de complejidad infinita, fundamentada en la obra de Cantor.