Tesis de la iglesia afirma que la máquina de Turing es un modelo universal de computación. ¿Cuál es el más convincente argumento que apoya esta afirmación?
Respuestas
¿Demasiados anuncios?
Zack Peterson
Puntos
19350
Hay una buena cantidad de 'la evidencia experimental', supongo. Ha habido un montón de otros modelos propuestos, y todos ellos han demostrado ser computacionalmente equivalentes a las máquinas de Turing. Esto es cierto incluso para los ordenadores cuánticos. Es decir, que todos podemos hacer exactamente las mismas cosas que las máquinas de Turing pueden. Pero también está la cuestión de si esta equivalencia es un polinomio de equivalencia a tiempo. Esto conduce a la "fuerte de la tesis de Church-Turing'. Se cree por muchos que los ordenadores cuánticos son estrictamente mejor que la clásica de los equipos en términos de tiempo, complejidad, aunque que yo sepa esto no ha sido probado todavía. Si esto se demuestra, entonces, el fuerte de la tesis de Church-Turing sería falso. Luego de lo natural sería afirmar una versión cuántica de la fuerte de la tesis de Church-Turing...
Edit: veo que este tema ha sido cerrado. Estoy de acuerdo en que es tal vez demasiado filosófico para las Matemáticas de Desbordamiento. Pero aún así, permítanme hacer un poco más de matemáticas comentarios, y un comentario filosófico. Considerar el cálculo lambda. Este es un modelo muy simple de cálculo; su funcionalidad es esencialmente restringido a una noción de una función y una noción de evaluación de las funciones, lo que permite la recursividad. Lo interesante es que, incluso con esta aparentemente muy limitado de funciones, el cálculo lambda es todavía Turing equivalente. Lo que esto demuestra es que es relativamente fácil para un "razonable modelo de cálculo" para ser al menos tan potente como máquinas de Turing; una vez que se tiene una noción de funciones y una noción de evaluación de las funciones, será al menos tan poderoso como el cálculo lambda, y por lo tanto máquinas de Turing. La más filosófica, la pregunta surge cuando consideramos la situación opuesta, es decir, ¿por qué deberíamos esperar "razonable modelos de cálculo" para no ser estrictamente más potente que las máquinas de Turing? No es (probablemente) no hay buena respuesta matemática a esto, porque no es (probablemente) no hay una buena definición matemática de "razonable".
TomvB
Puntos
131
