Si muchos . Si nuestra comprensión de la física es correcta, entonces cualquier tarea computacional que pueda realizar un sistema físico puede ser realizada por los sistemas formales llamados máquinas de Turing. Alan Turing [1] demostró en 1936 que hay algunas tareas que una máquina de Turing no puede realizar, llamadas problemas indecidibles . El ejemplo clásico se llama el problema de detención : dado el código fuente de un programa, decida si finalmente saldrá o se ejecutará para siempre. Suena simple, ¿no?
De hecho, podemos ir más allá. Nuevamente, si nuestra comprensión de la física es correcta, entonces ningún sistema físico puede realizar una tarea computacional mucho más rápido que una máquina de Turing ligeramente mejorada, llamada máquina de Turing cuántica. [2] Se sabe desde al menos los años 80 que hay algunas tareas computacionales que pueden plantearse con un número razonable de bits (en una cantidad razonable de espacio físico y masa) pero que no tienen máquina de Turing, o incluso Turing cuántico máquina, podría llevarse a cabo dentro de un billón de veces la edad del universo, o con toda la energía en el universo a su disposición, etc. Estos problemas se llaman EXPTIME-complete , lo que significa que ninguna máquina puede resolver instancias del problema en n bits en menos de aproximadamente 2 ^ n pasos: tome n = 500 y debería tener un margen cómodo sobre la magnitud de cualquier recurso en el universo. Un ejemplo clásico sería mirar una posición en una versión mxm de un tablero de ajedrez (o damas , o las reglas japonesas Go ), y decidir si las blancas o las negras tienen la estrategia ganadora.
Ahora, todos estos ejemplos tienen la desventaja de que si apareciera con una máquina que, según afirma, podría llevar a cabo estas tareas, no podríamos probarla simplemente ejecutándola y ver si funcionaba, porque para decidir si su máquina funciona las respuestas correctas serían tan imposibles como construir su supuesta máquina en primer lugar. Podríamos mostrarle los teoremas que prueban que su máquina es imposible, pero eso no es tan satisfactorio. =)
- ¿Por qué un qubit solo puede enviar 1 o 2 bits, incluso si está aislado, si tiene estados infinitos y almacena bits infinitos? ¿Podemos obtener esa información infinita de alguna manera?
- ¿La física cuántica ha ayudado a crear tecnología?
- ¿Es teóricamente posible almacenar qubits al nivel de partículas subatómicas?
- ¿Se necesita más potencia informática para simular el comportamiento de las partículas para la física newtoniana o cuántica?
- Si asumimos que los procesos cuánticos ocurren en el cerebro humano, ¿sería posible enredar la conciencia humana con una computadora cuántica?
Afortunadamente, hay una clase de problemas en los que deberíamos poder probar cualquier máquina que diga que funciona y demostrar que es defectuosa. ¡El problema es que no podemos probar esto! Si bien sabemos que ninguna máquina de Turing (cuántica) con recursos razonables puede resolver un problema de EXPTIME-complete, solo sospechamos que ningún sistema puede resolver un problema de NP-complete . [3] Estos problemas pueden no ser tan caros de resolver como sus parientes EXPTIME-complete, pero una máquina puede verificar sus soluciones a bajo costo. Los ejemplos clásicos de problemas NP-completos incluyen decidir si un conjunto de objetos de tamaños dados puede caber en un conjunto de cajas dado (el ” problema de la mochila “), si una red dada tiene un conjunto de k nodos todos directamente conectados entre sí ( el ” problema de la camarilla “), o si una fórmula lógica dada es siempre cierta (el (co-) ” problema de satisfacción “).
Entonces, hay algunos problemas (indecidibles y problemas EXPTIME-complete) en los que si afirma que tiene una máquina que puede resolverlos, podemos rechazar la máquina con un teorema, pero no podemos probar su salida . Hay otros (problemas de NP completo) en los que deseamos tener un teorema, pero si usted afirma tener una máquina, podríamos probarla y, casi con toda seguridad, podríamos demostrar que ha fallado.
Descargo de responsabilidad: esta no era mi área de especialización en informática teórica, y no estudié exhaustivamente para obtener esta respuesta, por lo que un experto sin duda señalaría cosas en las que me equivoqué.
[1] No los nombró por sí mismo, por supuesto, pero todos los demás lo hicieron después de que los hizo un buen uso.
[2] Para ser claros, una máquina de Turing normal puede hacer todo lo que una máquina de Turing cuántica puede hacer; de hecho, puede seguir lo que hace esta última paso a paso, pero puede llevar más tiempo.
[3] Los expertos (¿casi?) Universalmente creen que esto es cierto, pero nadie tiene una prueba. El problema es mostrar que BQP! = NP – BQP son problemas que una máquina cuántica de Turing puede resolver de manera eficiente, y NP son problemas que una máquina de Turing puede verificar una solución putativa de manera eficiente. Desafortunadamente, esta es una versión más difícil del famoso problema P vs NP, así que no esperes una prueba pronto.
