Quem pode nomear o maior número?

Por Scott Aaronson
Título original: “Who Can Name the Bigger Number?”

Em uma velha piada, dois nobres competem para nomear o maior número. O primeiro, depois de ruminar por horas, proclamou triunfantemente “Oitenta e três!” O segundo, fortemente impressionado, respondeu: “Você ganhou”.

O desafio para o maior número claramente não faz sentido quando os competidores se revezam. Mas o que aconteceria se os contendores escrevessem seus números simultaneamente, nenhum sabendo o do outro? Para apresentar uma palestra sobre “grandes números”, convidei dois voluntários da plateia para tentar exatamente isso. Eu disse a eles as regras:

Você tem quinze segundos. Usando notação matemática normal, palavras ou ambos, nomeie um único número inteiro (não infinito) em um folha em branco. Seja preciso o suficiente para que qualquer matemático moderno possa determinar exatamente qual número você nomeou, consultando apenas sua folha e, se necessário, a literatura publicada.

Portanto, os concorrentes não podem dizer “o número de grãos de areia no Saara”, porque a areia flutua regularmente dentro e fora do Saara. Eles também não podem dizer “o número do meu oponente mais um”, ou “o maior número que alguém já pensou mais um”; novamente, eles são mal definidos, dado o que a nossa matemática razoável tem disponível. Dentro das regras, o competidor que nomear o maior número vence.

Estão prontos? Pronto. Já.

Os resultados do concurso nunca são o que eu esperaria. Um aluno da sétima série uma vez encheu sua folha com uma série de noves sucessivos. Como muitos outros iniciantes em números grandes, ele procurou maximizar seu número colocando um 9 em cada casa decimal. Se ele tivesse escolhido o 1, mais fácil de escrever do que o 9 curvo, seu número poderia ter sido milhões de vezes maior. No entanto, ele ainda seria dizimado pela garota que ele estava enfrentando, que escreveu uma sequência de noves seguida de um super índice ⁹⁹⁹. AHA! Uma potência: um número multiplicado por si mesmo 999 vezes. Percebendo sua inovação, declarei a garota uma vitória sem me preocupar em contar os noves na folha.

E até mesmo o número da garota poderia ter sido muito maior ainda, se ela empilhasse o poderoso exponencial mais de uma vez. Pegue , por exemplo. Este gigante, igual a 9^387420489, tem 369693100 dígitos. Em comparação, o número de partículas elementares no universo observável é de aproximadamente 85 dígitos, mais ou menos. Três noves, quando empilhados exponencialmente, já nos elevam incompreensivelmente além de toda matéria que podemos observar… por um fator de cerca de 10^369693015. E nós não dissemos nada sobre ou  .

Notação decimal, potências, expoentes empilhados: cada um pode expressar os números grandes ilimitados e, nesse sentido, todos são equivalentes. Mas os sistemas de notação diferem dramaticamente nos números que podem expressar concisamente. É isso que ilustra o prazo de quinze segundos. Leva a mesma quantidade de tempo escrever 9999, e , sendo o primeiro número diário, o segundo astronômico e o terceiro hiper-mega astronômico. A chave para o maior desafio dos números não é a digitação rápida, mas sim um poderoso paradigma para a captura concisa do gigantesco. Tais paradigmas são raridades históricas. Encontramos agitação na antiguidade, outra agitação no século XX, e não muito no meio. Mas quando surge uma nova maneira de expressar concisamente grandes números, muitas vezes é como um subproduto de uma revolução científica maior: matemática sistematizada, lógica formal, ciência da computação. Revoluções importantes, como qualquer Kuhniano poderia lhe dizer, elas só acontecem sob as condições sociais certas. Assim, a história dos grandes números é a história do progresso humano.

E aqui se faz um paralelismo com outra história matemática. Em seu livro notável e subestimado Uma história de π, Petr Beckmann argumenta que a razão entre circunferência e diâmetro é “um espelho único da história do homem”. Nas raras sociedades onde a ciência e a razão encontraram refúgio (a antiga Atenas de Anaxágoras e Hípias, a Alexandria de Eratóstenes e Euclides, a Inglaterra do século XVII de Newton e Wallis) os matemáticos deram grandes passos no cálculo de π(pi). Em Roma e na Europa medieval, ao contrário, o conhecimento de π está estagnado. Aproximações grosseiras como o 25/8 dos babilônios e o 3 da Bíblia continuavam se alternando.

Acho que esse mesmo padrão se aplica a números grandes. Curiosidade e abertura levam a um fascínio por grandes números e à visão flutuante de que nenhuma quantidade, seja o número de estrelas na galáxia ou o número de mãos possíveis em uma ponte, é grande demais para a mente lidar. Por outro lado, a ignorância e a irracionalidade levam ao fatalismo sobre grandes números. A Bíblia, por exemplo, refere-se vinte e uma vezes à suposta incalculabilidade da areia. Veja Gênesis 32:13 “No entanto, você me disse: Eu te farei bem e farei sua descendência como a areia do mar, tão numerosa que não pode ser contada”. Ou Hebreus 11:12 “numerosos como as estrelas no céu e incontáveis como a areia na praia do mar.” Essa noção de que a multidão de grãos de areia poderia ser infinita, que é para pasmada estupefação, mas não para quantificação, é antiga. O historiador Ilan Vardi cita a palavra grega antiga ψαµµκoσιoι, de significado coloquial gazilhões; bem como uma passagem de Ode Olímpica II de Píndaro afirmando que “a areia escapa de ser contada”.

Mas a areia não escapa à contagem, como reconheceu Arquimedes no século III a.C. Foi assim que começou O contador de areia, uma espécie de artigo científico popular enviado ao rei de Siracusa:

Há alguns… que pensam que o número de arenas é infinito em multidão… e há outros que, não o considerando infinito, ainda pensam que nenhum número foi nomeado que seja grande o suficiente para exceder sua multidão. Mas eu vou tentar mostrar a vocês [números que] excedem não apenas o número da massa de areia igual em magnitude à Terra… mas também por uma massa igual em magnitude ao universo.

Isso Arquimedes passou a fazer, essencialmente usando o termo grego antigo miríade, o que significa dez mil, a base de exponenciais. Adotando o modelo cosmológico presciente de Aristarco, no qual a “esfera de estrelas fixas” é muito maior do que a esfera em que a Terra gira em torno do sol, Arquimedes obteve um limite superior de 10⁶³ do número de grãos de areia necessários para preencher o universo. (Supostamente 10⁶³ é o maior número com um nome lexicográfico padrão americano: vigintilhão. Mas o sério vigintilhão deve tomar cuidado para não ser usurpado pelos nomes mais caprichosos googol, ou 10¹⁰⁰, e googolplex, ou .) Grande é, claro, mas 10⁶³ não é elevado aos altares do maior número de todos os tempos. Seis séculos depois, Diofanto desenvolveu uma notação mais simples para exponenciais, permitindo-lhe ultrapassar .

Então, na Idade Média, a ascensão dos algarismos arábicos e do posicionamento decimal facilitou o empilhamento de exponenciais ainda maiores. Mas o paradigma de Arquimedes para expressar grandes números não foi fundamentalmente substituído até o século XX. E ainda hoje, os exponenciais dominam a discussão popular do imenso.

Considere, por exemplo, a lenda frequentemente repetida do grão-vizir da Pérsia que inventou o xadrez. O rei, como diz a lenda, ficou encantado com o novo jogo e convidou o vizir a pedir sua própria recompensa. O vizir respondeu que, sendo um homem modesto, só queria um grão de trigo para o primeiro quadrado do tabuleiro, dois grãos para o segundo, quatro para o terceiro e assim por diante, com o dobro de grãos por quadrado do que o anterior. O rei numérico consentiu, sem perceber que o número total de grãos para todos os 64 quadrados seria 2⁶⁴−1 ou 18,4 trilhões… equivalente à atual produção mundial de trigo por 150 anos.

Apropriadamente, é esse crescimento exponencial que torna o xadrez em si tão difícil. Existem apenas cerca de 35 escolhas legais em cada jogada de xadrez, mas as escolhas se multiplicam exponencialmente para produzir cerca de 10⁵⁰ posições possíveis no tabuleiro… grande até mesmo para um computador pesquisar exaustivamente. É por isso que demorou até 1997 para um computador, Deep Blue, derrotar o campeão mundial de xadrez humano. E em Go, que tem um tabuleiro de 19×19 e mais de 10¹⁵⁰ posições possíveis, mesmo um humano amador ainda pode vencer os programas número um do mundo. O crescimento exponencial também infecta os computadores de outras maneiras. O problema do viajante pede a rota mais curta conectando um conjunto de cidades, dada a distância entre cada par de cidades. O irritante é que o número de rotas possíveis cresce exponencialmente de acordo com o número de cidades. Quando há, digamos, cem cidades, há cerca de 10¹⁵⁸ rotas possíveis e, embora vários atalhos sejam possíveis, nenhum algoritmo computacional conhecido é fundamentalmente melhor do que provar uma a uma cada rota. O problema do viajante pertence a uma classe chamada NP-completo, que inclui centenas de outros problemas de interesse prático. (NP representa o termo técnico ‘tempo polinomial não determinístico’.) Sabe-se que se existe um algoritmo eficiente para qualquer problema NP-completo, então existem algoritmos eficientes para todos eles. Aqui ‘eficiente’ significa usar uma quantidade de tempo proporcional ao tamanho máximo do problema elevado a alguma potência fixa, por exemplo, o número de cidades ao cubo. No entanto, conjectura-se que não existe um algoritmo eficiente para problemas NP-completos. A prova desta conjectura, chamada , tem sido um grande problema não resolvido na computação por trinta anos.

Embora os computadores provavelmente nunca resolvam problemas NP-completos com eficiência, há mais esperança para outro graal da computação: a replicação da inteligência humana. O cérebro humano tem aproximadamente cem bilhões de neurônios conectados por cem trilhões de sinapses. E embora a função de um neurônio individual seja apenas parcialmente compreendido, acredita-se que cada neurônio dispara impulsos elétricos de acordo com regras relativamente simples até mil vezes por segundo. Então o que temos é um computador altamente conectado em rede capaz de talvez 10¹⁴ operações por segundo; em comparação, o supercomputador paralelo mais rápido do mundo, o 9200-Pentium Pro teraflops machine em Sandia National Lab, pode fazer 10¹² operações por segundo. Ao contrário da crença popular, a matéria cinzenta não é apenas conectada à inteligência: ela supera o silício, mesmo em poder computacional. Mas é improvável que isso permaneça verdadeiro por muito tempo. O motivo é a lei de Moore, que, em sua formulação de 1990, afirma que a quantidade de informação que pode ser armazenada em um chip de silício cresce exponencialmente, dobrando cerca de uma vez a cada dois anos. A lei de Moore acabará por estar fora de questão, à medida que os componentes do microchip atingem a escala atômica e a litografia convencional vacila. Mas novas tecnologias radicais, como computadores ópticos, computadores de DNA, ou mesmo computadores quânticos, poderiam usurpar o lugar do silício.

Para os previsores da inteligência artificial, a Lei de Moore é um glorioso arauto do crescimento exponencial. Mas os exponenciais também têm seu lado mais sombrio. A população humana passou recentemente de seis bilhões e está dobrando aproximadamente a cada quarenta anos. A esta taxa exponencial, se a pessoa média pesa 70 kilos, então no ano 3750 toda a Terra será composta de carne humana. Mas antes de investir em desodorantes, perceba que a população vai parar de aumentar muito antes que isso aconteça, seja através de fomes, epidemias, aquecimento global, extinções em massa de espécies, ar irrespirável ou, entrando no reino da especulação, controle de natalidade. Não é difícil entender por que o físico Albert Bartlett afirma que “a maior limitação da raça humana” é “nossa incapacidade de entender a função exponencial”. Ou por que Carl Sagan nos aconselha a “nunca subestimar um exponencial”. Em seu livro Bilhões e Bilhões, Sagan dá outras consequências deprimentes do crescimento exponencial. À taxa de inflação de cinco por cento ao ano, um dólar valeria apenas 37 centavos depois de vinte anos. Se um núcleo de urânio emite dois nêutrons, e ambos colidem com dois outros núcleos de urânio, fazendo com que emitam dois nêutrons, e assim por diante… bem, eu mencionei o holocausto nuclear como um possível fim ao crescimento populacional?

Os exponenciais são familiares, relevantes, intimamente ligados ao mundo físico e às esperanças e medos humanos. Usando o sistema de notação que discutirei a seguir, poderemos nomear concisamente números que se tornam insignificantes em comparação com exponenciais, que subjetivamente falando excedem tanto quanto excede 9. Mas estes novos sistemas podem parecer mais abstrusos do que os exponenciais. Em seu ensaio Sobre a entorpecimento numérico, Douglas Hofstadter leva seus leitores ao precipício desses sistemas, mas depois afirma que:

Se continuássemos nossa discussão apenas por um milissegundo mais, nós estaríamos bem no meio da teoria das funções recursivas e da complexidade algorítmica, e isso seria muito abstrato. Então vamos deixar o assunto aqui.

Mas largar o assunto é abandonar não apenas o desafio do maior número, mas qualquer esperança de entender como os paradigmas mais fortes levam aos maiores números. E assim chegamos ao início do século XX, quando uma escola de matemáticos chamada formalistas buscam colocar toda a matemática em fundamentos axiomáticos rigorosos. A questão-chave para os formalistas era o que a palavra “computável” significava. Isto é, como podemos saber se uma sequência de números pode ser listada por um procedimento mecânico definido? Alguns matemáticos pensavam que ‘computável’ coincidia com uma noção técnica chamada ‘primitiva recursiva’. Mas em 1928 Wilhelm Ackermann os refutou construindo uma sequência de números que é claramente computável, embora cresça rápido demais para ser uma primitiva recursiva. A ideia de Ackermann era criar uma interminável procissão de operações aritméticas, cada uma mais poderosa que a anterior. Primeiro vem a soma. Em segundo lugar vem a multiplicação, que podemos pensar como adição repetida: por exemplo, 5×3 significa 5 adicionado a si mesmo 3 vezes, ou 5 + 5 + 5 = 15. Em terceiro lugar vem a potenciação, que podemos pensar como multiplicação repetida. Quarta vem… o quê? Bem, temos que inventar uma nova operação estranha, para potencialização repetida. O matemático Rudy Rucker chama isso de ‘tetração’. Por exemplo, ‘5 tetrado a 3’ significa 5 elevado à sua própria potência 3 vezes, ou, um número com 2185 dígitos. Podemos continuar. Quinto vem a tetração repetida: podemos chamá-la de ‘pentação’? Sexto vem a pentação repetida: ‘hexação’? As operações continuam interminavelmente, com cada uma apoiada por seu antecessor para espiar ainda mais alto no firmamento dos grandes números. Se cada operação fosse um sabor doce, então a sequência de Ackermann seria o catálogo de amostras, misturando um número de cada sabor. O primeiro da sequência é 1+1, ou (não prenda a respiração) 2. O segundo é 2×2 ou 4. Terceiro é 3 elevado à terceira potência, ou 27. Ei, esses números não são tão grandes!

Fee. Fi. Fo. Fum.

Quarta é 4 tetrado para 4, ou , que tem 10154 dígitos. Se você está planejando escrever este número, é melhor começar agora. Quinto é 5 pentado para 5, ou com ‘5 tetrado a 4’ numerais na pilha. Esse número é colossal demais para ser descrito em termos comuns. E os números ficam muito maiores a partir daqui. Empunhando a sequência de Ackermann, podemos esmurrar oponentes incultos no maior desafio de números. Mas precisamos ter cuidado, pois existem várias definições da sequência de Ackermann, nem todas idênticas. Abaixo do limite de quinze segundos, aqui está o que eu poderia escrever para evitar ambiguidade:

Profunda como parece, a sequência de Ackermann tem algumas aplicações. Um problema em uma área chamada teoria de Ramsey pergunta pela menor dimensão de um hipercubo que satisfaça uma certa propriedade. Acredita-se que a dimensão correta seja 6, mas a dimensão mais baixa que ninguém conseguiu provar é tão grande que só pode ser expressa usando a mesma ‘aritmética estranha’ subjacente à sequência de Ackermann. Na verdade, o Guinness Book of World Records certa vez ele listou essa dimensão como o maior número já usado em uma prova matemática.

(Outro candidato ao título já foi o número de Skewes, cerca de, que surge no estudo  de como os números primos são distribuídos. O famoso matemático GH Hardy disse sarcasticamente que o número de Skewes era “o maior número que já serviu a qualquer propósito definido na matemática”.) Por exemplo, na análise de uma estrutura de dados chamada ‘Union-Find’, um termo é multiplicado pelo inverso da sequência de Ackermann, ou seja, para cada inteiro x, o primeiro númeron tal que n-ésimo número de Ackermann é maior que x. A inversa cresce tão lentamente quanto a sequência original de Ackermann cresce rapidamente; para todos os efeitos práticos, o inverso é como máximo 4.

Os números de Ackermann são bastante grandes, mas ainda não são grandes o suficiente. A busca por números ainda maiores nos leva de volta aos formalismos. Depois que Ackermann mostrou que ‘recursão primitiva’ não é o que queremos dizer com ‘computável’, a questão ainda permanece: o que nós queremos dizer com ‘computável’? Em 1936, Alonzo Church e Alan Turing responderam independentemente a essa pergunta. Enquanto Church respondeu usando um formalismo lógico chamado cálculo lambda, Turing respondeu usando uma máquina de computação idealizada (a máquina de Turing) que é essencialmente equivalente a cada Compaq, Dell, Macintosh e Cray no mundo moderno. O artigo de Turing descrevendo sua máquina, “On Computable Numbers”, é justamente celebrado como o documento fundador da ciência da computação. “Computar”, diz Turing,

”é normalmente feito escrevendo certos símbolos em um pedaço de papel. Podemos imaginar este papel dividido em quadrados como um livro de aritmética infantil. Em aritmética elementar, o caráter bidimensional do papel às vezes é útil. Mas esse uso é sempre evitável, e acho que será acordado que o caráter bidimensional do papel não é indispensável na computação. Suponho então que o cálculo seja feito em papel unidimensional, em uma fita dividida em quadrados.”

Turing continua explicando sua máquina usando um raciocínio engenhoso a partir dos primeiros princípios. A fita, diz Turing, se estende infinitamente em ambas as direções, de modo que a máquina teórica não seja restringida por limitações de recursos físicos. Além disso, há um símbolo escrito em cada quadrado da fita, como o ‘1’ e o ‘0’ na memória do computador moderno. Mas como os símbolos são manipulados? Bem, há uma ‘cabeça’ se movendo para frente e para trás ao longo da fita, examinando um quadrado de cada vez, escrevendo e apagando símbolos de acordo com regras definidas. As regras estão no programa de cabeçalho: altere-as e você altera o que o cabeçalho faz.

A percepção augusta de Turing foi que podemos programar a cabeça para realizar qualquer computação. As máquinas de Turing podem adicionar, multiplicar, extrair raízes cúbicas, classificar, pesquisar, verificar a ortografia, analisar, jogar jogo da velha, listar a sequência de Ackermann… Se representarmos a entrada do teclado, a saída de dados na tela e assim por diante como símbolos em fita, poderíamos até executar o Windows em uma máquina de Turing. Mas há um problema. Passe o mouse sobre uma sequência de símbolos e, eventualmente, ela pode parar, ou pode durar para sempre… como o lendário programador que fica preso na ducha porque as instruções no frasco do xampu dizem “ensaboar, enxaguar, repetir”. Se a máquina vai funcionar para sempre, seria bom saber com antecedência, para não passarmos uma eternidade esperando que ela termine. Mas como podemos determinar em um período de tempo finito, se algo vai continuar indefinidamente? Se você apostar com um amigo que seu relógio nunca vai parar, quando você vai declarar vitória? Mas talvez haja algum programa inteligente que possa examinar outros programas e nos dizer, infalivelmente, se eles vão parar de funcionar. Ainda não tínhamos pensado nisso.

Não há. Turing provou que este problema, chamado de problema da parada, é insolúvel por máquinas de Turing. A demonstração é um belo exemplo de auto-referência. Ele formaliza um velho argumento sobre porque você nunca pode ter uma introspecção perfeita: porque se você pudesse, então você poderia determinar o que você estaria fazendo dez segundos depois, e então fazer outra coisa. Turing imaginou que existe uma máquina especial que poderia resolver o problema da parada. Então ele mostrou como podemos fazer essa máquina analisar a si mesma, de modo que ela tenha que parar se funcionar para sempre, e funcionará para sempre se parar. Como um cão de caça que finalmente agarra seu rabo e se devora, a máquina mítica desaparece em uma fúria de contradição. (Que é o tipo de coisa que você nunca diria em um trabalho de pesquisa.)

“Muito bem”, você diz (ou talvez diga “não muito bem”). “Mas o que tudo isso tem a ver com grandes números?” AHA! A conexão só foi publicada em maio de 1962. Então, na Bell System Technical Journal, Aninhado entre artigos organizados pragmaticamente sobre “Multiport Structures” e “Pressure Wave Driven Seals” estava o modestamente intitulado “On Non Computable Functions” de Tibor Rado. Neste artigo, Rado apresentou os maiores números que alguém jamais imaginou.

Sua ideia era simples. Assim como classificamos as palavras por quantas letras elas contêm, podemos classificar as máquinas de Turing por quantas regras elas têm em suas cabeças. Algumas máquinas têm apenas uma regra, algumas têm duas regras, outras ainda têm três regras e assim por diante. Mas para cada inteiro n, assim como há apenas um número finito de palavras com n letras, então também há apenas um número finito de máquinas com n regras. Entre essas máquinas, algumas pararão e outras funcionarão para sempre quando iniciarem com uma fita em branco. Das que param, pergunta Rado, qual é o número máximo de passos que qualquer máquina dá antes da parada? (Na verdade, Rado estava perguntando principalmente sobre o número máximo de símbolos que qualquer máquina pode gravar na fita antes de parar. Mas o número máximo de etapas, que Rado chamou de S(n), tem as mesmas propriedades básicas e é mais fácil de raciocinar.)

Rado chamou esse máximo de o enésimo número do “castor ocupado”. (Ah, sim, o início dos anos 1960 foi uma época mais inocente.) Ele visualizou cada máquina de Turing como um castor correndo atarefadamente ao longo da fita, escrevendo e apagando símbolos. O desafio, então, é encontrar o castor mais ocupado com exatamente n regras, embora não um infinitamente ocupado. Podemos interpretar este desafio como a busca do programa de computador “mais complicado” de n bits de tamanho: aquele que produz mais material, mas não uma quantidade infinita.

Agora suponha que conhecemos o enésimo número do castor ocupado, que chamaremos BB(n). Então poderíamos decidir se alguma máquina de Turing com n regras para partindo uma fita em branco. Nós apenas temos que rodar a máquina: se ela parar, tudo bem; mas se não parar em BB(n) passos, então sabemos que nunca vai parar, pois BB(n) é o número máximo de passos que poderia dar antes de parar. Da mesma forma, se você sabe que todos os mortais morreram antes de seu aniversário de 200 anos, então se Sally viveu até os 200 anos, você pode concluir que Sally era imortal. Portanto, nenhuma máquina de Turing pode listar os números do castor ocupado… porque se pudesse, poderia resolver o problema da parada, que já sabemos ser impossível.

Mas há um fato curioso. Suponha que podemos nomear um número maior que o enésimo castor ocupado BB(n). Chamaremos esse número d de dique, já que como um dique de castor, é um trecho que o castor está à abaixo. Com d em mãos, calcular o próprio BB(n) torna-se fácil: basta simular todas as máquinas de Turing com n regras. Aqueles que não pararam d passos (aqueles que quebram o teto da barragem) nunca vão parar. Assim, podemos listar exatamente quais máquinas param e, entre elas, o número máximo de passos que qualquer máquina dá antes de parar é BB(n).

Conclusão? A sequência de números do castor ocupado, BB(1), BB(2), e sucessivamente, cresce mais rápido que qualquer sequência computável. Mais rápido que exponenciais, exponenciais empilhados e a sequência de Ackermann, você escolhe. Porque se uma máquina de Turing pudesse calcular uma sequência que cresce mais rápido que o castor ocupado, então poderíamos usar essa sequência para obter os d, a barragem do castor. E com esses d, você poderia listar os números do castor ocupado, o que (parece familiar?) já sabemos que é impossível. A sequência do castor ocupado não é computável, apenas porque cresce incrivelmente rápido… rápido demais para qualquer computador acompanhar, mesmo em princípio. Isso significa que nenhum programa de computador pode listar todos os castores ocupados um por um.

Isso não significa que castores ocupados específicos precisam permanecer eternamente desconhecidos. E, de fato, consertá-los tem sido um hobby de computação desde que Rado publicou seu artigo. É fácil verificar que BB(1), o primeiro número do castor ocupado, é 1. Isso porque se uma máquina de Turing de uma regra não para após o primeiro passo, ela continuará se movendo ao longo da fita infinitamente. Não há espaço para qualquer outro comportamento mais complexo. Com duas réguas podemos fazer mais, e um pouco de trabalho determinou que BB(2) é 6. Seis passos. E sobre o terceiro castor ocupado? Em 1965 Rado, juntamente com Shen Lin, provou que BB(3) é 21. A tarefa era árdua, exigindo análise humana de muitas máquinas para provar que elas não pararam… já que, lembre-se, não existe algoritmo para listar os números do castor ocupado. Mais tarde, em 1983, Allan Brady provou que BB(4) é 107. Inexpressivo até agora? Bem, como na sequência de Ackermann, não nos deixemos enganar pelos primeiros números.

Em 1984, AK Dewdney dedicou uma coluna a Scientific American aos castores ocupados, que inspiraram o matemático amador George Uhing a construir um dispositivo especial para simular máquinas de Turing. O dispositivo, que custou menos de US$ 100 a Uhing, encontrou uma máquina de cinco regras que executou 2.133.492 passos antes de parar… BB(5) deve ser pelo menos tão grande. Assim, em 1989, Heiner Marxen e Jürgen Buntrock descobriram que BB(5) é pelo menos 47176870. Até hoje, BB(5) não foi fixado com precisão e pode ser muito maior ainda. Por BB(6), Marxen e Buntrock estabeleceram outro recorde em 1997, provando que era pelo menos 8690333381690951. Uma conclusão formidável, mas Marxen, Buntrock e outros caçadores de castores ocupados apenas caminham nas margens do desconhecido. A humanidade nunca será capaz de saber o valor de BB(6) com certeza, deixemos em paz BB(7) ou qualquer outro número maior na sequência.

De fato, os primeiros competidores de cinco e seis regras já nos escapam: não podemos explicar como eles ‘funcionam’ em termos humanos. Se a criatividade impregna seu design, não é porque os humanos a colocaram lá. Uma maneira de entender isso é que mesmo pequenas máquinas de Turing podem codificar problemas matemáticos profundos. Pegue a conjectura de Goldbach, de que todo número par maior ou igual a 4 é a soma de dois números primos: 10 = 7 + 3, 18 = 13 + 5. A conjectura resiste à prova desde 1742. Poderíamos desenhar uma máquina de Turing com, digamos, 100 regras , que testa cada número par para ver se é uma soma de dois primos, e parar apenas se encontrar um contraexemplo para a conjectura. então sabendo BB(100), poderíamos, em princípio, operar esta máquina por BB(100) passos, vendo se para, e assim resolvendo a conjectura de Goldbach. Não precisamos nos aventurar muito em sucessão para entrar no covil do basilisco.

Pegue os números do castor ocupado, eles estão perfeitamente definidos matematicamente. Se você desafiar um amigo para o desafio de número mais alto, sugiro que escreva algo assim:

Se seu amigo não conhece máquinas de Turing ou similares, mas conhece apenas, digamos, números de Ackermann, então você vence o desafio. Você até ganharia se concedesse ao seu amigo um handicap, e você permite todo o tempo de existência do universo para ele escrever seu número. A chave para o desafio do maior número é um paradigma poderoso, e a teoria da computação de Turing é realmente poderosa.

Mas e se seu amigo também souber sobre as máquinas de Turing? Existe um sistema de notação para grandes números mais poderoso até do que castores ocupados?

Suponha que possamos dotar uma máquina de Turing com a habilidade mágica de resolver o problema da parada. O que poderíamos obter? Teríamos uma ‘máquina super-Turing’: uma com habilidades além de qualquer máquina comum. Mas agora, quão difícil é decidir se um super-máquina se detém? Hmm. Acontece que mesmo as supermáquinas não podem resolver seu ‘problema da super-parada’, pela mesma razão que as máquinas comuns não podem resolver o problema da parada comum. Para resolver o problema de parada para supermáquinas, precisamos de uma máquina inclusive mais poderosa: uma ‘super-hiper-máquina’. E para resolver o problema de parada da super-hiper-máquina, precisamos de uma ‘super-hiper-mega-máquina’. E assim sucessivamente sem fim. Essa hierarquia infinita foi formalizada pelo lógico Stephen Kleene em 1943 (embora ele não tenha usado o termo ‘super-hiper-mega’).

Imagine um romance, que está embutido em um romance maior, que está embutido em um romance ainda maior, e assim por diante até o infinito. Dentro de cada romance, os personagens podem debater os méritos literários de qualquer subromance. Mas, por analogia com as categorias de máquinas que não podem se analisar, os personagens jamais poderiam criticar o romance em que eles mesmos estão. (Isto, eu acho, ridiculariza nossa experiência comum de romances.) Para entender completamente qualquer coisa da realidade, precisamos sair da essa realidade. Essa é a essência da hierarquia de Kleene: para resolver o problema de parada para alguma categoria de máquinas, ainda precisamos de uma categoria de máquinas mais poderosa.

E não há escapatória. Suponha uma máquina de Turing com uma habilidade mágica para resolver o problema da parada, o problema da super-parada, o problema da super-hiper-parada, o problema da super-hipermega-parada, e assim por diante sem fim. Certamente esta será a rainha das máquinas de Turing? Realmente não. Assim que queremos decidir se uma ‘rainha das máquinas de Turing’ para, precisamos de uma máquina ainda mais poderosa: uma ‘imperatriz das máquinas de Turing’. E a hierarquia Kleene continua.

Mas como isso é relevante para grandes números? Bem, cada nível da hierarquia Kleene gera uma sucessão de castores ocupados de crescimento mais rápido do que todos os níveis anteriores. De fato, cada nível da sequência cresce tão rapidamente que só pode ser calculado por um nível superior. Por exemplo, defina BB₂(n) como o número máximo de passos que uma supermáquina com n regras pode fazer antes de parar. Se essa super-sequência de castores ocupados fosse computável por supermáquinas, então essas máquinas poderiam resolver o problema da superparada. Assim, os super-números de castores ocupados crescem rápido demais para serem computados, até se pudéssemos calcular o número normal de castores ocupados.

Você pode pensar que agora, no desafio de maior número, você pode eliminar até mesmo um oponente usando a sequência do castor ocupado digitando algo assim:

Mas não realmente. O problema é que eu nunca vi tais “castores ocupados de alto nível” definidos em qualquer lugar, provavelmente porque, para as pessoas que conhecem a teoria da computabilidade, eles são uma extensão bastante óbvia dos números comuns do castor ocupado. Portanto, nosso razoável matemático moderno não saberia qual número você está nomeando. Se você quiser usar os números do castor ocupado de nível mais alto no desafio de número mais alto, aqui está o que eu sugiro. Primeiro, publique um artigo formalizando o conceito em algum jornal obscuro e de baixo prestígio. Portanto, durante o desafio, cite o item em sua folha.

Para exceder os castores ocupados de nível mais alto, presumivelmente precisamos de algum modelo computacional superior até mesmo às máquinas de Turing. Não consigo imaginar como seria esse modelo. De alguma forma, ainda duvido que a história dos sistemas de notação para grandes números tenha terminado. Talvez um dia nós, humanos, sejamos capazes de nomear concisamente números que façam o castor ocupado 100 parecer tão infantil e divertidamente pequeno quanto os oitenta e três de nosso nobre. Ou se nunca nomearmos esses números, talvez outras civilizações o façam. Está em andamento um desafio em toda a galáxia dos maiores números?

Você pode se perguntar por que não podemos transcender todo o desfile de paradigmas e nomear números por um sistema que abrange e supera todos eles. Suponha que você escreva o seguinte no desafio de número mais alto:

O maior inteiro nomeável com 1000 letras.

Com certeza esse número existe. Usando 1000 letras, podemos nomear apenas um número finito de números, e entre esses números deve haver um maior. E ainda não fizemos referência a como o número é nomeado. O texto poderia invocar números de Ackermann, ou castores ocupados, ou castores ocupados de nível superior, ou mesmo um conceito ainda mais radical que ninguém ainda pensou. Então, a menos que seu oponente use o mesmo truque, nós o derrotamos no soco. Que ideia brilhante! Por que não pensamos nisso antes? Infelizmente isso não funciona. Poderíamos também ter escrito:

Um mais o maior inteiro nomeável com 1000 letras.

Este número precisa de pelo menos 1001 letras para nomeá-lo. Mas nós o nomeamos com apenas 47 letras! Como uma cobra se engolindo inteira, nosso colossal número se dissolve em um tumulto de contradição. O que sobrou? O paradoxo que acabei de descrever foi publicado pela primeira vez por Bertrand Russell, que o atribuiu a um bibliotecário chamado G.G. Berry. O paradoxo de Berry surge não da matemática, mas da ambiguidade inerente da linguagem. Não existe uma maneira segura de converter uma frase sobre o número que ele nomeia (ou para decidir se deve nomear um número de qualquer maneira), e é por isso que invoquei um “matemático moderno razoável” nas regras do desafio do maior número. Para contornar o paradoxo de Berry, precisamos nomear os números usando um sistema de notação matemático preciso, como as máquinas de Turing… que é exatamente a ideia por trás da sequência de castores ocupados. Então, em suma, não há truque astuto de linguagem para superar Arquimedes, Ackermann, Turing e Rado, nenhuma escada real de grandes números. Você também pode perguntar por que não podemos usar o infinito no desafio. A resposta é: pela mesma razão não podemos usar um carro-foguete em uma corrida de bicicleta. O infinito é fascinante e elegante, mas não é um número inteiro. Também não podemos ‘subtrair do infinito’ para produzir um inteiro. Infinito menos 17 ainda é infinito, enquanto infinito menos infinito é indefinido: pode ser 0,38 ou mesmo infinito novamente. Eu realmente deveria estar falando sobre infinitos, no plural. Durante o final do século XIX, Georg Cantor provou que existem diferentes níveis de infinito: por exemplo, a infinidade dos pontos em uma linha é maior que a infinidade dos inteiros. Além disso, assim como não há maior número, também não há maior infinito. Mas a busca por grandes infinitos é mais obscura do que a busca por grandes números. E envolve, não uma sucessão de paradigmas, mas essencialmente um: o de Cantor.

Então aqui estamos nós, na fronteira do conhecimento de grandes números. Como o discípulo de Euclides deve ter perguntado: “Para que ele serve tudo isto?” Vimos que o progresso em sistemas de notação para grandes números reflete o progresso em domínios maiores: matemática, lógica, ciência da computação. E, no entanto, embora um espelho reflita a realidade, não necessariamente a influência. Mesmo dentro da matemática, grandes números são frequentemente considerados trivialidades, seu estudo ocioso entretenimento sem implicações mais amplas. Eu quero argumentar uma visão contrária: que entender grandes números é a chave para entender o mundo. Imagine tentar explicar a máquina de Turing para Arquimedes. O gênio de Siracusa ouve pacientemente enquanto você discute a fita de papiro que se estende infinitamente em ambas as direções, as etapas, estados e entradas e saídas de sequências. Finalmente explode.

“Que tolice!” declara (ou o equivalente grego antigo). “Tudo o que você me dá é uma definição elaborada, sem valor fora de si mesma.”

Como responder? Arquimedes nunca ouviu falar de computadores, aqueles dispositivos meticulosos que, vinte e três séculos depois, comandam os negócios do mundo. Então você não pode reivindicar aplicações práticas. Nem você pode apelar para Hilbert e o programa de formalismo, já que Arquimedes não ouviu falar de ambos. Mas então você percebe: a sucessão do castor ocupado. Você define a sequência para Arquimedes, convencendo-o de que BB(1000) é mais de 10⁶³ grãos de areia enchendo o universo, mais de 10⁶³ elevado ao seu próprio potência 10⁶³ vezes. Você o desafia a nomear um número maior sem invocar máquinas de Turing ou algo equivalente. E enquanto ele pondera sobre esse desafio, o poder do conceito da máquina de Turing o ilumina. Embora sua intuição nunca pudesse apreender os números do castor ocupado, sua razão o compele a reconhecer sua imensidão. Grandes números têm uma maneira de imbuir noções abstratas com a realidade.

De fato, pode-se definir a ciência como o esforço da razão para compensar nossa incapacidade de perceber grandes números. Se pudéssemos correr a 280 milhões de metros por segundo, não haveria necessidade de uma teoria da relatividade especial: seria óbvio para qualquer um que quanto mais rápido fôssemos, mais pesados e agachados nos tornaríamos, e mais rápido o tempo passa no resto do mundo. Se pudéssemos viver por 70 milhões de anos, não haveria teoria da evolução, e certamente sem criacionismo: poderíamos observar a especiação e a adaptação com nossos próprios olhos, em vez de reconstruir minuciosamente os eventos a partir de fósseis e DNA. Se pudéssemos assar pão a 2.000.000 Kelvin, a fusão nuclear não seria o domínio esotérico dos físicos, mas o conhecimento comum e familiar. Mas não podemos fazer nada disso, então temos ciência, para deduzir sobre a gigantesca que nós, com nossas faculdades infinitesimais, jamais sentiremos. Se as pessoas temem grandes números, é de se admirar que também temam a ciência e se voltem para a pequenez reconfortante do misticismo?

Mas as pessoas tem medo dos grandes números? Certamente sim. Encontrei pessoas que não sabem a diferença entre um milhão e um bilhão, e eles não se importam. Jogamos na loteria com ‘seis maneiras de ganhar!’, passando por alto das vinte milhões de maneiras de perder. Bocejamos para seis bilhões de toneladas de dióxido de carbono liberados na atmosfera todos os anos e falamos de ‘desenvolvimento sustentável’ nas garras do crescimento exponencial. Tais casos, parece-me, transcendem a ignorância aritmética e representam a falta de vontade básica de compreender o imenso.

Então, de onde vem o medo de grandes números? Tem origem biológica?

Em 1999, um grupo liderado pelo neuropsicólogo Stanislas Dehaene relatou evidências na Science que dois sistemas cerebrais separados contribuem para o pensamento matemático. O grupo treinou bilíngues russo-inglês na resolução de um conjunto de problemas, incluindo adição de dois dígitos, adição de base oito, raízes cúbicas e logaritmos. Alguns sujeitos foram treinados em russo, outros em inglês. Quando os sujeitos foram solicitados a resolver problemas aproximadamente (para escolher a mais próxima de duas estimativas), eles se saíram igualmente bem em ambas as línguas. Mas quando eles foram solicitados a resolver problemas exatamente, eles se saíram melhor na linguagem de seu treinamento. Além disso, imagens cerebrais mostraram que os lobos parietais dos sujeitos, envolvidos no raciocínio espacial, eram mais ativos durante problemas de cálculo aproximado; enquanto os lobos frontais inferiores esquerdos, envolvidos no raciocínio verbal, foram mais ativos durante os problemas de computação exata. Estudos de pacientes com lesões cerebrais pintam o mesmo quadro: aqueles com lesões parietais às vezes não conseguem decidir se 9 está mais próximo de 10 ou 5, mas lembram da tabuada; enquanto aqueles com lesões no hemisfério esquerdo às vezes não conseguem decidir se 2 + 2 é 3 ou 4, mas sabem que a resposta está mais próxima de 3 do que de 9. Dehaene et al. conjecturaram que os humanos representam os números de duas maneiras. Para o cálculo aproximado, usamos uma ‘linha numérica mental’, que evoluiu há muito tempo e que provavelmente compartilhamos com outros animais. Mas para a computação exata usamos símbolos numéricos, que evoluíram recentemente e, sendo dependentes da linguagem, são exclusivos dos humanos. Essa hipótese explica nitidamente os resultados do experimento: a razão pela qual os sujeitos têm melhor desempenho em sua linguagem de treinamento para computação, mas não para problemas de aproximação, uma vez que o primeiro invoca o lobo de orientação verbal frontal inferior esquerdo e o segundo, o lobo parietal de orientação espacial.

Se a hipótese de Dehaene et al. está correta, então que representação usamos para números grandes? Certamente o simbólico; para ninguém a reta numérica mental pode ser longa o bastante para conter 999, 5 pentado a 5, ou BB(1000). E aqui, eu suspeito, está o problema. Quando pensamos em 3, 4 ou 7, somos guiados por nossa intuição espacial, aprimorada por milhões de anos percebendo 3 gazelas, 4 companheiros ou 7 membros de um clã hostil. Mas quando pensamos em BB(1000), só temos linguagem, essa evolução neófita. Os caminhos neurais usuais para representar números levam a um beco sem saída. E talvez seja por isso que as pessoas têm medo de grandes números.

A intervenção precoce poderia mitigar nossa fobia de grandes números? E se os professores de matemática do segundo ano tirassem uma hora de seu trabalho de casa chato para perguntar a seus alunos “como você nomearia um número muito, muito grande?” E então ele lhes falaria sobre potências e expoentes empilhados, tetração e sucessão de Ackermann, e talvez até castores ocupados: uma cornucópia de números mais vastos do que qualquer um que eles já conceberam, e ideias estendendo os limites de sua imaginação.

Quem pode nomear o maior número? Quem tiver o paradigma mais profundo. Estás pronto? Prepare-se. Já.

Referências

• Alan Turing, ”On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, Series 2, vol. 42, pp. 230- 265, 1936. Reprinted in Martin Davis (ed.), The Undecidable, Raven, 1965.
• Allan H. Brady, ”The Determination of the Value of Rado’s Noncomputable Function Sigma(k) for Four-State Turing Machines,” Mathematics of     Computation, vol. 40, no. 162, April 1983, pp 647- 665.
• A.K. Dewdney, The New Turing Omnibus: 66 Excursions in Computer Science, W.H. Freeman, 1993.
• Carl Sagan, Billions & Billions, Random House, 1997.
• Dexter C. Kozen, Automata and Computability, Springer-Verlag, 1997.
• ——, The Design and Analysis of Algorithms, Springer-Verlag, 1991.
• Donald E. Knuth, Selected Papers on Computer Science, CSLI Publications, 1996. Chapter 2, ”Mathematics and Computer Science: Coping with Finiteness,” pp. 31- 57.
• Douglas Hofstadter, Metamagical Themas: Questing for the Essence of Mind and Pattern, Basic Books, 1985. Chapter 6, ”On Number Numbness,” pp. 115- 135.
• Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999. Entry on ”Large Number” at http://www.treasure-troves.com/math/LargeNumber.html.
• Gregory J. Chaitin, ”The Berry Paradox,” Complexity, vol. 1, no. 1, 1995,     pp. 26- 30. At http://www.umcs.maine.edu/~chaitin/unm2.html.
• Heiner Marxen, Busy Beaver, at http://www.drb.insel.de/~heiner/BB/.
• —— and J¨urgen Buntrock, ”Attacking the Busy Beaver 5,” Bulletin of the     European Association for Theoretical Computer Science, no. 40, February 1990, pp. 247- 251.
• Ilan Vardi, ”Archimedes, the Sand Reckoner,” at http://www.ihes.fr/~ilan/sand_reckoner.ps.
• Michael Somos, ”Busy Beaver Turing Machine.” At http://grail.cba.csuohio.edu/~somos/bb.html.
• Petr Beckmann, A History of Pi, Golem Press, 1971.
• Robert Kanigel, The Man Who Knew Infinity: A Life of the Genius Ramanujan, Washington Square Press, 1991.
• Rudy Rucker,     Infinity and the Mind, Princeton University Press, 1995.
• Shen Lin and Tibor Rado, ”Computer studies of Turing machine problems,” Journal of the Association for Computing Machinery, vol. 12, no. 2, April 1965, pp. 196- 212.
• Stephen C. Kleene, ”Recursive predicates and quantifiers,” Transactions of the     American Mathematical Society, vol. 53, 1943, pp. 41- 74.
• S. Dehaene and E. Spelke and P. Pinel and R. Stanescu and S. Tsivkin, ”Sources of Mathematical Thinking: Behavioral and Brain-Imaging Evidence,” Science, vol. 284, no. 5416, May 7, 1999, pp. 970- 974.
• Tibor Rado, ”On Non-Computable Functions,” Bell System Technical Journal, vol. XLI, no. 2, May 1962, pp. 877- 884.