Problemas Que Nenhum Programa Resolve

A computabilidade parte de uma questão fundamental da ciência da computação: quais problemas podem, de fato, ser resolvidos por um algoritmo? O livro mostra como essa pergunta levou matemáticos e pesquisadores a transformar a noção intuitiva de cálculo em modelos formais, permitindo distinguir limitações causadas pela tecnologia de barreiras que pertencem à própria lógica da computação.

A máquina de Turing, a tese de Church-Turing e o problema da parada ajudam a compreender por que existem problemas que nenhum computador consegue resolver de maneira geral, mesmo que imaginemos máquinas com memória e tempo ilimitados. A indecidibilidade é apresentada de forma acessível, sem exigir conhecimentos matemáticos avançados, mostrando suas implicações para programas, sistemas e métodos de verificação.

O livro também aborda outro tipo de limite: problemas que podem ser resolvidos em princípio, mas que exigem uma quantidade de tempo ou recursos tão grande que sua solução se torna impraticável. A partir da distinção entre computabilidade e complexidade computacional, você conhece de maneira intuitiva as classes P e NP e entende por que encontrar uma solução pode ser muito mais difícil do que verificar se uma resposta já encontrada está correta.

Aproximações, algoritmos probabilísticos e heurísticas completam o percurso, mostrando como a computação enfrenta problemas para os quais soluções exatas são difíceis, caras ou inviáveis.