Diferencia entre revisiones de «La tesis de Church-Turing/Interpretaciones»
Contenido eliminado Contenido añadido
Línea 32:
== Strong Church-Turing thesis (SCTT) ==
En 1997, Bernstein y Vazirani expusieron la tesis Strong Church-Turing (SCTT), cuyo enunciado se muestra a continuación:
''"Any ‘reasonable’ model of computation can be efficiently simulated on a probabilistic Turing machine"''.
Es un misterio que la tesis original de Church-Turing sea equivalente a esta interpretación, aunque Turing negó dicha coincidencia.
Los estudios actuales sugieren que este enunciado es falso, puesto que no es posible capturar todas las formas de computación tanto existentes como posibles mediante un algoritmo. Por ejemplo, los protocolos interactivos no son algoritmos.
Uno de las principales razones de que se llegara a la conclusión de que dicho enunciado era falso, fue que Peter Shor demostró que el problema de factorizar los números primos se puede resolver usando un ordenador cuántico, mientras que no es posible encontrar una solución al mismo problema usando una máquina probabilística de Turing.
Las razones para por las que se acepta de forma general la “Tesis Mítica de Turing” se pueden examinar en el momento en que se estableció la Informática como una disciplina independiente en 1960. Para poder entender mejor estas razones, vamos a identificar y examinar las tres principales quejas:
• '''Conjetura 1:''' Todos los problemas computables están basados en una función. Razón: La adopción de los principios matemáticos para los conceptos fundamentales de la computación, identifican el concepto de computabilidad con la computación de funciones, al igual que con la Máquinas de Turing.
• '''Conjetura 2:''' Todos los problemas computables pueden ser descritos mediante un algoritmo. Razón: La adopción de algoritmos como conceptos generales y centrales de la Informática.
• '''Conjetura 3:''' Los computadores procesan los algoritmos. Razón: se concibe el concepto de un algoritmo para hacerlo más práctico.
| |||