Problema da parada
Origem: Wikipédia, a enciclopédia livre.
Este artigo precisa ser wikificado.
Por favor formate este artigo de acordo com as diretrizes estabelecidas no livro de estilo. Remova este aviso somente depois de todo o texto estar wikificado.
Na teoria da computabilidade o problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma:
- Dado uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou rodará indefinidamente, dada essa entrada.
Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir. Dizemos que o problema da parada é indecidível nas Máquinas de Turing.