ÁRVORE (3) é um grande número, quero dizer realmente grande.

Mente suficientemente soprada.

Josh Kerr Blocked Unblock Seguir Seguindo 27 de março de 2016

Eu gosto de números realmente grandes. Quando eu digo "realmente grande" eu não quero dizer números como um milhão ou um bilhão, quero dizer números como o número de Graham que é tão grande que se você tentasse armazenar cada dígito em seu cérebro, ele se tornaria um buraco negro antes que você pudesse colocar tudo lá. Ou dito de outra maneira, um buraco negro do tamanho do seu cérebro armazena menos informação do que números no número de Graham. O número e os números de Graham são tão grandes que, se você escrevesse um dígito em cada átomo de todo o universo conhecido, ficaria sem átomos antes de reduzir o número. Mente explodida.

Essas simples comparações estão apenas revelando por que os grandes números são tão interessantes para mim. O estudo dos grandes números é como estudar os limites do nosso universo e o que está além. Os dígitos que compõem esses números não podem ser conhecidos porque nosso universo não é grande o suficiente para expressá-los todos. Ainda assim, os matemáticos são capazes de estudar esses números e, mais importante, as funções que os criam.

Para criar esses números gigantescos, você precisa criar funções de crescimento rápido que os gerem de maneira eficiente. Muitas dessas funções já são familiares para você, como adição, multiplicação e exponenciação. Os matemáticos criaram novas funções que escalam muito mais rapidamente para números maiores e para essas funções que eu acho tão interessantes.

Antes de entrar, preciso primeiro avisá-lo de que não sou matemático, então, por favor, não considerem o conteúdo deste post nada além de um discurso de alguém interessado no assunto. Eu não tenho nenhum conhecimento profundo ou experiência nesses assuntos (o que deve ser óbvio para qualquer um que faça isso).

Finja que há um concurso para ver quem poderia escrever o maior número em um quadro branco. Se você foi primeiro o que você escreveria?

Você poderia escrever 999999999 e preencher todo o quadro branco com 9's. Você acabaria com um número realmente grande. No entanto, se você escrever um monte de 1s em vez de 9s, você terá um número ainda maior porque 1 ocupa menos espaço que os 9s, então você encaixaria mais dígitos no tabuleiro.

Um concurso semelhante realmente aconteceu no MIT em 26 de janeiro de 2007. O evento foi criado para receber alunos de graduação interessados em teoria computacional e me interessou em grandes números. Eu realmente escrevi sobre isso em um artigo que se tornou um dos artigos mais populares no meu blog, mas eu divago.

Duelo Big Number
forall R {{para qualquer fórmula (codificada) [?] e qualquer atribuição de variável t (R (([?] = `x_i ? x_j '? t (x_1) ? t (x_j)) ? ([?]… web. mit.edu

Para entender a função TREE você deve primeiro entender algumas das funções que criam grandes números. Uma das minhas funções favoritas é a notação de seta para cima de Knuth. Esta função faz exponenciação iterada e permite que você construa grandes números rapidamente. Se você não estiver familiarizado com o funcionamento, recomendo dar uma olhada no artigo da Wikipedia.

Notação de seta para cima de Knuth
Em matemática, a notação de seta de Knuth é um método de notação para inteiros muito grandes, introduzido por Donald Knuth… en.wikipedia.org

Aqui está uma simples progressão da notação de seta para cima de Knuth:

Alterar o 2 para um 3 produzirá um número ainda maior:

Adicionando mais um para torná-lo um 4 faz este grande número ímpio:

Com a notação de seta para cima, você deve ter uma noção da rapidez com que esses números podem crescer. Adicione uma flecha extra e as rodas saem do ônibus. Aqui está com três flechas:

Vamos adicionar mais um ao 2 para torná-lo um 3 e ver o que recebemos:

Esse número deve tirar suas meias. A coisa surpreendente sobre essa sequência é que com apenas três flechas para cima e o número 3 nós criamos esse monstro de um número. No entanto, esse número não chega nem perto do número de Graham. Para chegar ao número de Graham, precisamos adicionar mais flechas. Você viu no exemplo anterior o que aconteceu quando adicionamos mais setas. O número cresceu muito maior muito mais rápido. Isso acontece por causa da natureza recursiva da função. Ele coloca a resposta do cálculo anterior no slot mais poderoso da equação. Neste caso, o expoente.

Para chegar ao número de Graham, precisamos de mais flechas:

Então o número de Graham requer quatro flechas para começar. Mas isso só nos dá o primeiro dos 64 níveis. Então pegamos a resposta de cada nível e a usamos para definir o número de setas no próximo nível:

Agora estamos falando de um número insanamente grande. O primeiro nível do G1 já é tão grande que não podemos escrevê-lo. O G2 pega a resposta do G1 e adiciona várias setas para cima para fazer o G2. Então G2 se torna o número de flechas para cima para G3 e continuamos até chegarmos a G64. Uau.

A notação de seta para cima cresce rapidamente e pode criar alguns números muito grandes. No entanto, existem funções que crescem mais rapidamente do que a notação de seta para cima de Knuth. Por exemplo, a notação Conways Chained Arrow:

Notação de seta Conway acorrentado
A notação de flecha encadeada por Conway, criada pelo matemático John Horton Conway, é um meio de expressar certas… pt.wikipedia.org

Conways notação de flecha encadeada permite que você construa cadeias que através de recursão crescem mais rápido do que a notação de seta para cima. Você deve dar uma olhada no artigo da Wiki que eu vinculei antes de ler o restante deste artigo, se você não entender como ele funciona. Eu tentaria explicar isso neste artigo, mas não poderia fazer justiça.

Na notação de seta para cima de Knuth, vimos que o número de Graham não poderia ser representado porque estávamos lidando com tantas flechas que não poderíamos usar essa notação para escrever tudo. Mesmo se começássemos a escrever flechas no começo do universo, não teríamos feito nenhum dano – e isso é apenas com as flechas. Nós nem começamos a avaliar o número real ainda. Com a notação de seta encadeada Conways, por outro lado, podemos escrever um número que é uma aproximação muito próxima do número de Graham:

Então o número G de Graham fica entre esses dois números encadeados.

O número de Graham é na verdade um número muito pequeno comparado com TREE (3). Quero dizer, é tão pequeno que poderia ser 1. Demorei alguns meses estudando antes de começar a entender como a função TREE funcionava. A série de vídeos do matemático e professor David Metzler no YouTube me ajudou a entender a progressão de grandes números:

Eu recomendo assistir a esta série de vídeos. Existem cerca de 21 vídeos e cada um tem cerca de 20 a 30 minutos de duração. David passa por cada função demonstrando como ela funciona e por que produz grandes números. Eventualmente, ele aborda ÁRVORE (3).

Qual é a função TREE?

A função TREE é complicada. A essência é que a função retorna a maior sequência de árvores que você pode construir, dada uma entrada do número de diferentes tipos de sementes que você pode usar para construí-las. Também possui algumas regras que descrevem como você constrói essas sequências de árvores.

Teorema da Árvore de Kruskal
Em matemática, o teorema da árvore de Kruskal afirma que o conjunto de árvores finitas sobre um conjunto de etiquetas bem-ordenado é… en.wikipedia.org

ÁRVORE cresce muito rapidamente. Olhando para 1 e 2 como entradas não mostra nada impressionante, mas conecte um 3 e boom!

ÁRVORE (1) = 1

ÁRVORE (2) = 3

ÁRVORE (3) = número tão grande que supera o número de Graham.

Quando vi o quão rápido crescia, queria entender como funcionava. Eu precisei de ajuda, então voltei para o Stack Exchange. Eu postei um artigo pedindo ajuda:

Como Tree (3) cresce para ficar tão grande? Precisa de explicação leiga.
Eu não sou um matemático, mas estou interessado em grandes números. Eu acho que eles são realmente interessantes, quase como um deus. Eu… math.stackexchange.com

Esta foi a primeira vez que publiquei uma pergunta no Math.Stack Exchange, por isso fiquei surpreendido por obter uma resposta – uma resposta fantástica – e tão rapidamente. A resposta veio de Deedlit, que acredito ser um professor que dedica seu tempo à Teoria dos Gráficos. Sua resposta foi detalhada, longa e me ajudou a entender a função. Por alguns momentos entendi o poder da ÁRVORE.

A explicação realmente leiga para o porquê da TREE (3) é tão grande é assim. A função TREE (n) retorna a árvore mais longa possível feita com N elementos que seguem regras muito específicas. Essas regras garantem que a sequência de árvore mais longa resultante seja finita. Quando a entrada é 1 ou 2, o comprimento da maior árvore possível é pequeno. Quando é 3, o comprimento é muito muito longo. ÁRVORE (3) supera grandes números como o número de Graham.

Grandes números como o número de Graham são impossivelmente grandes, maiores que o nosso universo. De certo modo, isso significa que a compreensão desses números nos ajudará a entender algo que vai além do nosso universo. Há uma qualidade piedosa no estudo dos grandes números. Há muito poucas coisas no mundo que me surpreendem, como ter um vislumbre da escala e do tamanho desses grandes números. Você não pode realmente saber o quão grande eles são, mas quando você tem um gosto, oh rapaz é doce.

Se você está interessado em grandes números, um ótimo lugar para começar é o wiki da Googology:

Googology Wiki
Esta não é a única maneira de acessar o canal de IRC! Você deve obter um cliente adequado como o mIRC (Windows… googology.wikia.com

Os matemáticos mais brilhantes do mundo estão lá, elaborando artigos e discussões sobre grandes números e as funções que os produzem. Espero que este artigo tenha inspirado você a aprender mais sobre grandes números. Se você achar interessante este artigo, por favor, recomende-o e deixe-me um feedback.