Empoderado por inteligencia artificial tecnologías, las computadoras de hoy pueden entablar conversaciones convincentes con personas, componer canciones, pintar cuadros, jugar ajedrez y listoy diagnosticar enfermedades, por nombrar solo algunos ejemplos de su destreza tecnológica.
Estos éxitos podrían tomarse como una indicación de que la computación no tiene límites. Para ver si ese es el caso, es importante comprender qué hace que una computadora sea poderosa.
Hay dos aspectos en el poder de una computadora: la cantidad de operaciones que su hardware puede ejecutar por segundo y la eficiencia de los algoritmos que ejecuta. La velocidad del hardware está limitada por las leyes de la física. Algoritmos—básicamente conjuntos de instrucciones— están escritas por humanos y traducidas a una secuencia de operaciones que el hardware de la computadora puede ejecutar. Incluso si la velocidad de una computadora pudiera alcanzar el límite físico, los obstáculos computacionales permanecen debido a los límites de los algoritmos.
Estos obstáculos incluyen problemas que son imposibles de resolver para las computadoras y problemas que son teóricamente solucionables pero que en la práctica están más allá de las capacidades de incluso las versiones más poderosas de las computadoras actuales imaginables. Los matemáticos y los informáticos intentan determinar si un problema tiene solución probándolos en una máquina imaginaria.
Una máquina informática imaginaria
La noción moderna de algoritmo, conocida como máquina de Turing, fue formulada en 1936 por el matemático británico Alan Turing. Es un dispositivo imaginario que imita cómo se realizan los cálculos aritméticos con un lápiz sobre papel. La máquina de Turing es la plantilla en la que se basan todas las computadoras de hoy.
Para acomodar cálculos que necesitarían más papel si se hicieran manualmente, el suministro de papel imaginario en un Máquina de Turing se supone que es ilimitado. Esto es equivalente a una cinta ilimitada imaginaria, o "cinta", de cuadrados, cada uno de los cuales está en blanco o contiene un símbolo.
La máquina está controlada por un conjunto finito de reglas y comienza con una secuencia inicial de símbolos en la cinta. Las operaciones que puede realizar la máquina son moverse a una casilla vecina, borrar un símbolo y escribir un símbolo en una casilla en blanco. La máquina calcula realizando una secuencia de estas operaciones. Cuando la máquina termina, o se “detiene”, los símbolos que quedan en la cinta son la salida o el resultado.
La informática a menudo se trata de decisiones con respuestas de sí o no. Por analogía, una prueba médica (tipo de problema) comprueba si la muestra de un paciente (una instancia del problema) tiene un determinado indicador de enfermedad (respuesta sí o no). La instancia, representada en una máquina de Turing en forma digital, es la secuencia inicial de símbolos.
Un problema se considera "soluble" si se puede diseñar una máquina de Turing que se detenga para cada instancia, ya sea positiva o negativa, y determine correctamente qué respuesta produce la instancia.
No todos los problemas se pueden resolver
Muchos problemas se pueden resolver con una máquina de Turing y, por lo tanto, se pueden resolver en una computadora, mientras que muchos otros no. Por ejemplo, el problema del dominó, una variación del problema de mosaico formulado por el matemático chino-estadounidense hao wang en 1961, no tiene solución.
La tarea es usar un conjunto de fichas de dominó para cubrir una cuadrícula completa y, siguiendo las reglas de la mayoría de los juegos de dominó, igualar el número de puntos en los extremos de las fichas de dominó contiguas. Resulta que no existe ningún algoritmo que pueda comenzar con un conjunto de fichas de dominó y determinar si el conjunto cubrirá o no completamente la cuadrícula.
Manteniéndolo razonable
Una serie de problemas solucionables pueden resolverse mediante algoritmos que se detienen en un período de tiempo razonable. Estos "algoritmos de tiempo polinomial” son algoritmos eficientes, lo que significa que es práctico usar computadoras para resolver instancias de ellos.
No se sabe que miles de otros problemas solucionables tengan algoritmos de tiempo polinomial, a pesar de los intensos esfuerzos en curso para encontrar tales algoritmos. Estos incluyen el problema del viajante de comercio.
El problema del vendedor ambulante pregunta si un conjunto de puntos con algunos puntos conectados directamente, llamado gráfico, tiene un camino que comienza en cualquier punto y pasa por todos los demás puntos exactamente una vez, y regresa al punto original. Imagine que un vendedor quiere encontrar una ruta que pase por todos los hogares de un vecindario exactamente una vez y regrese al punto de partida.
Estos problemas, llamados NP-completo, fueron formulados de forma independiente y se demostró que existen a principios de la década de 1970 por dos científicos informáticos, estadounidenses canadienses Stephen Cook y estadounidense ucraniano Leonid Levin. Cook, cuyo trabajo llegó primero, recibió el Premio Turing de 1982, el más alto en informática, por este trabajo.
El costo de saber exactamente
Los algoritmos más conocidos para problemas NP-completos buscan esencialmente una solución a partir de todas las respuestas posibles. El problema del vendedor ambulante en un gráfico de unos pocos cientos de puntos tardaría años en ejecutarse en una supercomputadora. Dichos algoritmos son ineficientes, lo que significa que no hay atajos matemáticos.
Los algoritmos prácticos que abordan estos problemas en el mundo real solo pueden ofrecer aproximaciones, aunque las aproximaciones están mejorando. Si existen algoritmos de tiempo polinomial eficientes que puedan resolver problemas NP-completos está entre los siete problemas abiertos del milenio publicado por el Clay Mathematics Institute a principios del siglo XXI, cada uno con un premio de un millón de dólares.
Más allá de Turing
¿Podría haber una nueva forma de computación más allá del marco de Turing? En 1982, el físico estadounidense Richard Feynman, premio Nobel, planteó la idea de la computación basada en la mecánica cuántica.
En 1995, Peter Shor, un matemático aplicado estadounidense, presentó un algoritmo cuántico para factorizar enteros en tiempo polinomial. Los matemáticos creen que esto no se puede resolver mediante algoritmos de tiempo polinomial en el marco de Turing. Factorizar un entero significa encontrar un entero más pequeño mayor que uno que pueda dividir el entero. Por ejemplo, el entero 688,826,081 25,253 688,826,081 es divisible por un entero menor 25,253 27,277, porque XNUMX XNUMX XNUMX = XNUMX XNUMX x XNUMX XNUMX.
Un importante algoritmo llamado Algoritmo RSA, ampliamente utilizado para proteger las comunicaciones de red, se basa en la dificultad computacional de factorizar números enteros grandes. El resultado de Shor sugiere que la computación cuántica, si se hace realidad, cambiar el panorama de la ciberseguridad.
¿Puede un completo computadora cuántica construirse para factorizar enteros y resolver otros problemas? Algunos científicos creen que puede ser. Varios grupos de científicos de todo el mundo están trabajando para construir uno, y algunos ya han construido computadoras cuánticas a pequeña escala.
Sin embargo, como todas las tecnologías novedosas inventadas antes, es casi seguro que surgirán problemas con la computación cuántica que impondrían nuevos límites.
Este artículo se republica de La conversación bajo una licencia Creative Commons. Leer el articulo original.
Crédito de la imagen: Laura ockel / Unsplash
- Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
- Platoblockchain. Inteligencia del Metaverso Web3. Conocimiento amplificado. Accede Aquí.
- Fuente: https://singularityhub.com/2023/03/12/the-limits-of-computing-why-even-in-the-age-of-ai-some-problems-are-just-too-difficult/
