Exibir código-fonte para O problema da parada

= Problema da Parada =
<br>

* O Problema da Parada (Halting Problem) é uma das descobertas mais importantes da Ciência da Computação. Ele prova que existem limites para o que a tecnologia pode resolver.

* Em termos simples: é impossível criar um programa de computador que consiga analisar qualquer outro programa e dizer, com 100% de certeza, se esse programa um dia vai terminar de rodar (parar) ou se vai ficar travado em um loop infinito para sempre.
<br>

* Questões envolvidas:
** Limites da Tecnologia: Existem problemas que o computador simplesmente não consegue resolver, não importa o quão rápido ele seja.
** Segurança e Compiladores: É por isso que antivírus e compiladores às vezes não conseguem prever todos os comportamentos de um vírus ou software complexo.
** Decidibilidade: Introduza o termo: o Problema da Parada é indecidível
*** O que é isso? Decidibilidade é a capacidade de um problema ser resolvido por um algoritmo (um conjunto de passos lógicos) que sempre chega a uma resposta (Sim ou Não) em um tempo finito.
*** Se um problema é decidível, significa que você pode escrever um código que nunca ficará "pensando" para sempre; ele eventualmente lhe dará uma solução correta para qualquer entrada que você fornecer.
<br>

= Motivação =
<br>

* Por que os iniciantes devem conhecer esses problemas?
*** A lição fundamental aqui é a Modéstia Algorítmica. Quando um programador entende a decidibilidade, ele para de tentar o impossível e foca no que é viável:
*** Heurísticas: Em vez de uma resposta 100% certa, buscamos uma que funcione em 99% dos casos.
*** Restrições: Em vez de tentar resolver o problema para "qualquer programa", resolvemos apenas para programas que seguem certas regras rígidas.
*** Timeouts: Se o algoritmo demora demais para decidir, nós o interrompemos (aceitando que não saberemos a resposta).
<br>

= Máquina de Turing =
<br>

= Problemas decidíveis e indecidíveis =
<br>