A busca pela linguagem perfeita

por Gregory J. Chaitin

Um artigo de lógica matemática na Dicta? Não é uma revista que promete ser de cultura geral, quando este texto cheio de fórmulas é claramente especializado demais?

Bem, talvez este artigo exija um pouco de atenção e paciência por parte do leitor não especializado, mas o fato é que trata de um tema extremamente fascinante, mais ainda, indispensável para a teoria do conhecimento em geral: os limites intrínsecos da razão e a possibilidade de superá-los, ou ao menos de contorná-los. Quem não tiver nenhum estômago para as matemáticas, pode pular as fórmulas e ater-se ao texto, que no caso do autor é extremamente direto e vivo, e dá a informação indispensável.

O Dr. Gregory Chaitin leva-nos por um rápido percurso através da história do pensamento a partir de Raimundo Lúlio, expondo o ideal medieval de encontrar uma linguagem perfeita que permitisse ter a chave do conhecimento universal, de Deus e do mundo. Com Leibniz, vemos como esse ideal passa para as ciências, notadamente a matemática; Hilbert volta a formulá-lo com o empenho por encontrar uma linguagem que fornecesse todas as verdades matemáticas; no entanto, essa tentativa fracassou, como foi mostrado por Gödel, por Turing e pela “probabilidade de parada” Ω. Ao invés de encontrar a Teoria Unificada, encontramos a incompletude, a incomputabilidade e a aleatoriedade algorítmica.

Se esse parece ser o lado sombrio da busca, é fascinante do ponto de vista epistemológico: descobrimos os limites para o que pode ser conhecido, para a razão. Mas se é impossível encontrar línguas perfeitas para o raciocínio, por outro lado é possível encontrá-las no âmbito da computação. São as linguagens de programação, que nos permitiram criar um “Golem”, uma máquina que é uma espécie de “mini-Adão”, incapaz de raciocinar mas não de calcular: o nosso vulgar computador…

Também isso abre perspectivas interessantíssimas para a epistemologia: se sempre e em tudo é impossível conhecer cada caso concreto, todos os fatores envolvidos em um raciocínio (a razão é intrinsecamente limitada), mesmo assim é possível funcionar tomar decisões com a “visão de conjunto” que ela nos proporciona. Como fizemos desde Adão… mas sem saber o que fazíamos.

Julguei interessante apresentar aqui, no Perimeter Institute, uma versão da palestra que dei há um ano em Jerusalém [1]. A minha intenção é traçar um esboço geral da história da lógica matemática de acordo com minha visão pessoal da história das idéias. Sou um matemático que gosta de físicos – alguns não gostam – e que desejaria ser um físico teórico; ao menos, a certa altura da minha carreira desejei ser físico.

Portanto, falaremos das matemáticas, e dentro desse tema gostaria de traçar-lhes um quadro amplo – embora com toda a certeza não o quadro-padrão – de uma parte da história intelectual. Será uma palestra sobre a história do trabalho feito acerca dos fundamentos da matemática, procurando enfocar essas questões, ao menos em parte, a partir da perspectiva que se daria a elas na Idade Média.

Umberto Eco e a busca

Há um ótimo livro de Umberto Eco chamado The Search for the Perfect Language, “A busca pela língua perfeita” [2], que recomendo vivamente, no qual fica clara a predileção do autor pela Idade Média – a ponto de parecer que ele gostaria que ainda estivéssemos nela. O assunto da obra é um sonho (traduzido no seu título) que o autor julga ter desempenhado um papel fundamental na história intelectual da Europa.

Que espécie de busca é essa? Os físicos atuais a entenderiam como uma busca pela Teoria Unificada; mas, nos termos em que a expressão foi formulada originalmente, consistia na idéia de encontrar, por assim dizer, a língua da Criação, a língua anterior à Torre de Babel, a língua que Deus usou ao criar o Universo, a língua cuja estrutura exprimiria diretamente a estrutura do mundo, a língua na qual os conceitos seriam expressos no seu formato direto, original. Como vêem, esta idéia é ao menos um pouco semelhante à tentativa de encontrar, através das ciências físicas, uma Teoria Unificada fundante.

O que subjaz a isso é a noção de que conhecê-la seria como ter acesso à chave do conhecimento universal. Em termos teológicos, ela nos aproximaria imensamente do pensamento divino – o que é, no mínimo, perigoso. Em termos mágicos, ela daria acesso a enormes poderes. Em termos lingüísticos, estaríamos diante da língua na sua forma pura, não corrompida – a língua da qual todas as outras descendem. E poderíamos continuar indefinidamente…

Pois então: o livro de Eco é justamente sobre a procura por essa língua, que nos revelaria o conhecimento absoluto, Deus e a realidade última da natureza [3]. Em suma, … tudo.

Leibniz: characteristica universalis, calculus ratiocinator

Essa história intelectual está repleta de capítulos interessantes. Um deles é sobre Raimundo Lúlio ou Ramón Llul, um catalão que viveu no séc. XIII. Este cavalheiro procurou combinar mecanicamente todos os conceitos possíveis a fim de chegar a novos conhecimentos. Teríamos duas rodas, cada uma com alguns conceitos escritos sobre ela; a rotação das duas permitiria obter todas as combinações possíveis, o que constituiria uma maneira sistemática de se chegar a novos conceitos e novas verdades. Se nos lembrarmos das Viagens de Gulliver, livro que definitivamente não foi escrito para crianças, é de uma idéia semelhante que Swift faz troça em um dos seus capítulos.

Deixemos agora Lúlio de lado e nos ocupemos de Leibniz, ao qual Eco dedicou um capítulo inteiro. Trata-se de uma figura de transição maravilhosa em busca dessa linguagem. Maravilhosa porque universal: Leibniz sabia tudo sobre a Cabala judaica e cristã, sobre todo tipo de esoterismo e hermetismo, incluindo a alquimia – chegou a escrever, como ghost-writer, um livro sobre este assunto. Além disso, conhecia bem a filosofia antiga, a escolástica e aquilo a que então se chamava filosofia mecânica, que foi o começo da ciência moderna, tendo logrado aproveitar o lado bom de tudo isso.

A sua versão da busca em questão está ancorada numa louca mistura de mística, magia e teologia, e até hoje é atual, adequada aos ouvidos modernos (mesmo nos meios científicos contemporâneos). Essa linguagem foi chamada por Leibniz characteristica universalis, e deveria ser acompanhada por um crucial calculus ratiocinator.

Seu objetivo era reduzir o raciocínio ao cálculo, à computação, partindo da certeza de afirmações como 2 + 5 = 7. Leibniz ilustra isso recorrendo à idéia de que, numa disputa intelectual, ao invés de recorrerem a um duelo, bastaria que os adversários se sentassem e dissessem: “Senhores, vamos calcular!”; assim chegariam à resposta correta.

Mas até onde levou essa sua busca pela linguagem perfeita? Leibniz era do tipo que se entediava facilmente. Borboleteava de um assunto para outro propondo idéias fundamentais, mas raramente se dava ao trabalho de as desenvolver até o final. Uma das poucas coisas que levou até o final foi justamente uma parte da characteristica universalis chamada cálculo, que difere da versão de Newton precisamente por fazer parte de um projeto maior.

Leibniz aprendeu matemática quando já estava na casa dos vinte anos, uma idade relativamente avançada para a média dos matemáticos, que costumam começar muito cedo. O seu professor em Paris foi Christian Huygens, que por sinal viria a execrar o cálculo de Leibniz por considerá-lo demasiado mecânico e irracional: qualquer cretino poderia calcular uma resposta apenas seguindo regras, sem entender o que fazia.

Huygens preferia as antigas provas geométricas, nas quais era necessário ser criativo e apresentar no fim um diagrama e as razões particulares que comprovassem a sua verdade. Leibniz, por sua vez, buscava um método geral que permitisse determinar mecanicamente o que estava acontecendo. Para isso, uma notação correta era muito importante; a verdade absoluta poderia ser encontrada sem recurso à criatividade. Penso que não é uma má idéia, e demonstra a importância de Leibniz.

Cantor e os Conjuntos Infinitos

Daí passamos a Georg Cantor. A sua teoria, de fins do século XIX, é interessante porque reflete fielmente a Idade Média, embora seja de certo modo uma inspiração para toda a matemática do século XX.

A teoria dos conjuntos infinitos era pura teologia, teologia matemática. Normalmente é melhor não mencionar esse fato. Para que algo entre para o campo da matemática, o preço a pagar é jogar fora toda a filosofia e ficar apenas com algo técnico. Por isso, a teologia foi jogada fora mais tarde.

Mas o objetivo de Cantor era entender Deus – o Deus transcendente. A teoria dos conjuntos infinitos [4] tem essa hierarquia de infinitos cada vez maiores, os alephs (ℵs). Temos os ℵ0, ℵ1, o conjunto infinito dos números inteiros, o conjunto infinito dos números reais e por aí vai. Cada um deles é o conjunto de todos os sub-conjuntos do conjunto anterior. Daí para a frente, a coisa começa a ficar confusa, com infinitos do tipo de ℵω ; esse é o primeiro infinito depois de

0, 1, 2, 3, 4

Mas podemos continuar:

ω + 1, ω + 2, ω + 3 … 2ω + 1, 2ω + 2, 2ω + 3

Esses são os famosos números ordinais, que são os subscritos dos ℵs, os quais são por sua vez as respectivas cardinalidades. E a coisa continua:

ω2, ωω, ωωω

Até chegar ao número ordinal chamado épsilon-zero:

ε0 = ωωωω…

Que é a menor solução para a equação:

x = ωx.

E o cardinal correspondente, ℵε0, é bem grande!

Mas, sabe como é, Deus está bem longe – afinal Ele é infinito e transcendente. Podemos tentar ir em sua direção, mas nunca chegaremos lá porque depois de cada cardinal há sempre um maior: a cardinalidade do conjunto de todos os sub-conjuntos. Depois de toda seqüência infinita de cardinais que determinarmos, basta tomar a união de todas as seqüências e teremos um cardinal que é maior do que qualquer um que estava na seqüência anterior. A coisa toda não tem fim e ainda por cima é contraditória.

Esse é o problema. Tudo isso é absolutamente maravilhoso, uma coisa de tirar o fôlego – você precisaria fumar erva ou tomar um vinho para apreciá-la completamente. O único problema com esse raciocínio é que ele leva à contradição.

Trata-se de algo simples. Se tomamos o conjunto universal, o conjunto de tudo, e considerarmos o conjunto de todos os seus subconjuntos, pelo argumento da diagonal de Cantor, ele deveria ter uma cardinalidade maior; mas como é possível propor alguma coisa que seja maior que o conjunto de tudo?

Esse é o paradoxo que Bertrand Russell descobriu; ele olhou para tudo isso e se perguntou por que chegávamos a tão mau resultado. E se observamos a prova do argumento da diagonal de Cantor, de acordo com o qual o conjunto precisa ser maior que o todo, perceberemos que tudo isso envolve o conjunto de todos os conjuntos que não são membros de si mesmos [5],

{ x : x x },

o qual não pode conter a si mesmo e também não pode não conter a si mesmo. Esse é o chamado paradoxo de Russell.

Cantor tinha consciência disso, mas não estava preocupado com essas contradições. Nós somos finitos, mas Deus é infinito; portanto, naturalmente é paradoxal um ser finito tentar compreender um ser infinito, transcendente. Os paradoxos são inevitáveis. Mas é evidente que a comunidade matemática não está muito contente com uma teoria que leva a contradições.

No entanto, essas idéias são tão maravilhosas, que levaram a comunidade matemática a esquecer a teologia e a filosofia, varrendo as contradições para debaixo do tapete. A versão expurgada disso tudo é a chamada teoria dos conjuntos de Zermelo-Fraenkel, com o axioma da escolha – ou, usualmente, ZFC (o inglês para Zermelo-Fraenkel Choice). Trata-se de uma teoria formal axiomática desenvolvida com lógica de primeira ordem, constituindo uma versão expurgada da teoria de Cantor que, acredita-se, está isenta de paradoxos.

Bertrand Russell: a matemática é cheia de contradições

De todo modo, Bertrand Russell inspirou-se na teoria dos conjuntos inicial para propor uma tentativa de crítica geral do raciocínio matemático, encontrando assim várias contradições e argumentos que levavam a contradições.

Russell era um ateu em busca do absoluto, e que portanto acreditava na verdade absoluta. Ele amava a matemática e queria que ela fosse perfeita; por isso tomou a iniciativa de divulgar essas contradições a fim de promover a sua resolução.

Além do paradoxo de que não há o maior cardinal de todos, e de que o conjunto de todos os subconjutos do todo é maior que o próprio todo, existe também um problema com os números ordinais, o chamado paradoxo de Burali-Forti: o conjunto de todos os ordinais é um ordinal maior que todos os ordinais. Isso acontece porque cada ordinal pode ser definido como o conjunto de todos os ordinais que são menores que ele (e, portanto, um ordinal é menor que outro se, e somente se, estiver contido nele).

Enquanto Russell espalhava a idéia de que a razão leva a contradições, David Hilbert propôs um plano para estabelecer um fundamento seguro para a matemática. Basicamente, o que Hilbert propôs foi uma teoria axiomática completamente formal – uma versão moderna da characteristica universalis e do calculus ratiocinator de Leibniz!

David Hilbert: a matemática é uma teoria formal axiomática

A idéia de Hilbert é tornar a matemática algo totalmente objetivo, despojado de elementos subjetivos.

Nessa teoria formal axiomática haveria um número finito de axiomas. Estes não seriam escritos numa língua natural ambígua, mas numa linguagem artificial com uma gramática simples e precisa. Não há espaço para raciocínios informais: tudo é feito a partir da lógica matemática e as regras do jogo são especificadas de maneira totalmente precisa.

Hilbert era um conservador. Ele acreditava que a matemática tem acesso à verdade absoluta, o que é uma noção mais ou menos medieval. Dá para sentir o cheiro da Idade Média toda vez que se menciona “verdade absoluta”. No entanto, a matemática moderna continua enamorada dela. Como disse Gödel, nós matemáticos puros somos o último refúgio da Idade Média. Nós ainda acreditamos no mundo das idéias de Platão, pelos menos nas idéias matemáticas, enquanto todo mundo, inclusive os filósofos, riem dessa noção. Mas os matemáticos puros vivem no mundo platônico das idéias mesmo que todo o mundo já tenha se esquecido disso há muito tempo.

Pois bem: a matemática nos dá a verdade absoluta, disse Hilbert; todo matemático, lá no fundo, acredita nisso. Portanto, deve existir um conjunto finito de axiomas, bem como um conjunto preciso de regras de dedução, de maneira que toda verdade matemática seja uma conseqüência desses axiomas. Veja só: se a verdade matemática é assim, preto no branco, puramente objetiva, e se conseguimos estabelecer um conjunto finito de axiomas aceitos por todos, basta depois seguirmos os passos de cada prova, usando cuidadosamente uma linguagem artificial, livre de ambigüidades, para deste modo sermos capazes de deduzir todas as verdades da matemática. É propriamente essa a noção de que a matemática nos dá certezas absolutas – e Hilbert analisou o que isso significa.

Uma conseqüência importante dessa idéia nos leva de volta à Idade Média e à busca pela linguagem perfeita, que era o que Hilbert procurava. Teríamos a chave desse conhecimento absoluto se pudéssemos deduzir todos os teoremas dos axiomas apenas percorrendo a árvore de todas as provas possíveis. Começa-se pelos axiomas, aplicam-se as regras de inferência uma vez e têm-se todos os teoremas com provas de apenas um passo; então aplica-se novamente as regras de inferência e tem-se todos os teoremas com provas em dois passos; e assim, de maneira totalmente mecânica, começamos a ter todas as verdades da matemática, passando sistematicamente por todas as provas possíveis.

Hilbert não queria transformar a matemática em algo trivial. Além do mais, na prática esse processo tomaria uma absurda quantidade de tempo para chegar a resultados relevantes, e todos os teoremas interessantes perder-se-iam em meio aos desinteressantes, como o fato de que 1 + 1 = 2 e outras trivialidades do gênero.

Seria muito difícil separar o joio do trigo; mas o que realmente importa nessa tentativa é que, em princípio, poderíamos obter todas as verdades da matemática por esse método. Ninguém faria isso na prática, mas a teoria já teria mostrado que a matemática chega a verdades absolutas.

Uma das coisas mais importantes era fazer com que todos os matemáticos concordassem na escolha dessa teoria formal axiomática. Para isso, foi necessário que se usasse a metamatemática a fim de convencer a todos de que essa teoria formal axiomática não teria contradições e evitaria todos os paradoxos que tinham sido apontados por Bertrand Russell. A metamatemática estuda essas teorias formais axiomáticas de um ponto de vista exterior à matemática, com a finalidade de atingir a referida verdade absoluta, e isso através da noção de linguagem perfeita.

Mas o que aconteceu com a proposta de Hilbert? Bem, há boas e más notícias. A parte da boa, já a mencionei: o mais perto que se chegou ao que Hilbert propôs é a teoria dos conjuntos de Zermelo-Fraenkel, uma bela teoria axiomática. Indicarei alguns dos marcos do seu desenvolvimento.

Um dos passos dessa estrada são os números inteiros de Von Neumann. Spinoza tinha um sistema filosófico no qual o mundo era construído a partir de apenas uma substância, que era Deus. A teoria dos conjuntos de Zermelo-Fraenkel é semelhante: tudo são conjuntos, e todo conjunto é construído a partir do conjunto vazio.

Von Neumann parte de uma idéia parecida: o zero, que seria o conjunto vazio, é o primeiro número inteiro de Von Neumann e, generalizando-se, n + 1 é definido como o conjunto de todos os inteiros menores ou iguais a n:

Números de Von Neumann: 0 = { }, n + 1 = {0, 1, 2, …, n}.

Sendo assim, se removermos todas as abreviações, poderíamos escrever todos os números apenas com sinais de chaves (“{“ e ”}”); teríamos a formação do conjunto começando sem nenhum conteúdo e a notação completa até n crescendo exponencialmente em relação a n, porque tudo o que foi escrito para se chegar a um número deverá ser repetido no próximo. Mesmo assim, esse é um belo esquema conceitual.

Prosseguindo nessa teoria, é possível definir os números racionais como pares de números inteiros, e os números reais como o limite de seqüências de racionais, e disso tiramos toda a matemática (toda teoria dos números) começando apenas com o conjunto vazio. Trata-se de um adorável exemplo de ontologia matemática: toda criação construída a partir do conjunto vazio.

As outras duas pessoas que trabalharam com essa proposta de Hilbert foram, obviamente, Zermelo e Fraenkel – afinal, ela é chamada de teoria dos conjuntos de Zermelo-Fraenkel. Uma noção aproximada do que eles fizeram é a de uma tentativa de evitar os conjuntos muito grandes. O conjunto universal é muito grande, e acaba por trazer problemas (pois nem toda propriedade poderia determinar um conjunto). O resultado disso foi uma teoria formal que a maioria dos matemáticos acredita ser capaz de compreender todos os argumentos que normalmente aparecem na matemática – talvez se não incluirmos a teoria das categorias, que é, segundo penso, muito difícil de formalizar e ainda mais paradoxal do que a teoria dos conjuntos.

Gödel, 1931: incompletude

Mas há também as más notícias sobre o resultado da proposta de Hilbert. Vocês provavelmente já ouviram falar de Gödel e Turing; eles mostraram que não era possível encontrar a língua perfeita para matemática, ou seja, que não era possível estabelecer uma teoria formal axiomática para toda a matemática, tal como Hilbert queria. Em outras palavras, esse sistema sempre seria incompleto, deixando de fora algumas verdades.

É exatamente isso o que demonstra o teorema da incompletude de 1931. A prova original de Gödel é bastante estranha, mas poderíamos dizer que é basicamente o “paradoxo da afirmação falsa”:

“Esta afirmação é falsa!”

Uma assertiva como essa não tem pé nem cabeça porque não pode ser nem verdadeira, nem falsa. Se for falso que a afirmação é falsa, então segue-se que ela é verdadeira; se for por sua vez verdadeiro que ela é falsa, então ela será falsa. O que Gödel faz é usar o mesmo princípio com outro enunciado:

“Esta afirmação não pode ser provada!”

Da mesma forma, se a afirmação diz que não pode ser provada, temos duas possibilidades: ou ela pode ser provada, ou não pode ser provada. Se ela pode ser provada, estamos provando algo falso (já que a afirmação diz o contrário); portanto, essa possibilidade deve ser eliminada por hipótese – porque se provarmos algo falso, teremos uma teoria axiomática sem interesse, que prova coisas falsas.

Assim, a única possibilidade é que o enunciado não pode ser provado. Mas, se ele não pode ser provado, é verdadeiro. Então caímos num buraco: não reunimos todas as verdades matemáticas em nossa teoria, e portanto sempre haverá algo que não pode ser provado e a teoria nunca será completa.

Essa prova da incompletude choca muitas pessoas; a minha reação pessoal a ela é: “Ok, está correto. Mas não gosto nada disto”.

Turing, 1936: incomputabilidade incompletude

Uma prova mais profunda da incompletude é a de Turing, em 1936. Ele chega a esse mesmo resultado partindo de um fenômeno mais fundamental, o da incomputabilidade. Trata-se da descoberta de que a matemática está cheia de coisas que são definidas mas que não podem ser calculadas em razão da ausência de um algoritmo.

Em particular, a incomputabilidade que Turing descobriu foi o problema da parada. É uma questão muito simples: um programa de computador que contenha a si mesmo pára em algum momento ou continua rodando para sempre? Não há um algoritmo que responda a essa questão em todos os casos individuais, e portanto não pode haver uma teoria formal axiomática que sempre permita provar, nos casos individuais, qual seria a resposta.

Por que não? Porque, se existisse uma teoria formal axiomática completa para o problema da parada, existiria um procedimento mecânico de decisão que poderia percorrer as possíveis provas até fornecer a solução para a parada de cada caso individual, ou então provar que o programa não pára. Mas esse não pode ser o caso porque essa não é uma função computável.

Como já dissemos, o insight de Turing em 1936 foi que a incompletude, que Gödel havia descoberto em 1931 para toda teoria formal axiomática, provinha de um fenômeno mais profundo, a incomputabilidade. A incompletude seria um corolário imediato da incomputabilidade, este último um conceito que não aparece no artigo de Gödel em 1931.

O artigo de Turing tem um lado ruim – aquele que acabei de mencionar –, mas também tem um lado bom. Ele chega à incompletude, mas também descobre um certo tipo de completude. Ele chega, em suma, à língua perfeita.

Como Gödel mostrou em 1931 e Turing novamente em 1936, não existe uma língua perfeita para o raciocínio matemático. Mas Turing também mostrou, no mesmo ano, que existem línguas perfeitas, não para o raciocínio matemático, mas para a computação, para a especificação de algoritmos. O que ele descobriu foi um tipo de completude chamada universalidade, segundo a qual existem máquinas de Turing universais, ou uma linguagem universal de programação através da qual todo o algoritmo possível pode ser escrito.

Portanto, embora não exista uma língua universal para o raciocínio matemático, existe sim uma linguagem perfeita para computação, para a escrita de algoritmos – esse é o lado positivo, no sentido da completude, do artigo de Turing de 1936.

Teoria Algorítmica da Informação (TAI): Aleatoriedade algorítmica, irredutibilidade algorítmica

Eu passei a maior parte da minha vida profissional estudando um assunto a que chamo teoria algorítmica da informação. Essa teoria parte da incomputabilidade para chegar à incompletude, considerando uma forma extrema de incomputabilidade chamada aleatoriedade algorítmica ou irredutibilidade algorítmica.

Aí está a linguagem perfeita mais uma vez. Ela não está isenta, contudo, de um lado negativo: a probabilidade de parada Ω, cujos bits parecem fatos matemáticos acidentais e no entanto constituem verdades matemáticas irredutíveis. Eles parecem contingentes, acidentais:

Ω = .010010111

Trata-se de uma questão de matemática pura muito bem definida, que é a de saber os bits do valor numérico da probabilidade de parada. No mundo da matemática todas as verdades são necessárias, mas estas parecem verdades contingentes, acidentais. Elas parecem aleatórias; é uma complexidade irredutível.

Esse é o caso máximo de incomputabilidade, um lugar na matemática pura onde não há absolutamente estrutura nenhuma, embora em alguns casos se possa conhecer alguns desses bits.

Existe na verdade um número infinito de probabilidades de parada, dependendo da escolha da linguagem de programação. Depois de escolher a linguagem, pergunta-se qual a probabilidade de um programa gerado aleatoriamente – na base do “cara ou coroa”, digamos – vir a parar. E aí temos uma probabilidade de parada distinta. O valor numérico será diferente; as propriedades paradoxais, as mesmas.

É verdade que existem casos para os quais podemos conhecer alguns dos primeiros bits. Por exemplo, se Ω começar com 1s em base binária ou 9s em base decimal, é possível conhecer esses bits ou dígitos:

se Ω = .11111… (base dois) ou
se
Ω = .99999… (base dez).

Talvez possamos conhecer um número finito de bits do valor numérico de Ω, mas se a teoria formal axiomática tiver N bits, nunca conheceremos mais do que N bits de Ω. Esse é mais ou menos o resultado geral da teoria: a irredutibilidade lógica e computacional, que é, como dito, uma informação matemática irredutível. Estamos diante de uma simulação perfeita de verdades contingentes, acidentais e entrópicas num campo que normalmente lida apenas com verdades necessárias.

Pois bem, essas são as más notícias sobre a TAI. Mas, assim como ocorreu com o trabalho de Turing de 1936, há também um boas notícias. Por um lado temos a máxima incomputabilidade, máxima entropia, ausência total de estrutura, ausência total de redundância em qualquer sentido que diga respeito à teoria da informação; por outro lado, mas temos também a possibilidade de chegar a linguagens com uma expressividade máxima.

Quando a TAI examina a complexidade dos programas – teoria na qual a probabilidade Ω aparece como a jóia da coroa –, toma emprestado das línguas universais de Turing a noção de máxima expressividade em linguagens de programação. Elas são os elementos mais interessantes para o desenvolvimento da teoria que chega a Ω.

Quando temos uma linguagem de programação de máxima expressividade, conseguimos desenvolver programas que são maximamente compactos, ou seja, lidamos com uma noção de complexidade bastante básica, que é a do “menor programa necessário para calcular algo”.

H(x) é o tamanho em bits do menor programa necessário para calcular x.

E assim chegamos a uma melhor noção de perfeição: verificamos que as “línguas perfeitas” que Turing descobriu não são todas igualmente boas, e com a TAI nos concentramos num subconjunto delas formado pelas linguagens que permitem escrever os programas mais concisos. Essas são as linguagens mais expressivas, aquelas que permitem criar programas menores.

As decisões de Deus

Essa definição de complexidade é uma maneira seca, técnica, de expressar essa idéia em termos modernos. A terminologia medieval é muito mais rica. A noção de “complexidade de tamanho do programa” (program-size complexity) – que na verdade tem vários nomes diferentes (complexidade algorítmica, complexidade de Kolmogorov) – em termos medievais seria o equivalente da pergunta quantas decisões sim/não Deus precisou tomar para criar algo?, que é na verdade uma questão bastante básica se considerarmos que Deus está calculando o Universo. Essa é uma perspectiva medieval dos desenvolvimentos modernos. A teologia era, se é que podemos falar assim, a “física teórica” da Idade Média.

A noção de máquina de Turing usada na TAI é a idéia mais básica de uma máquina flexível, de um hardware flexível – que hoje chamamos de software. De certo modo, em 1936 Turing criou a indústria e a tecnologia de computadores. E isso foi um tremendo benefício para um artigo que, em termos matemáticos, parecia inicialmente bastante negativo por falar de coisas que não poderiam ser calculadas ou provadas. Mesmo assim, havia também a vantagem de que as linguagens de programação poderiam ser completas apesar de não existirem teorias formais axiomáticas completas.

Foi John von Neumann quem primeiro apontou, a partir do artigo de Turing, para essa noção de software. E foi assim que tive contato com o assunto pela primeira vez quando era estudante, lendo um ensaio de Von Neumann.

Mas no contexto da TAI, quando falamos sobre o programa mais expressivo, estamos interessados numa classe particular de máquinas de Turing universais (U). O fato essencial, em linguagem matemática, é:

U(πC p) = C(p).

Na qual C é um computador arbitrário, em outras palavras qualquer linguagem de programação C; p é um programa rodado nesse computador C; porquanto a função C(p) significa o resultado de colocar o programa p no computador C. E o que são exatamente esses computadores U usados para definir a complexidade de tamanho do programa e para falar sobre Ω? Um computador universal U tem a propriedade pela qual, para qualquer outro computador C com um programa p, o mesmo resultado será calculado (pelo computador U) se você der o programa original p para C concatenado com o prefixo πC – que depende apenas do computador C que você quer simular. Ou seja, πC diz a U qual computador simular.

Em outras palavras, πC p é a concatenação de duas informações, constituindo uma seqüência binária. Com o programa original p em mãos, que também é uma seqüência binária, a única coisa necessária a fazer é colocar à sua frente um prefixo determinado, o qual dirá qual computador deve ser simulado. Isso significa que esses programas πC p para U são apenas um número fixo de bits maior que o programa p para qualquer máquina individual C.

Este U é a máquina universal de Turing usada na TAI. Essas são as linguagens com poder expressivo máximo e, portanto, aquelas nas quais os programas são mais concisos. É deste modo que se define a complexidade de tamanho do programa; numa analogia, “Deus” naturalmente irá usar a mais perfeita das linguagens de programação quando estiver criando o mundo.

Duas versões da TAI

Devo notar que o conceito original de universalidade de Turing não lidava com o número de bits; ele realmente não se preocupava com o tamanho dos programas. Tudo o que as máquinas universais U tinham de fazer era serem capazes de simular qualquer outra máquina C. Não havia, contudo, a preocupação de se estudar o tamanho do programa para U como uma função do tamanho do programa para C. A TAI, por sua vez, preocupa-se com maneiras particularmente eficientes de tornar U universal (porque a noção de universalidade de Turing não exigia tanto); aqui preocupamo-nos apenas com não desperdiçar bits.

Mas o fato de que basta adicionar um número fixo de bits num programa para C e determinar um programa para U não é completamente trivial. Quando se concatena a seqüência de bits πC com p, obtendo-se uma nova seqüência de bits, é necessário de alguma maneira indicar onde o prefixo πC termina e onde o programa p começa. Existem várias maneiras de fazê-lo.

Um jeito muito simples de tornar o prefixo πC auto-delimitante é ter uma seqüência de 0s seguida por um 1:

πC = 0k 1.

O número k de 0s diz qual máquina C deve ser simulada. Mas essa é uma maneira muito dispendiosa de proceder.

O prefixo πC é na verdade um intérprete para a linguagem de programação C. As linguagens universais U na TAI permitem que se forneça a U um intérprete, e mais o programa p nessa outra linguagem C; assim, U rodará o intérprete para ver o que p faz. Se pensarmos em πC como sendo uma seqüência arbitrária de bits, uma maneira de torná-la auto-delimitante é apenas dobrar todos os bits. Cada 0 transforma-se em 00, cada 1 transforma-se em 11; então se coloca um par de bits desiguais como sinal de pontuação no final:

πC arbitrário: 0 00, 1 11, 01 no final.

Essa é uma maneira otimizada de fazer com que o prefixo concatenado com a informação binária p seja auto-delimitado; ela apenas dobra o tamanho, enquanto a sugestão anterior (0k 1) aumentava o tamanho exponencialmente em k.

Existem ainda maneiras muito mais eficientes de fazer isso. Essencialmente, é necessário em geral adicionar um termo logarítmico ao prefixo arbitrário πC indicando o tamanho de πC em bits. É mais ou menos como acontece com as bonecas russas, porque se o módulo de πC (|πC|) é colocado na frente do próprio πC, também o |πC| precisa ser auto-delimitante:

U(… ||πC|| |πC| πC p) = C(p).

De qualquer modo, essa maneira de abordar as máquinas universais U foi a idéia original da TAI nos anos 1960 proposta de modo independente por Solomonoff, Kolmogorov e por mim. Mas dez anos depois percebeu-se que essa não era a abordagem correta. Na verdade era necessário que todo o programa πC p para U fosse auto-delimitante, e não apenas o prefixo πC. Era preciso que a coisa toda fosse auto-delimitante para se chegar à correta teoria da complexidade dos programas.

Em outras palavras, a diferença básica entre a versão de 1960 da TAI e da sua versão de 1970 é que, na primeira, uma seqüência de N bits em geral precisava de um programa de N bits – pelo menos, se for irredutível como a maioria dos algoritmos. Na segunda versão da TAI parece que foi dado um passo atrás, porque a seqüência necessária terá N+log2N bits para fazer os programas auto-delimitantes. Uma seqüência de N bits normalmente precisa de um programa de N+log2N bits:

Para a maioria das seqüências de N-bits:
a TAI1960 tem N bits de complexidade,

a TAI1970 tem N+log2N bits de complexidade.

Na verdade, podemos escrever que na TAI1970 temos N mais uma função H(N), que é o tamanho do menor programa auto-delimitante para calcular N. É exatamente isso o que significa o termo logarítmico acima. Em outras palavras, na versão de 1970 da TAI, o tamanho do menor programa para calcular uma seqüência de N bits tem normalmente N bits mais o tamanho em bits do menor programa auto-delimitante para calcular N, que basicamente tem

log N + loglog N + logloglog N + ….

bits de comprimento. Esse é o aspecto de matriuchka – essas bonecas russas encaixadas uma dentro das outras – dessa teoria.

A versão de 1970 da TAI, que apenas toma idéia de auto-delimitação do prefixo e a aplica a todo o programa, é uma linguagem perfeita ainda melhor. Portanto, a TAI tem dois estágios. Primeiro dizemos que essas são as mais perfeitas linguagens,

U(πC p) = C(p),

na qual πC é auto-delimitante. Depois insistimos que a todo esse πC p precisa ser auto-delimitante. Ao fazer isso, temos novos resultados importantes, como por exemplo a sub-aditividade da complexidade dos programas,

H(x, y) ≤ H(x) + H(y),

que não ocorre se não tornarmos a coisa toda auto-delimitante. A fórmula acima diz apenas que é possível concatenar o menor programa para calcular x e o menor programa para calcular y e chegar a um programa para calcular x e y.

Pela TAI1960 , não é possível sequer calcular a probabilidade de parada Ω. Se for permitido que toda seqüência de N-bits sejam programas, então não será possível definir a probabilidade de parada de uma maneira natural, porque a soma para definir a probabilidade de um programa parar [6],

Ω = Σp parada 1/2(número de bits de p)

diverge ao infinito ao invés de estar entre zero e um. Esse é um ponto chave na TAI, no campo da complexidade do tamanho do programa.

Para deixar esse ponto mais claro, é necessário definir a probabilidade de parada. A maneira lógica de pensar sobre programas é que existem 2N programas com N bits. Sendo assim, a maneira natural de definir a probabilidade de parada é que cada programa de N-bit que pára contribui com 1/2N para a probabilidade de parada. O problema é que essa seqüência diverge, porque para cada N fixo existem programas que param na ordem de 2N ; portanto, se somarmos as possibilidades para todos os tamanhos N, a soma tenderá ao infinito, o que não é nada bom.

A fim de se obter uma probabilidade de parada entre zero e um,

0 < Ω = Σp pára 1/2(número de bits de p) < 1

é preciso ter certeza de que a probabilidade total somada por todos os programas é menor ou igual a 1. E a maneira de fazer isso é igual à demonstrada ao tornar o prefixo πC auto-delimitante. Permitam-me colocar esse assunto em termos antropomórficos: suponha que você seja o computador universal U; conforme você lê o programa, bit por bit, você precisará ser capaz de decidir por si mesmo quando o programa termina sem nenhum sinal de pontuação no final.

Trata-se de um modo de dizer que nenhuma extensão de um programa válido é um programa válido, e que o conjunto de programas válidos é um conjunto sem prefixos. Então, o fato de que a soma que define Ω precisa estar entre zero e um é apenas um caso especial da chamada desigualdade de Kraft na teoria da informação de Shannon.

Intuitivamente, enquanto lê o programa bit por bit, você é forçado a parar sem ver nenhum sinal de pontuação especial. Em outras palavras, na TAI de 1960 usávamos de fato um alfabeto com três símbolos: 0, 1 e o espaço vazio – este último dizia que o programa terminava. Mas era um símbolo desperdiçado, já que muito pouco usado – quando temos um alfabeto de três símbolos, a maneira correta de utilizá-lo supõe que cada símbolo seja empregado em mais ou menos um terço das vezes; em outras palavras, que tenha uma freqüência próxima a 33%.

Como na verdade usava-se apenas os 0s e 1s, seria interessante forçar a máquina de Turing a decidir por si mesma quando o programa terminava. Não fazia sentido ter um espaço vazio apenas para indicar esse término.

Os programas com N bits de comprimento, assim, passaram a ter N+log2N bits para indicar à máquina o seu tamanho. Mas por outro lado, quando temos dois programas concatenados, passa a ser possível fazer com que a própria máquina os separe, rodando depois em seguida um após o outro – e assim a complexidade do tamanho do programa passa a ser sub-aditiva. Roda-se a máquina universal U para calcular o primeiro objeto x e depois novamente a mesma máquina para calcular o objeto y. Temos deste modo x e y, e portanto

H(x, y) ≤ H(x) + H(y).

Em outras palavras, a complexidade do tamanho do programa é sub-aditiva porque é possível tomar sub-rotinas e concatená-las para fazer um programa maior.

Numa síntese, podemos dizer o que essas linguagens binárias auto-delimitantes, através do estudo da complexidade do tamanho do programa, foram discriminadas como as mais perfeitas linguagens. Para chegar a elas foram necessários dois estágios, a TAI1960 e a TAI1970 , que são linguagens usadas para expressar algoritmos e não raciocínio matemático; mais especificamente, linguagens universais de programação maximamente expressivas e concisas. Nós já sabíamos como fazer isso na década de 1960; na década seguinte descobrimos que elas deveriam também ser auto-delimitantes, o que trazia outras propriedades desejáveis, como a capacidade de definir a probabilidade de parada Ω.

Conclusões

Eis a história. Agora talvez seja interessante resumir toda essa saga da busca da linguagem perfeita. Como já disse, há algumas conclusões negativas e outras positivas.

Hilbert queria encontrar uma linguagem que fornecesse todas as verdades matemáticas, i.e., uma teoria axiomática formal para toda a matemática. Seu intuito era formular uma Teoria Unificada para o mundo da matemática pura, mas percebeu que isso não pode acontecer – já que sabemos que toda teoria formal axiomática é incompleta, como foi mostrado por Gödel, por Turing e pela probabilidade de parada Ω. Ao invés de encontrar a Teoria Unificada, encontramos a incompletude, a incomputabilidade e a aleatoriedade algorítmica. Esse é o lado sombrio da busca, mas algo fascinante do ponto de vista epistemológico: descobrimos os limites para o que pode ser conhecido, para a razão.

O mais interessante é que a comunidade matemática não deu a mínima para isso. Eles ainda desejam e acreditam na verdade absoluta! E se você quer uma prova disso, basta ler a edição de dezembro de 2008 da Notices of the American Mathematical Society, um número especial sobre provas formais.

A tecnologia se desenvolveu a tal ponto que agora é possível rodar no computador provas matemáticas reais e depois checá-las. Um matemático escreve uma prova em linguagem formal, preenche os passos faltantes e faz correções até que um checador de provas possa compreendê-la e verificar se está correta. Esses programas estão ficando cada vez mais sagazes, e cada vez mais os detalhes podem ser deixados de lado. Conforme a tecnologia melhora, o trabalho de formalizar essas provas vai ficando cada vez mais fácil.

Os extremistas das provas formais já estão dizendo que, no futuro, toda matemática precisará ser escrita de maneira formal e verificada através destes programas. Isso já pode ser feito, por exemplo, com a prova da conjectura das quatro cores: ela foi escrita como uma prova formal que foi verificada num programa checador de provas. Dá para acreditar!?

A posição desses extremistas é que no futuro o único trabalho humano será decidir se uma prova que já foi checada pelo computador é ou não digna de ser publicada, sem se preocupar com a correção da prova. Desejam também um repositório de todo o conhecimento matemático sob a forma de um banco de dados contendo todas as provas de teoremas já checados. Esse projeto envolve uma comunidade considerável de estudiosos, o que significa que… ainda acreditam na verdade absoluta.

Não é minha intenção desprezar esse trabalho extremamente interessante. Na verdade, julgo que há uma tensão intelectual maravilhosa entre isso e os resultados de incompletude discutidos acima. As pessoas ainda querem levar adiante a proposta de Hilbert e de fato formalizar tudo, como se Gödel e Turing nunca tivessem existido! Considero tudo isso extremamente interessante e inesperado.

Mas desejo encerrar com os aspectos positivos. Há línguas perfeitas para computar, mas não para o raciocínio. São as linguagens de programação. A TAI tomou as linguagens de programação mais expressivas e mostrou que são particularmente interessantes como base da teoria da complexidade do tamanho do programa.

Esse é o ponto substancialmente positivo. E como dediquei a maior parte da minha carreira profissional ao problema da complexidade, vejo que existe aí uma grande contribuição para a referida busca pela linguagem perfeita. Afinal, estamos lidando com uma medida do poder de expressão, de complexidade conceitual e de complexidade de idéias. Lembrem-se de que eu disse que de uma perspectiva medieval tratava-se de quantas decisões sim/não Deus precisou fazer para criar alguma coisa, algo que faria obviamente de maneira otimizada, o mais perfeitamente possível. Isso, é claro, se você enxergasse Deus como um programador, não como um matemático.

Do lado teórico, essa busca foi em alguma medida decepcionante, devido à incompletude de Gödel: não há uma Teoria Unificada para a matemática pura. Está provado que ela não existe. Na verdade, se olharmos para os bits da probabilidade de parada Ω, veremos que a matemática pura contém um complexidade irredutível infinita, e nesse sentido preciso é mais parecida com a biologia – o domínio do complexo – do que com a física teórica, na qual ainda há esperança de se encontrar uma simples e elegante Teoria Unificada.

Esse é a desvantagem do assunto, ao menos se você não for biólogo. Vantajosa é essa maravilhosa tecnologia de programação. Portanto, esse sonho de encontrar a linguagem perfeita e o conhecimento absoluto acabou nos confins de um computador; acabou encerrada em um Golem.

Deixe-me terminar com uma perspectiva medieval. O que aconteceria, com efeito, se mostrássemos um notebook a alguém do século XII? Um computador é uma máquina, um objeto físico; e quando colocamos nele um software, ele repentinamente ganha vida. Segundo essa perspectiva, eu diria que as linguagens perfeitas que encontramos nos deram alguns poderem mágicos, divinos, comunicadores de vida; não a toda, mas a um certo tipo de matéria inanimada. Um hardware é análogo a um corpo e um software análogo a uma alma: quando os dois se unem, esse objeto inanimado ganha vida e gera os seus próprios mundos virtuais.

Assim, uma pessoa do ano 1200 diria que a busca pela linguagem perfeita foi bem sucedida e nos proporcionou algumas habilidades mágicas, divinas; só que… nós a encaramos como algo totalmente natural.

Gregory Chaitin é pesquisador sênior do Centro de Pesquisas Watson da IBM em Nova York. É membro da Academia Brasileira de Filosofia, foi agraciado com um doutorado honoris causa pela Universidade de Córdoba na Argentina e é professor honorário na Universidade de Buenos Aires. Também lecionou no Instituto de Sistemas Complexos de Valparaíso, Chile, e no Programa de História das Ciências e das Técnicas e Epistemologia (HCTE) na Universidade Federal do Rio de Janeiro (UFRJ). Um de seus livros, Meta Mat! Em busca do Ômega, foi publicado este ano em São Paulo pela Editora Perspectiva. Para mais informações, ver sua homepage em http://www.cs.umaine.edu/~chaitin/.

Agradecemos a Elói Medina Galego, professor livre-docente do Instituto de Matemática e Estatística da USP, pela revisão dos termos técnicos e a elaboração das notas explicativas relativas a conceitos matemáticos, que incorporamos nas notas explicativas do tradutor.

Tradução de Júlio Lemos e Guilherme Malzoni Rabello.


[1] Palestra ministrada a 21 de setembro de 2009, no Perimeter Institute for Theoretical Physics em Waterloo, Canadá. O autor agradece ao Prof. Ilias Kotsireas, da Wilfrid Laurier University, por organizar a sua lecture tour em Ontário neste mês de setembro de 2009. O vídeo dessa palestra pode ser visto em http://pirsa.org/09090007/. Seguiram-se vinte minutos de perguntas e discussão que não foram transcritos aqui, mas estão disponíveis em digital streaming video.

[2] Trad. do original La ricerca della lingua perfetta nella cultura europea, publicado no Brasil pela EDUSC, 2001. Traduzimos neste artigo a expressão do original, language,  por “língua”; embora saibamos que nem todos os gramáticos do português estão de acordo neste ponto, seguimos nisso a distinção entre “língua”, código concreto de sinais determinados, e “linguagem”, capacidade humana de expressar-se por meio desses códigos. Somente abrimos uma exceção para a expressão já consagrada “linguagem” ou “linguagens de programação” (N. do T.).

[3] Estritamente falando, nos termos teológicos e metafísicos já empregados na Idade Média, essa linguagem não nos daria um conhecimento de Deus, mas da Sabedoria divina, do conhecimento que Deus tem do mundo (N. do T.).

[4] Cantor estendeu a noção de contar os elementos de um conjunto finito aos conjuntos infinitos. Os números 1, 2, 3 pertencem à contagem de conjuntos finitos e os alephs permitem a contagem dos conjuntos infinitos (N. do T.).

[5] A fórmula deve ser lida da seguinte maneira: “o conjunto formado por x tal que x não pertence a x”. (N. do T.)

[6] A maneira de ler a expressão matemática seguinte é: “ômega é igual ao somatório de 1/2 elevado ao número de bits de todos os programas p que param” (N. do T.).

Deixe uma resposta

O seu endereço de email não será publicado Campos obrigatórios são marcados *

Você pode usar estas tags e atributos de HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>