Vamos con un poco de teoría de la computación ¿Qué es el problema de paro, de parada o de Halting? Consiste en determinar si existe una máquina de Turing capaz de determinar si cualquier Máquina de Turing se va a detener o no. Dada una máquina de Turing M y una palabra w se determinará si M acabará en un número finito de pasos usando w como dato de entrada.

El problema es indecidible, según el propio Turing ninguna máquina de Turing puede resolverlo. Es decir, no puede existir un programa genérico que demuestre que todos los programas del mundo terminan, se puede hacer para un programa concreto pero no existe la solución general.

Existen varias demostraciones de por qué es indecidible, vamos a ver una demostración escrita en javascript.

Imaginemos que alguien escribe una función f que recibe como parámetros una función y sus argumentos, y que tiene un código capaz de comprobar si esta se detendrá o no.

var f = function (funcion, argumentos) { ... }; // Aquí iría un código correcto que supuestamente calcularía si la máquina para o no

Vamos a suponer que esa función está correcta, funciona y nos devuelve true si el programa termina, y false si caería en un bucle infinito. Entonces podríamos usarla como subrutina dentro de otra función más grande llamada g como la que viene a continuación:

var g = function (funcion) {
//Pasamos en el parámetro funcion la función y sus argumentos 
  if (f(funcion,funcion)) {
    while (true); //esto provoca un bucle infinito
  }
  else {
    return false;
  }
}

Esto vendría a decir que g(funcion) termina siempre y cuando funcion(funcion) nunca termina.

Entonces ¿qué ocurre si la pasásemos a la función g como parámetro su propio código? Es decir ¿qué pasa si g evalúa a g? Pues que llegamos a una contradicción: g(g) termina siempre y cuando g(g) nunca termina. Por tanto, al llevarnos a una paradoja dicho algoritmo no puede existir.