Hay problemas irresolubles... De hecho, la mayoría de los problemas lo son
Sí, se demostró con cardinalidades entre conjuntos.
Hoy voy a hablar de algo que me dejó consternada por un rato.
Un día estaba leyendo la demostración, pensé que quizá si hubiera estado con mis compañeros también hubieran sentido algo al enterarse del resultado... Luego recordé que quizá pensarían en cómo la demostración empoderaría a la clase trabajadora y yo aquí con tonterías pseudotrascendentales. (Facultad de Ciencias, Socialist Icon 💖)
En fin, empecemos.
Problemas de decisión
Dentro de la Teoría de la Computación un problema de decisión es aquel donde la salida del algoritmo sólo es Sí o No, 0 o 1, True o False, o algún equivalente
Por ejemplo, decidir si una gráfica es conexa o no, es un problema de decisión
Supongamos que fuera posible pasar cada una de todas las infinitas gráficas posibles como input al algoritmo. Luego de eso podríamos ver a las infinitas gráficas separadas en dos conjuntos.
Por ejemplo en el caso anterior L contendría a todas las gráficas que sí son conexas. Es decir, para la pregunta ¿X es conexa? nuestro conjunto L de sí-instancias son todas la gráficas conexas.
Este problema podría ser traducido a una función, codificaríamos cada gráfica a una cadena binaria y asociaríamos a cada gráfica con 1 o 0.
Problemas de decisión como funciones
Los problemas de decisión pueden ser traducidos a funciones.
Esto nos da una idea intuitiva de cómo cualquier función que va de los Naturales al {0,1} forma un problema de decisión, el problema sería: ¿Bajo f, cuál es la imagen de x?.
Además notemos que su conjunto L de sí-instancias son todos aquellos elementos que son mapeados a 1.
¿Cuántos problemas de decisión existen?
Para saber esto, basta contar cuántas funciones podemos formar.
Potencialmente, cualquier número puede ser asociado tanto con 0 como con 1.
Para contar los problemas de decisión utilizaremos la siguiente idea:
Cada posible subconjunto de los naturales, podría representar a algún conjunto L de sí instancias de alguna función.
Por ejemplo, el conjunto
L = {3, 5, 7, 9}
Forma al problema de decisión tal que mapea los números 3, 5, 7 y 9 al número 1 y al resto de los números al 0.
De esta forma, cada posible subconjunto de los Naturales es un problema de decisión.
Existe una demostración que afirma lo siguiente:
Observemos que nos gustaría tener un programa por cada problema de decisión. Así cada programa resolvería cada problema de decisión.
Cantidad posible de programas
Sabemos que cada código fuente es traducido a una cadena de bits y a su vez cada cadena de bits puede ser interpretado como un número natural.
Con esto llegamos a que cada programa posible es un número natural¹.
Con lo anterior llegamos a que, tenemos tantos programas posibles como números naturales.
¿Ya viste el problema?
Enlace
Una vez que contamos la cantidad de problemas de decisión que existen y la cantidad de programas posibles, tenemos que la cantidad de problemas es mucho más grande que los programas para resolverlos.
Pues tenemos tantos problemas como números reales, pero sólo tantos programas como números naturales.
Y dado que la cantidad de números reales es infinitamente más grande que la cantidad de los números naturales, tenemos que la cantidad de programas posibles es infinitamente más pequeña que la cantidad de problemas que existen.
Conclusión
Creo que para este punto, el título ya tiene más sentido.
Sabemos que los números naturales tienen medida cero sobre los números reales, esto quiere decir que si tuviéramos en una bolsa a todos los números posibles, al meter la mano y sacar un número tenemos una probabilidad infinitamente pequeña de haber sacado un número natural.
La mayoría de los problemas existentes no tienen solución y aún así, la mayoría de los problemas en los que pensamos tienen una solución. (¿por qué pasa eso?) es decir, aunque tenemos una probabilidad infinitamente pequeña de pensar en un problema computable, ¡pensamos en problemas computables!.
Hay problemas que aún no hemos concebido pero que ya sabemos que no podemos resolver de forma algorítmica... Hasta ahora.
Instagram (alerta nuevo post): https://www.instagram.com/mathandcss/
Google Summer of Code:
Convocatoria abierta a partir 29 Marzo 2021. Verano para trabajar en proyectos de código abierto. https://summerofcode.
¹En realidad, la forma para contar la cantidad de programas posibles es a través de la traducción de cada máquina de Turing a un número binario, pero la explicación dada guarda la esencia de lo que en realidad pasa.
**El post debe entenderse como una explicación informal, parcial y que omite muchos detalles con fines informativos.**
Comentarios
Publicar un comentario