La “Tesis de Church-Turing” dice que cualquier algoritmo que pueda ser realizado por un humano, puede calcularse en una Máquina Universal de Turing.
Algunas personas no están de acuerdo. Los argumentos van desde la gravedad cuántica que interactúa con sus microtúbulos, hasta el acceso al reino platónico a través de su alma, hasta algún beneficio inherente a las redes neuronales físicas. Las personas en este campo afirmarían que hay “algoritmos” que un humano puede hacer que un UTM nunca puede hacer, como tener conciencia.
Pero, si le damos un pase, entonces la barra para implementar “cualquier algoritmo finito” es implementar una Máquina Universal de Turing (y pasarle el algoritmo como entrada).
- En algoritmos, proporcione una matriz incremental del entero (-200, ... 0, ... 500) y quite un número. ¿Cuál es el algoritmo eficiente para encontrar el número que falta?
- Cómo calcular todos los quíntuples ordenados de números primos (a, b, c, d, e) de modo que [matemática] a + \ sqrt {b ^ 2 + c} = \ sqrt {d ^ 2 + e} [/ matemática]
- ¿Es posible tomar la construcción del producto para DFA con diferentes idiomas?
- ¿Cuál es un ejemplo de un montón que requiere exactamente n * log (n) pasos? Sé que el límite superior de un montón es O (n log n), pero ¿cómo hago para mostrar un ejemplo donde requiera exactamente n * log (n) pasos?
- ¿Es justo decir que las matemáticas, la informática y la programación se encuentran en la intersección de todas las materias?
Una prueba matemática formal de que un lenguaje de programación es capaz de computación universal generalmente toma la forma de implementar otro lenguaje de programación que se sabe que es universal, o un pequeño UTM directamente. Se sabe que existen varios UTM pequeños, como uno con solo 4 estados y 6 símbolos. Ver Máquina universal de Turing – Máquinas más pequeñas.
La mayoría de los lenguajes de programación tienen algunas partes que dependen de la implementación o la plataforma, y otras partes que son la semántica del lenguaje. Por ejemplo, en C el tipo “largo” debe ser de al menos 32 bits, pero podría ser más. Es posible que algún algoritmo no se pueda implementar porque el espacio de direcciones de la computadora, o algún otro límite definido por la implementación, no permitió una “cinta” ilimitada para el UTM. Pero generalmente tratamos esto como una limitación en la computadora (que en realidad son máquinas de estado finito muy grandes), no del lenguaje en sí.
