Por ejemplo, el problema de satisfacibilidad booleana puede reducirse al problema de parada transformándolo en la descripción de una máquina de Turing que prueba todos los valores de las variables; cuando encuentra una combinación que satisface la fórmula se detiene y en caso contrario reintenta desde el principio, quedándose en un lazo infinito.