amchacon escribió:dark_hunter escribió:
¿Un ordenador clásico podría computar el algoritmo de Shor?
EDIT: veo que sí. Pensaba que lo de máquina universal sólo aplicaba a algoritmos clásicos.
Sin conocer el algoritmo, ya te digo que sí.
Unos de los ejercicios que nos pusieron en la carrera es demostrar que una máquina de Turing determinista y una máquina de Turing no determinista son equivalentes.
Una máquina de Turing determinista es aquella que para cada símbolo, solo tiene una respuesta posible.
Una máquina de Turing no determinista es aquella que para cada símbolo, existen múltiples respuestas que se ejecutan simultáneamente y de forma independiente.
Una máquina de Turing determinista puede emular a la otra simplemente explorando todos los posibles caminos uno a uno.
Por otro lado, una máquina de Turing determinista no deja de ser un caso especial de una no-determinista. Donde las "múltiples respuestas" son siempre uno.
Dado que con una máquina puedes simular a la otra. Ambas máquinas son equivalentes en cuanto capacidad de cómputo.