Computadoras Quantum y Turing Machine

7

Por lo que sé, una máquina de Turing es el modelo ampliamente utilizado en la teoría computacional para saber si algo podría calcularse y si puede calcularse puede calcularse en tiempo finito (P, NP, NPSpace). Pero tengo las siguientes dudas:

  1. ¿Es una Máquina de Turing esencialmente un modelo de caja negra donde un conjunto de entradas proporciona un conjunto de salidas de tal manera que no podría haber interacción durante el cálculo? Por ninguna interacción, quiero decir que durante el cálculo las variables no se alterarían por un factor externo.
  2. Como una extensión de la pregunta anterior, ¿están completas las funciones no deterministas?
  3. ¿Es la máquina de Turing un modelo eficiente para la computación cuántica?

Siguiendo con lo que he aprendido hasta ahora, mis respuestas son:

  1. Las máquinas de Turing no pueden manejar la interacción y el comportamiento aleatorio y Turing no lo garantiza, ni siquiera en su artículo original.
  2. Las funciones no deterministas pueden detener las máquinas de Turing.
  3. No, ya que las máquinas de Turing no pueden soportar eficientemente la superposición de bits.

Nota

No estoy bien versado ni en la Teoría de la Computación ni en la Computación Cuántica. Así que un montón de enlaces y algunas cosas para principiantes serían muy útiles y leer este artículo inspirado esta pregunta.

    
pregunta Ubermensch 26.05.2012 - 17:03

3 respuestas

3

1) Como señalaste, gran parte de la teoría sobre "lo que se puede calcular" se basa en ello. Para que eso funcione es esencial saber cómo funciona internamente. Una máquina de Turing no es una caja negra. Una propiedad favorable de las máquinas de Turing es su localidad de cambio. Cada paso cambia muy poco, es decir, el estado interno (piense en él como un número), la letra en la cinta y la posición en la cinta. Este último solo se puede cambiar 1 paso hacia la izquierda o hacia la derecha. En este modelo, todas las entradas están en forma de lo que está escrito en la cinta. El contenido de la cinta solo es cambiado por la máquina. Entonces, no hay interacción.

2) Una máquina o lenguaje de programación se llama Turing completo, si puede simular todas las máquinas de Turing. Por lo tanto, las máquinas de Turing no deterministas están completas, porque pueden simular una máquina de Turing simplemente no utilizando el no determinismo. Curiosamente, un Turing determinista puede simular uno no determinista, simplemente probando todos los resultados posibles de resultados no deterministas secuencialmente. Este es un enfoque de fuerza bruta y no muy eficiente. No está claro si hay una manera eficiente de hacerlo. Por cierto, la mayoría de los científicos informáticos no creen que se pueda hacer.

En cuanto a su propia respuesta a esto, se supone que las máquinas de Turing se deben detener. En este contexto, significa que el cálculo está terminado y tiene un resultado. Se podría pensar que significa que la máquina se congela. Pero es al revés. Una máquina congelada (por ejemplo, su computadora de escritorio) no se detuvo cuando se suponía que debía hacerlo y sabe que está esperando para siempre y no puede hacer nada (pero reiniciar). El no determinismo no tiene efecto en que una máquina se detenga o no.

3) La única forma conocida de simular un dispositivo de computación cuántica utiliza el no determinismo. Como se dice en 2), podemos simular el no determinismo, pero no de manera eficiente. Y probablemente nunca lo haremos.

    
respondido por el scarfridge 26.05.2012 - 18:42
8

Las computadoras Quantum aún están dentro de los límites de Turing-complete. Puede simular exactamente uno con una máquina normal, simplemente tomaría tiempo exponencial. Por supuesto, las clases de complejidad no son necesariamente las mismas; por ejemplo, la factorización discreta es un problema de NP-difícil en una computadora clásica, pero un algoritmo cuántico puede hacerlo en tiempo lineal.

Las computadoras cuánticas no rompen fundamentalmente las reglas de cálculo. Ninguna computadora cuántica puede resolver el problema de la detención, ni nada de eso. Simplemente pueden realizar algunos tipos de computación mucho, mucho más rápido que una computadora clásica. Es exactamente lo mismo que tener una máquina clásica exponencialmente más rápida.

    
respondido por el DeadMG 26.05.2012 - 17:29
1

Aunque las computadoras cuánticas pueden ser más rápidas que las clásicas, no pueden resolver ningún problema que las computadoras clásicas no puedan resolver. Una máquina de Turing puede simular estas computadoras cuánticas, por lo que una computadora cuántica nunca podría resolver un problema indecidible como el problema de la detención. Existe una idea errónea de que las computadoras cuánticas pueden resolver problemas de NP-completa en el tiempo polinomial. No se sabe que eso sea cierto, y generalmente se sospecha que es falso. La existencia de computadoras cuánticas "estándar" no refuta la tesis de Church-Turing. La máquina D-Wave está resolviendo problemas usando tecnología cuántica, pero no es una computadora estándar o de "propósito general" en ningún sentido del término. Que haga lo que está haciendo es genial y será fascinante ver lo que nos depara el futuro. Vea las referencias citadas en la entrada de Wikipedia.

    
respondido por el Richard Rankin 10.11.2014 - 01:43

Lea otras preguntas en las etiquetas