Esta es una pregunta mucho más difícil de lo que parece a primera vista.
La idea de que una máquina de Turing puede calcular todas las funciones que cualquier sistema físico que sigue estrictamente un algoritmo puede calcular, se conoce como la tesis de Church-Turing. (*)
La tesis de Church-Turing no define rigurosamente qué podría ser “un sistema físico que sigue estrictamente un algoritmo”. Depende de la ley de la física qué forma podría tomar dicho sistema, y nunca podemos estar seguros de que conocemos todas las leyes de la física.
- ¿Qué se usó antes de LaTeX para escribir documentos matemáticos? ¿Cómo se dibujaron las figuras? ¿Cómo se generaron y posicionaron las ecuaciones matemáticas con notación complicada en el documento? ¿Quién hizo la composición en su forma final para imprimir después de que fue aceptada?
- Para un número binario [matemático] n [/ matemático], ¿cuál es la probabilidad de que los dígitos contengan 1 consecutivos? Por ejemplo, un número binario de 3 dígitos tiene 8 posibilidades, y 110, 011 y 111 son los 3 escenarios donde hay 1s consecutivos.
- ¿Cómo se puede dividir un conjunto de números en dos subconjuntos de modo que el XOR de los elementos en un subconjunto sea igual al XOR de los elementos en el otro y sea lo más grande posible?
- ¿Qué es un algoritmo para encontrar la mediana de la complejidad en o (n) tiempo?
- ¿Cómo valora las opciones sobre acciones utilizando la transformación de Fourier?
Entonces, la tesis de Church-Turing es una hipótesis empírica , del tipo que normalmente se encuentra en las ciencias naturales. Nunca se puede probar, solo no se puede probar, si alguien encuentra un método de cálculo de una función que probablemente no se puede hacer en una máquina Turing.
Algunas personas llaman a la tesis de Church-Turing una “conjetura”, pero eso es engañoso, ya que las conjeturas matemáticas son afirmaciones matemáticas precisas no relacionadas con el mundo físico, que podrían probarse, al menos en principio.
Sin embargo, es una hipótesis muy fuerte. Nadie ha encontrado el más mínimo indicio de un método para calcular una función que podría llevarse a cabo en la práctica, pero no con una máquina Turing. Además, encontrar un método de este tipo sin duda sería difícil, porque las máquinas de Turing pueden simular las leyes de la física tal como se las entiende actualmente. (**) Por lo tanto, probablemente podrían simular su método. Por lo tanto, para todos los efectos, es un resultado empírico muy bien establecido y confiable que las máquinas de Turing pueden ejecutar todos los algoritmos.
Dado que todos están tan convencidos de la validez de la tesis de la Iglesia-Turing, las personas se sienten seguras para definir una función que sea “computable” si es computable en una máquina de Turing, e “incuestionable” si no lo es. Se conocen muchas funciones incompatibles, pero no hay forma de asegurarse de que nunca serán computables utilizando algo que no sea una máquina Turing.
(*) Originalmente, la tesis se refiere a los humanos que siguen un algoritmo, pero me gusta generalizarlo a cualquier sistema físico.
(**) No necesita una computadora cuántica para hacer esto, aunque las computadoras clásicas ejecutarán la simulación mucho más lentamente, pero eso no es relevante aquí.
