A importância histórica do problema da parada reside no fato de que foi um dos primeiros problemas a serem provados indecidíveis descobertos, definindo se, a partir da entrada informada, o programa terminaria ou rodaria infinitamente. Considere as seguintes afirmações e classifique-as como verdadeiras (V) ou falsas (F):

• ( ) Uma consequência da indecidibilidade do problema da parada é que é impossível ter um algoritmo geral para determinar se determinada frase está certa ou errada.
• ( ) Se a máquina de Turing não puder resolver o problema de parada, nenhum outro sistema de algoritmo será capaz de definir uma solução para o mesmo problema.
• ( ) O problema de parada é decidível, uma vez que a máquina de Turing sempre permite que ele tenha um fim e não se torne infinito por falta de uma solução para qualquer problema.
• ( ) A redução (o princípio da redução) é uma técnica que transforma um problema em outro, diminuindo sua complexidade. Contudo, ainda não é aplicável para interromper problemas.
• ( ) O problema da parada é um problema de decisão sobre os atributos de um programa de computador, como o fato de todos os programas que podem ser escritos em uma linguagem de programação geral serem equivalentes a máquinas de Turing.