Diferencia entre revisiones de «La tesis de Church-Turing/Interpretaciones»

En 1985, Deutsch afirma que la tesis de Church es demasiado general en comparación con algunos de los principios físicos conocidos. Deutsch propone referirse a las “funciones''"funciones que de manera natural sean consideradas computables”computables"'' como “funciones''"funciones que puedan ser computadas por un sistema físico real”real"'', ya que de esta forma lo que se quiere expresar es mucho más concreto. Todo esto le permitió introducir la concepción del diseño de una máquina de Turing.

La idea anteriormente expuesta es innovadora e interesante ya que para nosotros no es fácil entender que algo “considerado"considerado computable de forma natural”natural" no pueda ser computado por la naturaleza. De esta manera, Deutsch convierte la tesis en un principio llamado “Principio"Principio de Church-Turing-Deutsch”Deutsch" cuyo enunciado se muestra a continuación:

“Todos''"Todos los sistemas físicos finitos comprensibles pueden ser simulados por una máquina de computación universal que opere en pasos finitos"''.

“Todo''"Todo sistema físico finito puede ser simulado por una máquina de Turing, cuyo coste es equivalente al coste polinomial”polinomial"''

Esta es una de las implicaciones más importantes de la Tesis de Church-Turing. Principalmente, nos vamos a fijar en la siguiente consecuencia: a partir de este momento, a partir dedado un conjunto de leyes físicas perfectamente definidas mediante el uso de experimentos, seríamos capaces de deducir a partir del CTDP, como una consecuencia directa de estas leyes, que todos los sistemas definidos mediante reglas se pueden simular usando para ello una máquina de Turing.