Existem problemas que os computadores não conseguem resolver?

Informação, entretenimento, trabalho, educação, soluções rápidas para problemas complexos… em geral, temos uma ideia bem sólida do que queremos ao usar um computador. Na verdade, há momentos em que um sistema parece capaz de resolver tudo, e isso nos leva a um exercício de lógica muito interessante: imagine um computador com tempo, energia e poder de processamento infinitos. Será que existe algo que, apesar dessas vantagens, ele não consiga resolver? A resposta curta é «sim», mas precisamos da ajuda de Tom Scott para o resto…

Quantas vezes isso aconteceu? Uma pergunta simples nos joga em um buraco negro de lógica e razão. O matemático David Hilbert (o mesmo do hotel infinito) ficou preso nessa situação junto com seu colega Wilhelm Ackermann em 1928, quando ambos apresentaram o desafio do Entscheidungsproblem, ou «Problema de Decisão». Em termos bem relaxados, o problema propõe o seguinte: é possível determinar se uma declaração ou sentença dada é demonstrável ou não? Com tempo e energia suficientes, podemos encontrar a resposta para qualquer coisa?

Qual é a relação disso com computadores? Na verdade, essa dúvida de Hilbert pode ser adaptada ao universo da computação de uma forma muito particular: imagine o código de um programa, qualquer programa. É possível analisar esse código e determinar automaticamente se ele vai parar ou entrar em um loop infinito? Nesse ponto, alguém sugere um exemplo como:

10 PRINT "OLÁ MUNDO"
20 GOTO 10
RUN

Obviamente, essa peça de código leva a um loop infinito... mas a diferença é que ela foi projetada desse modo. Determinar se alguns programas param ou continuam para sempre, isso é fácil. A ideia de pegar qualquer código, todos os códigos, e analisá-los para estabelecer definitivamente se terminam ou entram em loop pode parecer simples na superfície, mas é matematicamente impossível. Como sabemos? Graças a um certo cavalheiro chamado Alan Turing, e à famosa Máquina que leva seu sobrenome, de 1936.

É aqui que Tom Scott nos resgata com sua explicação: imaginemos um programa chamado «Halts» que pode ver uma amostra de qualquer código, e determinar se ele vai parar (não precisamos saber como ele faz isso, o importante é que funciona). Mais uma vez: «Halts» vê o código e responde «sim» (para) ou «não» (loop infinito). Agora, imaginemos um segundo programa conectado a «Halts», que faz exatamente o oposto da resposta dele. Ou seja, se «Halts» disse que o código para, o segundo programa entra em loop infinito, e se disse que entra em loop, ele para.

Esse sistema é chamado «Oposto», porque em essência faz o contrário do que você insere nele... mas é aqui que Turing quebra tudo com sua proposta: pegar o código completo que compõe «Oposto» e fazer com que ele analise a si mesmo. O resultado é que não há resultado. É um paradoxo, uma impossibilidade matemática. Mesmo com as condições iniciais ideais, uma mínima variação colapsa o processo. E aí está nossa resposta à pergunta original: existe pelo menos uma coisa que os computadores não podem nem poderão resolver.