O Problema da Decisão

Paris, 1900. Diante de uma plateia que reunia a elite intelectual da Europa, David Hilbert (1862 — 1943) traçou um programa para o futuro da matemática. O famoso matemático de Göttingen queria fundamentos inabaláveis. A matemática, pensava, poderia ser erguida como uma catedral lógica: completa, consistente, irrefuável, formalmente segura contra paradoxos.

As 23 “Questões de Hilbert”

No Congresso Internacional de Matemáticos,, como outros tantos eventos culturais realizados em Paris para marcar o novo século, Hilbert apresentou uma lista definitiva de vinte e três problemas matemáticos importantes que ele acreditava que deveriam ser o foco do século XX. Esses problemas, as “Questões de Hilbert”, dominaram a pesquisa matemática por décadas. Embora muitos tenham sido resolvidos, seu objetivo fundamental para a área acabou sendo desafiado. Ainda assim, direcionou esforços de estabelecer os fundamentos lógicos da matemática e forneceu a base matemática para avanços revolucionários na física.

A influência de Hilbert sobre a mecânica quântica foi decisiva. Suas inovações matemáticas forneceram instrumentos fundamentais para a chamada “Era de Ouro da Física”. Em 1925, Werner Heisenberg utilizou uma ideia de Hilbert para desenvolver a mecânica matricial, a primeira base matemática genuína para a estrutura atômica.

O trabalho de Hilbert também auxiliou os físicos na transição entre a tentativa de visualizar o interior do átomo e a medição de suas propriedades por meio de tabelas matemáticas abstratas, isto é, matrizes. Essa mudança alterou profundamente a forma como a física passou a compreender os fenômenos atômicos.

Como professor da Universidade de Göttingen, Hilbert contribuiu para transformar a instituição em um dos três centros seminais da física e da matemática mundial, ao lado de Cambridge e Copenhague. A expansão do conhecimento matemático impulsionada por Hilbert e seus contemporâneos levou, posteriormente, à criação da revista Mathematical Reviews, em 1939, após a interferência do regime nazista nos tradicionais periódicos alemães de resumos acadêmicos.

Três décadas depois, o sonho ganhou uma formulação precisa: o Entscheidungsproblem, o Problema da Decisão. Dada qualquer afirmação matemática escrita numa linguagem formal adequada, existiria um procedimento mecânico (um algoritmo) capaz de determinar, em tempo finito, se ela é verdadeira ou falsa?

Hilbert acreditava que sim. No entanto a resposta foi um revés, ainda que uma das maiores conquistas da história intelectual. Não, tal procedimento não existe. E a prova dessa impossibilidade inaugurou a ciência da computação e redefiniu o que entendemos por conhecimento.

A busca pela certeza mecânica

O programa de Hilbert nasceu de uma crise. Paradoxos na teoria dos conjuntos, como o de Russell, haviam abalado a confiança nos alicerces da matemática. Geometrias não euclidianas mostravam que até as intuições mais básicas podiam falhar. Escolas rivais disputavam o sentido do rigor.

Hilbert propôs uma estratégia ousada. Queria formalizar tudo. A matemática deveria ser tratada como manipulação de símbolos segundo regras explícitas. Depois, seria possível estudar esses próprios sistemas formais de fora, ou seja, uma “metamatemática” finitista, segura, que provaria três coisas sobre o sistema:

• Consistência: nenhuma contradição pode ser derivada.
• Completude: toda verdade matemática pode ser provada.
• Decidibilidade: existe um método geral para decidir a verdade ou falsidade de qualquer enunciado.

Era o espírito mecanicista da modernidade levado ao extremo. O gênio individual poderia, em princípio, ser substituído por um procedimento. A verdade tornar-se-ia questão de cálculo.

Gödel e a fratura interna da lógica

O primeiro grande abalo veio em 1931, com Kurt Gödel (1906–1978). Em vez de atacar diretamente o Problema da Decisão, Gödel mostrou que o próprio ideal de completude era inalcançável.

Seu truque foi transformar afirmações matemáticas em números e, com isso, permitir que a aritmética falasse sobre si mesma. Ele construiu uma proposição que, essencialmente, dizia: “Esta afirmação não é provável neste sistema.”

Se o sistema a provasse, cairia em contradição. Se não a provasse, então a afirmação seria verdadeira, mas indemonstrável. Resultado: em qualquer sistema formal suficientemente potente para conter a aritmética, existem verdades que não podem ser provadas dentro dele.

O segundo teorema foi ainda mais devastador: tal sistema não pode provar sua própria consistência. A segurança absoluta que Hilbert desejava não podia ser estabelecida pelos próprios meios formais que ele confiava.

Gödel não respondeu diretamente ao Entscheidungsproblem. Atacou os alicerces da lógica subjacente a ele. A lógica continha regiões inacessíveis à prova. A ideia de um método universal de decisão começava a parecer improvável.

O que seria, afinal, um “procedimento mecânico”?

Seu trabalho também deu continuidade ao ideal de uma “linguagem universal da lógica”. Essa concepção influenciou pensadores posteriores, como Alan Turing, que desenvolveu os conceitos de Hilbert para definir os limites teóricos da computação e formular a chamada “Máquina de Turing”. Faltava ainda uma definição precisa do que seria esse método mecânico. Três abordagens quase simultâneas convergiram para a mesma noção.

Alonzo Church (1903 —1995) formalizou a ideia de computação por meio do cálculo lambda, um sistema abstrato de manipulação de funções. Church propôs a tese de que toda função efetivamente calculável pode ser expressa nesse formalismo.

Church demonstrou que não existe algoritmo geral, nesse modelo, capaz de decidir a validade de todas as fórmulas da lógica de predicados. O Entscheidungsproblem era insolúvel ali. Mas muitos acharam o formalismo excessivamente etéreo para capturar a intuição de cálculo mecânico.

Alan Turing (1912–1954) ofereceu uma imagem mais concreta. Ele imaginou uma máquina idealizada com:

• uma fita potencialmente infinita, dividida em células;
• um cabeçote que lê e escreve símbolos;
• um conjunto finito de estados internos;
• uma tabela de instruções que dita cada passo.

Turing argumentou que qualquer procedimento que um humano pudesse executar seguindo regras fixas poderia ser simulado por tal máquina. Surgia o modelo que, até hoje, define formalmente o que é computável.

A tese de Church-Turing de que os diferentes modelos capturam a mesma classe de processos efetivos viria a ser o fundamento conceitual da computação. A tese sustenta que toda função computável pode ser executada por uma Máquina de Turing. Um algoritmo consiste em instruções finitas, precisas e executáveis por meios mecânicos, como papel e lápis, sem exigir inteligência além da aplicação das regras. A tese não pode ser provada formalmente, pois a noção intuitiva de algoritmo permanece indefinida. Qualquer programa pode ser traduzido para uma Máquina de Turing e vice-versa.

O problema da parada e o coração da indecidibilidade

O golpe final veio com o chamado Problema da Parada. Dada a descrição de um programa e de sua entrada, existe um algoritmo que possa decidir se esse programa irá terminar ou rodar para sempre?

Turing provou que não. Sua estratégia foi engenhosa: supor que tal algoritmo exista e, a partir dele, construir um programa que produz uma contradição ao ser executado sobre si mesmo. A autorreferência, já explorada por Gödel, reaparece aqui em forma computacional.

Se não podemos decidir nem mesmo se um programa para, não pode haver um procedimento geral para decidir a verdade de todas as afirmações matemáticas formalizadas. O Entscheidungsproblem estava resolvido, só que negativamente.

Limites que criaram um mundo

O resultado foi extraordinariamente fértil. Ao delimitar o que máquinas não podem fazer, Turing definiu com clareza o que elas podem. Sua máquina abstrata tornou-se o modelo do computador digital de programa armazenado.

Ao mesmo tempo, a indecidibilidade introduziu uma nova humildade intelectual. Existem problemas bem formulados, dentro de sistemas rigorosos, que estão além de qualquer método algorítmico universal. A razão formal tem fronteiras.

Isso não encerra a matemática nem a ciência. Pelo contrário, abre um território infinito de investigações locais, métodos parciais, heurísticas, intuições. O ideal de um procedimento único e definitivo cede lugar a uma ecologia de técnicas.

O horizonte do conhecimento

Hilbert estava errado sobre a possibilidade de um método de decisão universal. Mas sua pergunta foi uma das mais fecundas já feitas. Ao tentar mecanizar a verdade matemática, ele forçou a lógica a olhar para si mesma.

Gödel revelou a incompletude interna dos sistemas formais. Church e Turing mostraram que a própria noção de procedimento efetivo tem limites intrínsecos. No ponto onde a matemática encontrou sua fronteira, nasceu a teoria da computação. Consequentemente, nasceu os mundos digital e virtual.

A máquina de Turing universal, percorrendo sua fita sem fim, é o símbolo desse paradoxo: possuímos um modelo extraordinariamente potente de cálculo, capaz de simular qualquer algoritmo concebível. E, no entanto, sabemos que há perguntas que nenhuma máquina, nenhum método mecânico, poderá jamais decidir de modo geral.

É nesse limite que a matemática deixa de ser apenas um sistema de respostas e se torna, também, uma cartografia do que não pode ser resolvido.