O que é o problema da parada?

O problema da parada, ou "halting problem", é um conceito fundamental na teoria da computação. Ele se refere à questão de saber se um programa de computador, dado um conjunto de entradas, irá parar (terminar) ou continuar a executar indefinidamente. Alan Turing provou que não existe um algoritmo geral que possa resolver esse problema para todos os programas e entradas possíveis, ou seja, não é possível determinar, de forma universal, se um programa vai parar ou não. Essa descoberta tem implicações profundas na computação e na lógica.