Sobre la indecidibilidad del problema del salto de energía

Saber si un algoritmo se detiene tras un número finito de pasos, el problema de la parada, es un problema indecidible. Alan Turing demostró en 1936 que no hay ningún algoritmo universal capaz de decidir si cualquier otro algoritmo parará o no aplicado a una entrada arbitraria. La idea de la demostración es similar a decidir si la frase “esta frase es falsa” es verdadera o es falsa (obviamente indecidible). ¿Existen problemas físicos que sean indecidibles? No sabemos si la Naturaleza es (o tiene que ser) computable (en el sentido de la tesis de Church–Turing). Luego la cuestión es imposible de resolver.

link:
 Sobre la indecidibilidad del problema del salto de energía