La máquina de Turing clásica viene en una variedad de sabores diferentes. La versión básica es la que describió por primera vez Turing, la versión no determinista permite la ramificación finita en cada cálculo y en la que se sigue cada rama, o en la probabilística, se elige aleatoriamente una sola rama.
Una máquina de turing no determinista resuelve provably exactamente los mismos problemas que la básica, pero lo hace exponencialmente más rápido, y las máquinas probabilísticas pueden ser simuladas eficientemente por la básica con desaceleración polinomial.
Por lo tanto, parece que, a pesar de las diferencias, estos sabores, en lo que respecta a la capacidad de resolución (pero no al poder computacional), son equivalentes.
Qué añade aquí el calificativo Quantum . El artículo en Wikipedia no es claro aquí en:
una. ¿En qué se diferencia de la versión clásica en términos de solucionabilidad ? Es decir, resuelve exactamente la misma clase de problemas, o difieren en algún aspecto esencial.
b. ¿Cómo difieren en términos de poder computacional? La suposición más simple sería la aceleración exponencial, lo que nos llevaría a máquinas de Turing no determinísticas. ¿Es esto correcto?
Compare las clases de complejidad BQP (cuántica) y BPP (clásica). Es posible que esté más familiarizado con P vs. NP; tenga en cuenta que BPP ⊆ BQP y no sabemos cómo se relaciona BPP con NP. BPP es una versión probabilística de P. De acuerdo con el modelo BQP de computación cuántica, las computadoras cuánticas son simplemente más rápidas para resolver algunos tipos de problemas. Me refiero a dos cosas al usar el término muy científico de la informática 'simplemente más rápido':
¿Por qué BQP puede ser más rápido? Bueno, resulta que podemos explotar 'funciones' físicamente computables, como la búsqueda de períodos, que es lo que permite que la factorización prima esté en la clase de complejidad BQP. Para obtener más información, consulte Algoritmo cuántico . No es correcto ver la computación cuántica como "intentar todas las respuestas simultáneamente"; esto permitiría resolver problemas NP en tiempo P, ya que no existe un modelo físico conocido de computación que lo permita. Ahora, los informáticos hablan de "¿y si pudiéramos resolver problemas de NP en tiempo constante?"; ver máquinas de oráculo .
¿Cuál sería un tipo de computación más poderoso que las máquinas de Turing? Eche un vistazo al problema indecidible . En caso de que no esté muy familiarizado con los problemas de decisión, puede pensar en un cálculo que produce una salida compleja sobre alguna entrada como, en cambio, un cálculo que toma dos entradas, la entrada y el "intento" de una solución, y simplemente da usted un 'sí' o un 'no' como salida. Para ver ejemplos de problemas que podría abordar algo 'más fuerte' que la computación cuántica clásica o [conocida], consulte la lista de problemas indecidibles .
Una característica de los problemas indecidibles es que el problema requiere que encontremos si existe alguna secuencia arbitrariamente larga que resuelva nuestro problema. ¿Recuerda esos problemas en los que tiene que pasar de una palabra a otra a través de unos pocos pasos, cada uno de los cuales implica un cambio de una sola letra y cada 'palabra' intermedia es válida? Imagínese si puede tener tantos pasos como sea necesario: no siempre será el caso de que una máquina de Turing pueda decirle si existe algún conjunto de pasos en un límite de tiempo/espacio conocido. Esto se debe a que el límite de tiempo/espacio es una función de la entrada , no de la salida. Si la salida puede ser arbitrariamente grande, 'todas las apuestas están canceladas', por así decirlo.
Si pasamos del 'cuántico' a la "verdadera descripción del universo", podríamos encontrar que nuestro universo es más poderoso que las máquinas de Turing. Por ejemplo, podríamos ser capaces de realizar de alguna manera cálculos infinitos (o arbitrariamente grandes) en tiempos limitados , tiempos que no 'explotan' de la manera que hace que ciertos problemas sean indecidibles bajo el modelo de la máquina de Turing. La transición clásica → cuántica no nos da esto, pero si realizamos la inducción en ese paso, podríamos esperar futuras transiciones que son igualmente inesperadas; uno de ellos podría hacer añicos el modelo de máquina de Turing de la realidad física.
Algunas de las diferencias entre las capacidades de las máquinas de Turing clásicas y las computadoras cuánticas se describen aquí:
http://www.cs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf
En esta sección presento un modelo general, completamente cuántico para computación. Luego describo la computadora cuántica universal Q, que es capaz de simular perfectamente cada sistema físico finito y realizable. Puede simular sistemas cerrados ideales (temperatura cero), incluidas todas las demás instancias de computadoras cuánticas y simuladores cuánticos, con una precisión arbitrariamente alta pero no perfecta. Al calcular funciones estrictas de Z a Z, genera precisamente las funciones recursivas clásicas C(T) (una manifestación del principio de correspondencia). A diferencia de T , puede simular perfectamente cualquier proceso estocástico discreto clásico finito. Además, como veremos en x3, tiene muchas capacidades notables y potencialmente útiles que no tienen análogos clásicos.
usuario3164
niel de beadrap
Mozibur Ullah