¿Este artículo implica que Turing-Computability no es lo mismo que "efectivamente computable"?

8

En primer lugar, me disculpo si se me ha preguntado esto, pero realmente no encontré nada.

Me he topado con este artículo . Dice que hay un problema que solo las computadoras cuánticas pueden resolver. Según tengo entendido, esto debería significar, intuitivamente, que este problema es "efectivamente computable", ya que tenemos un método efectivo y real para calcularlo: construir una computadora cuántica y resolverlo. Pero, dado que una máquina de Turing (las máquinas de Turing no son computadoras cuánticas, creo) no puede resolverlo, esto no es computable.

Por lo tanto, ¿esto significa que "efectivamente computable" y "turing-computable" no son el mismo concepto? Entonces, ¿está equivocada la tesis de la Iglesia-Turing? Mi intuición dice "no", porque en ese caso, esto sería una gran noticia. Entonces, si no, ¿por qué no?

Además, soy consciente de que ya existen modelos de cálculo que son más potentes que las máquinas de Turing, pero esos son solo "teóricos", ¿no? Las computadoras cuánticas, por otro lado, son físicamente construibles.

olinarr
fuente

Respuestas:

13

Hay muchos significados diferentes de la palabra "can". ¿Hay algún algoritmo que pueda romper el cifrado AES-512? Una estrategia sería tomar los 2 ^ 512 bloques posibles de 512 bits, cifrarlos todos con la clave pública y, para cada uno de ellos, verificar si coinciden con el texto cifrado. En un sentido puramente abstracto, este es un algoritmo que "puede" romper AES-512. Desde un punto de vista práctico, convertir toda la materia del universo conocido en computadoras, y ejecutar el programa en ellas hasta la muerte por calor del universo, no sería capaz de verificar los 2 ^ 512 bloques.

Por lo tanto, existe un concepto abstracto y teórico de "poder" que no tiene en cuenta la cantidad de recursos necesarios, y un significado práctico que sí lo hace.

La computabilidad de Turing se refiere al primer tipo de "lata". Una máquina Turing es un dispositivo que puede ejecutarse por tiempo ilimitado con memoria ilimitada. Es un modelo abstracto utilizado para formular afirmaciones teóricas. No existe una verdadera TM en el mundo real.

Por lo tanto, no hay contradicción entre afirmar, por un lado, que cualquier cosa que una computadora cuántica puede hacer, una TM también puede hacer, y por otro lado afirmar que hay problemas que una computadora cuántica puede resolver, pero ninguna computadora clásica puede resolver; una computadora real tendrá restricciones de energía de la computadora que una TM no tiene.

Acumulacion
fuente
17

En primer lugar, las computadoras cuánticas (o más bien, los modelos teóricos de computación cuántica), de hecho, no son más potentes que las máquinas de Turing, en el sentido de que pueden emularse en una máquina de Turing y pueden emular una máquina de Turing. Tenga en cuenta que el artículo en sí no usa la palabra 'computable', y por una buena razón. La computabilidad no es de lo que están hablando.

La diferencia entre las computadoras cuánticas y las clásicas es la velocidad. Aquí es donde entra en juego la teoría de la complejidad. Aquí, todos los problemas que consideramos son computables, pero algunos pueden ser muy ineficientes para resolver en términos de tiempo de ejecución asintótico o uso de memoria.

La Jerarquía polinómica (PH) es una gran clase que contiene problemas que son básicamente un juego alternativo entre adivinar de forma no determinista una solución y encontrar una (o más bien, cuantificadores existenciales y universales alternos), pero todo en tiempo polinómico. P es la clase más básica dentro del PH y corresponde aproximadamente a los problemas que podemos resolver en un tiempo razonable en las computadoras clásicas. NP es otra subclase básica de PH.

BQP es el análogo de P para computadoras cuánticas. Bueno, no del todo, BQP está más cerca de BPP, donde permitimos que nuestra computadora clásica dé una respuesta incorrecta con solo una pequeña probabilidad. Los efectos cuánticos no se pueden explotar realmente sin involucrar la probabilidad de manera significativa. En cualquier caso, BPP todavía está dentro de PH.

Este artículo trata sobre un problema que se ha demostrado que no radica en el PH sino en el BQP. En cierto modo, el 'paso cuántico' permite resolver un problema que ni siquiera está cerca de P o BPP clásicamente, ni siquiera en la misma jerarquía infinita, en tiempo polinómico en una computadora cuántica. Entonces, esta es una fuerte evidencia del poder (teórico) del modelo de computación cuántica.


En cuanto a la tesis de Church-Turing, el cálculo cuántico es más rápido que el clásico no lo contradice, ya que a la tesis no le importa el tiempo de cálculo. Sin embargo, la tesis más fuerte de Extended Church-Turing se contradice con este resultado (es decir, si realmente se construyen computadoras cuánticas escalables)

Lagarto discreto
fuente
Pero entonces, ¿por qué dice "Que solo las computadoras cuánticas podrán resolver" y "la prueba de Raz y Tal demuestra que todavía habría problemas que solo las computadoras cuánticas podrían resolver"?
olinarr
66
Porque de manera realista, aunque algo puede ser computable, pero lleva más tiempo que la edad del universo para terminar, no se resolverá. No es tan difícil llamar a un problema fuera de PH algo que no resolveremos efectivamente en una computadora clásica.
Lagarto discreto
1
@NetHacker "Alguna vez podrá resolver" puede significar otras cosas además de "en realidad no puede calcular". En particular, puede escribir algoritmos que probablemente terminarían y darían el resultado que desea, pero que tomaría más tiempo que la muerte por calor del universo para terminar realmente. El problema es computable, pero de manera realista una computadora clásica " nunca será capaz de resolver".
Delioth