La computabilidad de la física

Question

Como tengo entendido Universal Cuántica Simulador puede simular cualquier sistema cuántico y por lo tanto nada de lo que existe en el universo. También, un ordenador cuántico puede implementar un simulador cuántico. Además, por lo que he leído, un ordenador cuántico no tiene la capacidad para calcular algo que no es computable por una clásica Máquina de Turing, aunque se puede realizar determinados cálculos de manera mucho más eficiente.

Sin embargo, hace poco vi esto: Clásico problema es indecidible en un quantum de configuración. El papel real: Cuántica de la medición de la ocurrencia es indecidible

No entiendo esto, por desgracia, así que quería preguntar, ¿esto quiere decir que la física no es computable por una clásica equipo (Máquina de Turing)? Lo que por un ordenador cuántico? O es este artículo que decía algo diferente?

Answer 1

El artículo está diciendo algo diferente.

Hay una diferencia entre ser capaz de ejecutar un programa (máquina de Turing) y ser capaz de decidir si el programa evenutally termina de ejecutarse. El último se llama un $\Pi_1$ decisión del problema.

Un clásico de la computadora puede ejecutar cualquier programa, sujeto a las limitaciones de recursos, pero no existe ningún algoritmo para decidir si un determinado programa de nunca acabar.

El artículo ha llegado con un tipo de sistema físico y un problema de decisión. Se resuelve el problema de decisión de la versión clásica del sistema y demuestra que el problema de decisión para la versión cuántica del sistema es indecidible. Esto no significa que un clásico ordenador no se puede simular la versión cuántica del sistema. Esto significa que, en general, no puede contestar una pregunta acerca de lo que podría llegar a suceder (y tampoco puede un ordenador cuántico responder a la pregunta).