Mente soprada: a hierarquia crescente para leigos – também conhecidos como números enormes

Postado por joshkerr 7 de outubro de 2016 1º de fevereiro de 2019 Deixe um comentário sobre Mind blown: a hierarquia crescente para leigos – também conhecidos como números enormes

AVISO – Eu não sou um matemático, então eu provavelmente fiz um monte de erros. Por favor, deixe as correções nos comentários.

O universo

Há alguns anos me deparei com um artigo do famoso cientista da computação e especialista em física quântica, Scott Aaronson, intitulado “ Quem pode nomear o número maior? O artigo inspirou uma disputa entre dois filósofos do MIT para ver quem poderia nomear o maior número. Eu escrevi anteriormente sobre este concurso aqui .

O artigo de Scott gerou meu interesse em grandes números. Você consegue imaginar algo tão grande que transcende nosso Universo? Ao contrário da física, que é baseada em nosso mundo físico, os números grandes são puramente abstratos. Não podemos escrevê-las porque não há matéria suficiente no Universo para armazenar cada dígito. Algumas pessoas nem acreditam que elas existem. Ainda assim, grandes números são importantes, e os matemáticos os usam em provas e para classificar a força computacional de vários sistemas matemáticos.

Para adquirir uma compreensão profunda desta área da matemática requer conhecimentos sobre teoria dos números e teoria dos conjuntos que eu não tenho. Ainda assim, estou interessado nesses assuntos e dediquei tempo a este artigo para estimular o seu interesse também.

Aquecer

Se você fosse participar do concurso de Scott para nomear o maior número, o que você escreveria? A maioria das pessoas provavelmente escreveria googol. O mecanismo de busca ficou famoso por ter esse nome. É um Seguido por zeros. Quando escrito, parece com isso:

Um googol é um 1 seguido por 100 zeros

Essa seria uma boa resposta para a maioria das pessoas. Se você enfrentasse um matemático, seria trucidado.

No exemplo do googol, era difícil escrever esse número porque ele tem muitos zeros nele. Felizmente, inventamos vários sistemas para escrever grandes números. Por exemplo, usando expoentes, podemos escrever o googol assim:

Durante a maior parte deste artigo, usaremos várias formas de notação ordinal para escrever números cada vez maiores. Eu farei o meu melhor para explicá-los como eu os entendo. Parte da mágica na compreensão dos grandes números está acompanhando enquanto ascendemos a números cada vez maiores.

Para o googol, é fácil ver o tamanho dele porque você pode ver todos os seus dígitos. Escrevê-lo em forma exponencial faz com que pareça ainda menor. Googol não é pequeno.

Quão grande é o googol?

Imagine um aquário do tamanho do universo conhecido

A melhor maneira de visualizar o tamanho do googol é fingir que poderíamos preencher todo o universo com grãos de areia. Imagine um tanque de peixes com 46 bilhões de anos-luz em cubos. Agora conte cada grão de areia no aquário do tamanho do universo. Sua contagem é menor que o googol. Você precisaria de outros 10x grãos de areia para alcançar o googol. A magnitude desse número é incrível.

O Googol parece ser um grande número, mas comparado aos números que virão mais adiante neste artigo, é infinitamente pequeno. Dada uma escala de zero a infinito, o googol é muito próximo de zero em comparação com os números sobre os quais estamos prestes a falar. Como não podemos visualizar o tamanho desses números, usaremos uma escala chamada Fast Growing Hierarchy (FGH) para classificá-los.

O FGH é baseado em funções de crescimento rápido com a função mais lenta na parte inferior e funções mais rápidas conforme você sobe na hierarquia. Grande parte deste artigo descreverá essas funções e a velocidade com que elas crescem. Mostrarei como podemos escrevê-las com mais eficiência e fazer expansões para algumas das mais populares. As expansões ajudam você a ter uma idéia do poder dessas funções inserindo números pequenos para ver as saídas massivas. Em muitos casos, não serei capaz de fazer as expansões completas porque os números ficam muito grandes ou piores, existem infinitamente muitos passos para expandi-los.

Essa coisa me surpreende e espero que também exploda a sua.

A Hierarquia do Crescimento Rápido é a nossa vara de medição

Nós começamos esta viagem louca introduzindo funções. As funções são fáceis de entender, elas recebem dados, seguem algumas regras e produzem resultados. Quando você pensa em uma função que aumenta rapidamente os números, provavelmente pensa em exponenciação. Nós o usamos em nossas vidas diárias e os resultados podem ser facilmente visualizados. A Hierarquia de Crescimento Rápido é composta de uma série de funções crescentes cada vez mais rápidas. Tudo começa com a sucessão, passa para a adição, depois multiplicação, etc. Cada barra superior na escada do FGH representa uma função de crescimento mais rápido.

Passos de bebê

Nível 1: Sucesso

O sucesso é a função mais básica. Ele pergunta, qual é o próximo item maior na lista? Parece assim quando se trabalha com os números naturais:

Sucessor

Não subestime o poder dessa função. Pode ser chamado recursivamente para gerar funções mais poderosas como adição, multiplicação e até exponenciação. A recursão é a chave de como as funções no FGH funcionam tão efetivamente para produzir números monstruosos. A recursão funciona, permitindo-nos chamar uma função que pode então chamar-se. Ele pode continuar fazendo isso até que seja feito.

Um exemplo fácil de recursão é visto com a função sucessora. Se você quiser gerar o número 5 e começar com o número 1, basta chamar a função successor – que se chamaria 4 vezes para incrementar 1 a 5. A recursão é muito poderosa, como você verá rapidamente. Em seguida é a multiplicação.

Nível 2: multiplicação (mais ou menos)

A multiplicação é definida como adição repetida que está usando chamadas repetidas para a função sucessora.

Em geral, à medida que subimos o FGH, veremos que cada degrau mais alto na escada usa chamadas de funções recursivas para o degrau anterior. Uma maneira mais geral de escrever isso é:

Se quiséssemos fazer uma expansão simples no nível 2, ficaria assim:

Este padrão continuará por um tempo com cada passo acima do FGH. Em seguida é exponenciação:

Nível 3: Exponenciação

A exponenciação é definida usando multiplicação repetida. Não parece poderoso à primeira vista, mas se você olhar para alguns exemplos, você verá o contrário.

Ou que tal este:

Esse número tem 33 dígitos. Já é um grande número e estamos apenas começando no nível 3 no FGH.

Escrever esses números listando todos os seus dígitos ocupa muito espaço. Se continuarmos assim, rapidamente ficaremos sem espaço.

Notação de seta para cima de Knuth

Donald Knuth concebeu a notação de setas como uma maneira de usar menos símbolos para escrever números maiores. Dê uma olhada neste problema simples usando exponenciação:

Exponenciação

Existe uma maneira de expandir a exponenciação e construir torres de expoentes. Isso é chamado de tetração. Aqui está um exemplo:

Tetration

Observe a rapidez com que o número cresce quando adicionamos mais 3 à torre? Esse número já é 1000 vezes o tamanho da população mundial. É cerca de um décimo do número de células em um corpo humano.

Células no corpo humano

Podemos continuar adicionando mais números à torre para obter números ainda maiores. Depois de um tempo isso fica chato porque você acaba com uma torre ridiculamente grande. Por exemplo:

Imagine uma pilha de 3 's 1000 de altura.

E se quiséssemos uma série de torres de energia de 3 e assim por diante? Subir o FGH sem ter uma boa maneira de descrever rapidamente as operações de nível mais alto é difícil. É aqui que a notação de seta é útil. Em vez de escrever todos esses expoentes, podemos usar flechas. Cada seta para cima é um nível mais alto de potência operacional. Produz números massivamente maiores que o nível anterior. Aqui está uma simples progressão da notação de seta para cima:

Uma flecha é a exponenciação

O primeiro dígito é a base, depois a seta ou setas e, em seguida, o número de vezes que você deseja executar a operação. Portanto, neste caso, a base é 2 e você deseja executar a operação 3 vezes com uma seta para cima. (Uma seta para cima é exponenciação.)

Duas flechas é tetration

Vamos tentar três setas para cima:

Três setas é pentation

Indo de duas flechas para cima para três flechas para cima levou o número de 16 para 65536. Isso é chamado de pentation. Vamos tentar novamente com quatro setas para cima:

Quatro setas é hexação

Este já é um número monstruoso e ainda temos uma operação de seta dupla que ainda não foi avaliada. Outra maneira de escrever isso é:

Para lhe dar outro quadro de referência, vamos ver onde um googolplex se encontra em termos de notação de seta para cima. Como você sabe:

Outra maneira de pensar em googoleplex é aumentar para um googol. É um grande número. Com a notação de seta para cima, é onde encontramos o Googolplex:

Um googolplex está, na verdade, mais próximo do limite inferior, mas essa é uma boa maneira de entender o quão grande ele é em termos de notação de seta para cima.

Outro exemplo que mostra o poder da notação de seta para cima:

Nós ainda não expandimos esse número todo o caminho

Uau, temos um grande número aqui. Olhe isto deste modo:

Ou você poderia ver isso dessa maneira. É uma torre de três 7,6 trilhões de altura 3.

Este número já é tão grande que não temos capacidade de entendê-lo. Nada no mundo é tão numeroso. Mesmo se fôssemos embaralhar todas as partículas do universo conhecido, não poderíamos nos aproximar desse número.

Eventualmente, chegaremos ao número de Graham, que será abordado mais adiante neste artigo. O número de Graham é construído em níveis de setas que começam em:

A hexação é poderosa

e cresce descontroladamente. Você verá mais desta beleza mais adiante no artigo.

Toddlers

A primeira função do FGH é o sucesso, o segundo é a multiplicação, o terceiro é a exponenciação, vamos dar uma olhada no quarto da série. Isso é chamado de tetração.

Nível 4: Tetration

Pense em tetration como uma exponenciação iterada. A maneira como a exponenciação agrupa uma série de problemas de multiplicação, a tetration agrupa uma série de problemas de exponenciação. Vamos começar a usar a notação de seta para discutir a força de cada função à medida que avançamos no FGH.

Tetration. Está chamando recursivamente a função de exponenciação.

Deixe-me impressionar a força dessa função mostrando um exemplo:

Como isso é para grande?

Com n = 3, obtemos um número massivo. Você nem quer saber como é o n = 4. O próximo nível é chamado de pentation.

Nível 5: Pentation

Pentation é uma iteração de tetration. É uma série de problemas de tetration agrupados. Pense nisso como uma série de torres de energia. É um pouco mais poderoso que o triplo das flechas que, como vimos anteriormente, cresce insanamente rápido.

Pentation

Em seguida, Hexation. Este é mais importante porque neste nível podemos construir o número de Graham que, como mencionei anteriormente, é um grande número famoso. Também é um monstro de um número.

Nível 6: Hexação

Hexation

A hexação é uma pentação iterada. Então, assim como nos exemplos anteriores, estamos realizando uma série de operações de pentation e agrupando-as.

Podemos continuar aumentando o nível em um, mas levará muito tempo para chegar onde queremos ir. Em vez disso, podemos ir adiante e generalizar a fórmula para determinar o poder de cada degrau no FGH:

Como você viu na minha explicação da notação de seta para cima, cada seta adicional aumenta o resultado em uma quantidade muito grande. À medida que subimos mais no FGH, vemos números cada vez maiores. Vamos precisar de um número cada vez maior de setas para cima para representá-las.

Por exemplo:

O FGH aos 15 anos produz um número perversamente grande. Basta olhar para todas essas flechas! Ainda assim, este é um número relativamente pequeno para onde estamos indo.

Diagonalização

Podemos ver que a recursão é a chave para gerar esses grandes números e que à medida que subimos o FGH, a recursão se torna mais poderosa. Existe mais alguma coisa que podemos fazer para tornar essas funções mais rápidas? Sim. Diagonalização Este conceito é um pouco abstrato, mas é assim.

Se fôssemos calcular todos os valores da função, ficaria assim:

Tabela mostrando diagonalização

A tabela obviamente iria para o infinito em cada direção, mas isso dá uma idéia de como as funções seriam. E se fôssemos pegar a diagonal dessa grade? Acabaríamos com um conjunto que se parece com isso:

Isso é chamado de diagonalização. Vamos tentar um exemplo para mostrar o quão poderoso isso é combinado com a recursão. À primeira vista, isso não parecerá muito poderoso:

Em n = 4 a função não é muito impressionante. No entanto, quando você aumenta para n = 1000, você verá uma história totalmente diferente:

Esmaga o original. A diagonalização é uma maneira muito poderosa de gerar funções de crescimento muito rápido.

Vamos voltar ao FGH e ver se podemos gerar números ainda maiores com funções de crescimento mais rápido. Até agora, usamos números inteiros positivos para representar o índice de cada nível até o FGH. Podemos resumir isso criando uma sequência fundamental que se parece com isso:

FGH como um conjunto de funções crescentes

Essa sequência iria para o infinito. Este conjunto é chamado de sequência fundamental para os números naturais. Como podemos ir além dos números naturais do FGH? É mesmo possível? Pode apostar. No entanto, requer alguma explicação de um tipo especial de infinito chamado omega: ?.

Pré-adolescentes

O conjunto de todos os números naturais

Ao estudar grandes números, você eventualmente encontrará ?. É comumente escrito como:

Omega – o ordinal representando o conjunto de números naturais

? é um conceito muito interessante porque representa o primeiro ordinal infinito depois dos números naturais. Mais especificamente, é um ordinal que é identificado com o conjunto de números naturais. ? é um ordinal, mas é um ordinal especial chamado ordinal transfinito.

Não há como adicionar números naturais, multiplicá-los ou qualquer outra operação primitiva neles para alcançar ?. É chamado de número inacessível porque não pode ser acessado por baixo. É o menor infinito maior que os números naturais.

Outra propriedade importante de ? é que é um ordinal. Isso significa que os números contidos no conjunto representado por ? são ordenados. Sua ordem é importante porque podemos adicionar 1 a ? para alcançar algo maior que ?:

O que acontece quando adicionamos 1 a ?? Nós entendemos isso:

Isso significa que tomamos ? e adicionamos outro conjunto que simplesmente tem o número 1 nele. ? + 1 é um ordinal maior que apenas ? por si só, porque representa um conjunto maior que ?.

Para fins de mostrar o crescimento da hierarquia de crescimento rápido, trataremos a adição com ? assim:

Isso é importante porque podemos usar as propriedades de ? para definir funções de crescimento ainda mais rápidas.

Ômega: ?

? é importante na definição do FGH porque nos permite definir funções de crescimento significativamente mais rápidas. Lembre-se, podemos pegar um índice arbitrariamente grande para m como:

Podemos subir cada vez mais com os números inteiros positivos indexados. E se quisermos ir mais alto que isso? Lembre-se, os números naturais são infinitos. É aqui que vem a calhar. Podemos escrever ? no subscrito:

Isto é completamente válido e um ponto importante na hierarquia crescente. Em termos de velocidade de crescimento usando ? no subscript cria uma função que cresce exatamente como a que criamos anteriormente:

É aqui que a função de diagonalização que criamos anteriormente entra em ação. Existe uma função famosa chamada de função Ackermann, que cresce a este ritmo.

Então, como você expandiria essa função? Da mesma forma que fizemos antes, tomando o item n na sequência fundamental:

Aqui está outro exemplo:

Podemos ir maior do que ?? Claro, podemos adicionar 1 a ele:

Se você se lembra, a sequência fundamental para ? ficou assim:

Como seria a sequência fundamental em ? + 1? É fácil, basta adicionar um a cada item no conjunto:

FGH em ômega + 1

Observe que o conjunto começa em 1 em vez de zero e inclui ? no final? Não é óbvio no início, mas este conjunto cresce significativamente mais rápido do que apenas ?. Por exemplo:

Você já pode ver como ? + 1 irá gerar números significativamente maiores do que o que obtivemos com apenas ?. Nós nem sequer começamos a avaliar os dois ?s externos e já temos esse monstro de um número com n = 3.

No FGH, ? + 1 cresce muito rapidamente. Na verdade, ele cresce rápido o suficiente para criar o número de Graham, que mencionei várias vezes antes, mas ainda não descrevi. Este é um bom lugar para fazer um desvio.

Número de Graham

Ron Graham

O número de Graham é um dos grandes números mais famosos da matemática. Por um tempo, foi o maior número já usado em uma prova. Isso não é mais o caso, mas ainda é uma lenda. O número é o limite superior de um problema na Teoria de Ramsey. Eu não vou detalhar o problema, mas você pode ler mais sobre isso na página do Wiki.

Podemos definir o número de Graham usando algumas das funções que já definimos. Entender esse número ajudará você a perceber como essas funções crescem rapidamente. O número de Graham é um ótimo marcador nesse sentido. É também um grande número em tamanho.

Usando a notação de seta para cima, vamos construir o número de Graham. Primeiro começamos com isso:

Nós já analisamos o G1 anteriormente quando falamos sobre a notação de seta para cima de Knuth. O G1 já é um número gigante. Com o número de Graham, este é o primeiro passo. Para o segundo passo, pegue o resultado de G1 e use-o para determinar quantas flechas para cima estão no G2:

Continuamos fazendo isso até o G64. Toda a progressão se parece com isso:

Isso te dá o número de Graham. Outra maneira de escrever é:

Se fôssemos escrever o número de Graham usando a hierarquia crescente, diríamos que é por aí:

O número de Graham é muito grande. Se você tentasse armazenar todos os seus dígitos em seu cérebro, sua cabeça se transformaria em um buraco negro antes de memorizar todos os dígitos. Dito de outra forma – um buraco negro do tamanho da sua cabeça armazena menos informações do que números no número de Graham.

Há muitos ótimos vídeos no YouTube sobre o número de Graham. Eu particularmente gosto do vídeo Numberphile:

Este vídeo me deixou entusiasmado com grandes números e começou minha viagem pelo buraco negro escuro. Vamos voltar para a hierarquia crescente.

Adolescentes

Indo grande com omega

? + 1 no FGH resultou em uma função de crescimento muito rápido. Podemos continuar adicionando ao ? para criar funções de crescimento mais rápido:

Deixe-me mostrar um exemplo para que você possa ver quanto mais rápido ? + 2 cresce em comparação com ? + 1:

Sabemos do exemplo anterior que n = 3 em ? + 1 resulta em um número massivo. Agora insira esse número massivo nessa função para obter:

Então você pode ver que as coisas estão ficando um pouco ridículas à medida que expandimos esse número. O que você está vendo é o poder da recursão e da diagonalização. ? + 2 é uma função de crescimento muito mais rápida que ? + 1. É muito maior que poderíamos dizer:

Se você der uma olhada na função, o poder real que gera números grandes está no índice da função, não no valor de n . O exemplo acima enfatiza que cada índice crescente é um salto significativo no poder e produz números muito maiores.

Nós podemos continuar daqui. Por exemplo:

Observe que podemos adicionar ? + ?? Isso cria outra sequência fundamental. A sequência é assim:

Agora podemos diagonalizar sobre isso para obter uma função muito poderosa. Vamos tentar um exemplo:

Assim como nos exemplos anteriores, n determina qual índice na sequência fundamental usamos para avaliar a função. Existem outras maneiras de pensar em ? + ?:

Podemos adicionar mais ?'s para obter sequências mais altas no FGH. Por exemplo, todos são válidos:

A sequência fundamental para ?² é:

Um exemplo de expandir alguns de ² é um pouco mais complicado:

Podemos continuar indo mais alto com:

? ^ ? também tem uma sequência fundamental que se parece com isso:

Vamos tentar um exemplo:

A expansão é um pouco complicada, mas dá uma ideia do tamanho desse número. Se fôssemos fazer mais uma expansão, ficaria assim:

Se você se lembra de quão grande era ? + 1, você pode ver que ? ^ ? é um monstro. Podemos continuar aumentando adicionando mais ômegas à torre de energia de ?. Na verdade, podemos ir até uma infinidade de ?'s:

Adultos jovens

Estamos agora em um ponto muito especial sobre o FGH. Chegamos ao nosso segundo ordinal transfinito. É chamado Epsilon Naught: ?0.

Como nos recordamos, o limite para o conjunto infinito de números naturais foi ?. Se fôssemos construir um conjunto de todas as ordenações possíveis de ?:

Então, ?0 é o limite de todas as ordenações possíveis de ?. ?0 também é importante porque é o primeiro ponto fixo que satisfaz a equação de:

Este é um pequeno resumo, mas o que isso significa é que se você adicionar outro ? ao topo da pilha infinita de ?s, você obterá a mesma resposta, porque adicionar mais um ? ao topo não altera o número. O número já está no infinito, então adicionar mais um não o altera.

Também Epsilon Naught

Epsilon nada: ?0 é maior que qualquer ordinal que pode ser nomeado usando adição, multiplicação e exponenciação usando o símbolo ?. Pense nisso como uma torre de energia infinita de ?. Tudo além deste ponto é não computável.

Expansão funciona da mesma maneira que funciona com ?. Nós indexamos a sequência fundamental de ?0 e depois expandimos. Aqui está um exemplo simples:

Outra expansão com n = 6 seria assim:

Como conseguimos uma função mais rápida que ?0? Se não podemos adicionar mais ?'s à pilha, parece que estamos presos. Certo? Errado. Podemos incrementar ?0 assim como fizemos com ?:

Adicionar um 1 ao índice aumenta drasticamente o tamanho dessa função

Vamos tentar um exemplo com (?0 + 1):

Vamos ficar maiores. Aqui estamos levantando (?0 + 1) para ?:

Este exemplo sugere outra sequência fundamental. Este se parece com isso:

Você pode pensar nesta seqüência como uma torre infinita de ? com um (?0 + 1) no topo:

Estamos presos novamente? Se adicionarmos mais infinitos ou mais ?0, obteremos a mesma coisa. Então, como vamos crescer? Como sobre ?1? Aqui está a sequência fundamental para isso:

Quão alto o FGH somos neste momento? Alto. Estamos gerando números colossais com essa função. Vamos tentar expandir um exemplo com ?1:

Nós já sabemos como expandir este número com base no exemplo anterior e como você pode ver, ?1 constrói um número muito maior do que qualquer coisa que vimos em ?0. Como vimos, cada passo acima do FGH constrói números significativamente maiores.

Podemos continuar aumentando usando a próxima sequência fundamental:

Nós podemos continuar assim. Cada próximo índice é uma função ridiculamente crescente que produz números que confundem a mente. Podemos até ligar um ?:

Lembre-se que ? nos permitiu obter índices maiores depois que usamos todos os inteiros positivos. Com ? a mesma estratégia é verdadeira. Então, fazer um exemplo com ? no índice produziria:

Podemos até ter aninhamentos de épsilons no índice. É complicado explicar, mas lembre-se de que o índice é onde está o poder de crescimento dessas funções. Portanto, adicionar epsilons aninhados produziria uma função muito mais poderosa. Por exemplo:

Isso é perfeitamente válido. Isso também nos leva à nossa próxima sequência fundamental, que também é um ponto fixo importante no FGH:

?0 cria grandes números perversos. Semelhante a ?0, satisf0 satisfaz a equação:

Isso significa que adicionar outro nível de epsilon não altera o valor de ?0. É como a pilha infinita de ?. Adicionar outro não muda ?0. Da mesma forma, ?0 é uma pilha infinita de ?, portanto, adicionar outro não irá alterá-lo.

Vamos tentar um exemplo:

À medida que expandimos ?0, podemos ver algumas funções muito pesadas se formando. Imaging expandindo isso até os dígitos reais?

Para ir além de ?0, precisamos fazer exatamente a mesma coisa que fizemos com ?. Nós adicionamos 1. Então nós temos:

E um exemplo que deve parecer familiar:

Sabemos como mass0 massivamente grande é onde n = 3, então você pode imaginar quão grande é esse número quando a entrada é a saída da função ?0 anterior.

Vamos continuar. Podemos facilmente construir ?1 a partir da próxima sequência fundamental.

Vamos tentar um exemplo rápido:

Quebrar o zeta 1 levará muito tempo

Podemos continuar indo mais alto com os zetas, assim como fizemos com os epsilons. Eventualmente chegamos à sequência fundamental:

Isso é chamado de eta nada: ?0. Nós construímos de forma semelhante à forma como construímos ?. O tamanho dos números gerados por essas funções é incompreensível. Eles são enormes.

Para recapitular, geramos esses números grandes usando funções representadas por letras em grego:

Símbolos representam conjuntos infinitos cada vez maiores

Para cada degrau do FGH, usamos uma nova letra grega para representar uma função cada vez mais poderosa. Em algum momento vamos ficar sem letras gregas. Isso significa o limite para o FGH? Não, não tem.

A resposta para esse problema é a função Veblen, que aproveita mais eficientemente os ordinais para indexar as funções. Então podemos criar um número infinito deles. Como resultado, podemos subir mais alto na escala de funções de rápido crescimento e gerar números maiores. A função Veblen é um pouco mais complicada do que eu descrevi até agora, então vamos precisar de outro desvio.

Adultos

Funções Veblen

Oswald Veblen

Criado por Oswald Veblen em 1908, a função Veblen é o método de mapeamento de ordinais para os ordinais. A Veblen Hierarchy é uma lista de funções que representam pontos fixos. Semelhante à forma como atingimos um ponto fixo quando passamos de ? para ?, a hierarquia Veblen nos permite enumerar esses pontos fixos usando uma letra grega ? e um índice:

A hierarquia de Velben

E assim nós iteramos através de 4 funções de crescimento rápido. A função Veblen é um monstro. Outra maneira de pensar em nível é um aninhamento infinito de pontos fixos:

Aninhamentos Infinitos

Por exemplo, vamos dizer que queríamos escrever ?1 usando a função Veblen:

Vamos dividir um pouco para ver o que está acontecendo:

O índice em ? nos diz qual o nível da hierarquia a ser usada. A próxima entrada nos diz qual índice desse nível usar. A última entrada nos diz qual índice na sequência fundamental usar. Se fôssemos quebrá-lo em um exemplo:

À medida que a função Veblen se expande, você pode ver que ela começa a ficar muito grande. Essa expansão continuará por muito, muito tempo. Com entradas de 1 e 3, a função is é um monstro. A expansão é complicada porque se baseia em muitos tipos diferentes de matemática (regras de expoentes, por exemplo), mas quando você pega o jeito, pode fazê-lo.

Vamos fazer mais um exemplo da função Veblen:

Eu vou parar por aí porque esta expansão está ficando um pouco fora de mão. Como você pode ver, as funções recursivas Veblen crescem como loucas. Isso continuaria e continuaria.

Podemos usar ômega ? na função Veblen também. Por exemplo:

Eu não vou expandir mais, mas isso gera um número muito, muito, muito grande. Você também pode usar epsilon, zeta, etc. no índice da função Veblen. Você pode aninhá-los também, assim como fizemos antes. Podemos até aninhar a função Veblen:

O que acontece se aninharmos a função Veblen um número infinito de vezes?

Existe um ordinal especial que é o menor número maior que o maior número que você poderia criar a partir de um infinito aninhamento da função Veblen. É chamado de Gamma Naught: ?0. (É também chamado o ordinal Feferman-Schütte nomeado após as pessoas que descobriram.)

Seriamente grandes números para adultos sérios

Agora estamos entrando nas coisas realmente boas. Gamma nought ?0 é o limite para o maior ordinal possível que você pode obter usando recursão e diagonalização. Dito de outro modo, se você usar toda a matemática que mencionamos até o momento, você não poderá gerar uma função de crescimento mais rápido que ?0.

É léguas além de qualquer outra coisa sobre a qual falamos até agora. Não pode haver uma função que atinja esta altura, certo? Sim, pode. Deixe-me apresentar-lhe o teorema da árvore de Krukal .

A função TREE

A função TREE é uma famosa função de rápido crescimento, cuja força mede fora dos gráficos. Ela cresce perversamente rápido – mais rápido do que qualquer coisa que você possa imaginar. Por exemplo, estes são os três primeiros valores de TREE (n):

ÁRVORE (1) = 1
ÁRVORE (2) = 3
ÁRVORE (3) = grande número ímpio

ÁRVORE (3) tornou-se famosa porque com uma entrada tão pequena você é capaz de gerar um número que é perversamente grande. ÁRVORE (n) passa de ?0 em força!

A maneira como esta função funciona é muito complicada. Eu postei perguntas para vários lugares tentando obter uma explicação leiga para como esta função funciona e não tenho certeza se entendi bem o suficiente para explicar por mim mesmo, então vou usar a explicação de Deedlit :

Primeiro, vou mostrar uma função em ordinais que gera funções de crescimento rápido. Segundo, vou relacionar isso com a função de árvore menor (n). Por fim, mostrarei a função TREE (n) que cresce ainda mais rapidamente que tree (n).

Com o FGH, vimos como uma função em ordinais pode produzir funções de rápido crescimento. Para cada ponto fixo, encontramos um ordinal que não tem antecessor: ômega, épsilon, zeta, etc. Cada um desses pontos fixos relaciona-se a uma sequência fundamental; isto é, uma sequência crescente de ordinais que limitam é o ponto fixo ordinal.

Se a = um ordinal sucessor (ponto fixo como ? e ?) e n = os números naturais, podemos escrever a forma geral desta sequência como esta:

Uma coisa interessante sobre essa seqüência é que para uma [n] <a esta é uma sequência estritamente decrescente de ordinais. Uma das propriedades definidoras dos ordinais é que não há uma sequência infinita decrescente de ordinais; Portanto, para a > 0, existe um número natural mínimo m tal que:

Vamos definir uma nova função que receba uma entrada de um ordinal sucessor e um número natural e retorne m .

Com algum exemplo rápido, podemos ver como isso funciona:

Como você pode ver, esta construção leva aos mesmos números grandes que o FGH. Em geral, podemos dizer:

Ok, agora que temos isso, vamos falar sobre árvores. As árvores ficam assim:

Este é um exemplo de uma árvore.

Agora vamos definir a função small tree (n):

Defina tree (n) como a mais longa seqüência de árvores não-ordenadas, não-ordenadas T1, T2, … de tal forma que para todo i, Ti tem no máximo n + i vértices, e para todo i, j com i <j, Ti não é homeomorficamente incorporável em Tj.

O que é importante entender sobre as árvores é que, por serem incorporadas homeomorficamente, elas são “bem ordenadas” e isso significa que elas não podem ter uma sequência descendente infinita. Esta é uma propriedade similar aos ordinais que discutimos anteriormente. As árvores são diferentes, porque existem elementos em uma árvore que não podem ser comparados. Por exemplo:

Estas duas árvores não podem ser comparadas porque têm um número diferente de crianças no 2º nível. Nenhuma árvore incorpora a outra. Com a boa ordenação, podemos dizer que se Ti <Tj, então Ti não é embutido em Tj.

Com essas informações em mãos, podemos agora construir sequências de árvores que obedecem às condições requeridas: considerar Ti + 1 como a maior árvore menor que Ti, com não mais que o maior número permitido de nós.

Então, que tipo de números podemos obter? A situação é muito semelhante aos ordinais decrescentes que descrevemos acima.

Por exemplo, deixe a árvore T consistir em um único caminho de m vertices; isso corresponde ao ordinal finito m. Seja n o número máximo permitido de vértices na próxima árvore. Então a próxima árvore, que iremos denotar T [n], será um caminho de m-1 vértices, que corresponde ao ordinal m = 1, que é exatamente m [n]. Da mesma forma, a próxima árvore, T [n] [n + 1], corresponderá ao ordinal m [n] [n + 1] e assim por diante.

O que isto significa é que a sequência de árvores diminui a uma taxa similar que os ordinais diminuem. Em termos mais leigos, se começarmos uma árvore em ? ^ a, teremos uma função comparável na hierarquia de rápido crescimento Fa. A pergunta natural a ser feita é: Qual é o ordinal correspondente a esta ordenação de árvores?

Para responder a essa pergunta, vamos precisar voltar à função Veblen para aprender sobre a função Veblen estendida.

Função Veblen estendida

A função Veblen estendida é muito semelhante à função Veblen, mas é estendida para ir além de ?0.

Gamma Naught satisfaz esta questão:

–0 – Nama Gamma

Podemos estender a função Veblen adicionando outro dígito a ela. Isso também é igual a ?0:

?0 em notação Veblen estendida

Essa notação nos permite ir além de ?0. Assim, por exemplo, o gama 1 corresponderia à sequência fundamental de:

Não importa quão grande seja o ordinal, sabemos como lidar com os pontos fixos, escrevendo a sequência fundamental e depois indexando o termo correto na sequência.

Na notação de Veblen, podemos escrever ?1 escrevendo simplesmente:

Continuamos indo cada vez mais alto até chegarmos:

O próximo ordinal seria:

Observe que aumentamos a segunda entrada de 0 para 1? É assim que lidamos com ir além de ?. Nós poderíamos continuar:

Finalmente, chegamos a um ponto em que a entrada do meio fica sem energia. Quando isso acontece, nós simplesmente incrementamos a primeira entrada:

Além disso, as coisas ficam bem incompletas. Podemos continuar e continuar adicionando novos dígitos à função Veblen:

Agora, o que aconteceria se tivéssemos uma função Veblen com um número infinito de argumentos? Isso corresponderia à sequência fundamental de algo como:

O Pequeno Ordinal Veblen

Isso é chamado de Pequeno Veblen Ordinal. É um ponto importante no FGH e muito além de tudo que discutimos até agora.

ÁRVORE (n)

Portanto, agora que definimos as funções estendidas de Veblen, podemos medir a magnitude da ordem dos poços. Bem, a ordenação é baseada no princípio de que todo conjunto não vazio de inteiros positivos contém um elemento mínimo. Em outras palavras, o conjunto de inteiros positivos é bem ordenado. O limite de ordenação de poços e nossa função de pequena árvore (n) é o Pequeno Ordinal Veblen.

Uma árvore cuja raiz como duas crianças sem filhos corresponde ao ômega. Uma árvore cuja raiz tem três filhos sem filhos corresponde a ?0. Uma árvore cuja raiz tem quatro filhos sem filhos corresponde a phi (1,0,0,0). Isso continua indo até o Pequeno Veblen Ordinal!

Agora podemos definir TREE (n):

ÁRVORE (n) é o comprimento da maior sequência de árvores T1, T2,… rotulada a partir de {1,2,3, .., n} tal que, para todo i, Ti tem no máximo i vértices, e para todos i , de tal modo que eu não há incorporação homeomorfa de preservar rótulos de Ti em Tj.

ÁRVORE (1) é simples. A primeira árvore tem que ser uma única árvore de vértices.

ÁRVORE (2) é 3.

ÁRVORE (3) é uma história totalmente diferente. É tão insondável que a humanidade ainda não foi – e provavelmente nunca será – capaz de inventar uma maneira de definir escalas suficientemente grandes para compreender o número. É ordens de magnitude além do nosso alcance.

Como é o TREE (3)?

Seqüência de árvore (3)

ÁRVORE (3) começa assim e continua por um tempo muito longo. Sabemos que a função menor de árvore (n) é limitada pelo Pequeno Ordinal Veblen. Também sabemos que o TREE (n) cresce muito mais rápido que a árvore (n), porque as árvores rotuladas levam a mais possibilidades do que as árvores sem rótulos. Quanto mais rápido cresce?

ÁRVORE (3) é grande perversa.

Se você olhar de perto, estamos executando a função de árvore menor (n) em uma entrada MUITO grande e ela ainda é menor que a ÁRVORE (3).

O matemático Harvey Friedman demonstrou que a menor prova na aritmética de Peano de que o TREE (3) existe requer muito mais símbolos do que átomos no Universo.

É aqui que o TREE (n) fica no FGH:

Existe outra função chamada Função de Gráfico Subcúbico SSG (n) que coloca VERDADE (n) como vergonha. Eu não entendo completamente, então não incluí no artigo. Ainda assim, podemos ir mais alto.

Função de Colapso Infinito

Para passar pelas Funções Veblen Estendidas, precisamos aprender uma nova técnica. Essa nova notação ordinal foi criada por David Madore e usou uma variante da função de Buchholz . Essa função é muito abstrata, então fique lá. Primeiro temos que definir o conjunto S.

? é um novo tipo de ordinal que é MUITO GRANDE, maior do que qualquer coisa que possamos precisar. Agora podemos definir um novo conjunto C0 que é composto de tudo que você pode fazer com adição, multiplicação, etc.

Qual é o primeiro ordinal inacessível neste conjunto? É uma torre infinita de ?'s. Também chamado de ?0. É assim que podemos defini-lo usando ?:

Agora vamos criar um novo conjunto C1 que contém todos os itens em C0, além de todos os itens que poderíamos fazer com adição, exponenciação, etc. a partir de C0:

Agora podemos definir ? (1):

E podemos continuar assim até ?0. Como você ultrapassa ?0 da função?? Não importa o que você conecte à função,, ela não pode passar de ?0.

É aqui que vem a calhar do conjunto original S que criamos.

Agora que usamos o ? definido para definir ? (?0), podemos definir C (?0 + 1):

E agora nós temos:

Então, conseguimos passar pela armadilha de ponto fixo usando a função ?. Podemos continuar fazendo isso para continuar subindo a escada.

Isso vai continuar por um longo tempo até chegarmos à próxima armadilha de ponto fixo:

Então, como podemos superar isso? ? para o resgate!

Em geral, podemos dizer:

Podemos continuar até a próxima vez que ficarmos presos, o que será:

Mas podemos usar ? para sair disso:

Espero que você esteja vendo um padrão se formando aqui. Podemos nos ater a sair disso. Geralmente podemos dizer que:

Podemos adicionar continuamente nossos produtos para obter números maiores e maiores. Por exemplo:

Podemos até comparar esses números com as funções Veblen:

E aqui está o pequeno ordinal Veblen:

Pequeno Ordinal Veblen escrito usando funções de recolhimento

Podemos ir maior? Sim, podemos, como sobre o grande Ordinal Veblen, que é o máximo de ordinal de toda a hierarquia Veblen estendida:

O grande ordinal Veblen

E assim, escrevemos um ordinal que vai além de tudo que vimos até agora. Vamos relacionar esse número com o FGH e desconstruí-lo um pouco. Primeiro precisamos construir a sequência fundamental:

Agora podemos tentar um exemplo:

Se nós desconstruirmos um pouco mais:

E continua indo e indo e indo. O grande ordinal Veblen é o ordinal máximo? Podemos ir mais alto? Absolutamente. E se adicionássemos outro ? ao topo? Nós conseguiríamos isto:

Estrondo! Nós apenas fomos maiores que toda a Hierarquia Veblen. Isso está tão além de qualquer coisa com a qual trabalhamos que não sabemos realmente como é esse número. Nós realmente não podemos compará-lo a nada. Podemos, no entanto, continuar. Podemos ficar em uma torre infinita de which que é onde as coisas param.

Bachman Howard Ordinal

Isso é chamado de Bachmann Howard Ordinal e é o limite superior da função ?. Esta é a prova teórica ordinal para várias teorias matemáticas incluem a teoria dos conjuntos de Kripke Platek (com o axioma do infinito) e o sistema CZF da teoria dos conjuntos construtivos . Este ordinal está doente.

Podemos ir maior?

Precisamos criar um novo conjunto S1 que contenha um novo elemento:

Agora podemos começar a definir ?1:

Nota: este não é o Bachmann Howard Ordinal

Se quiséssemos escrever o Bachmann Howard Ordinal em termos desse novo we1, escreveríamos:

O Bachmann Howard Ordinal

Se quiséssemos ir além do Bachmann Howard Ordinal, simplesmente temos que fazer isso:

Estrondo! Nós descrevemos um ordinal que é maior que o Bachmann Howard Ordinal. Podemos continuar crescendo usando as mesmas técnicas que usamos antes. Eventualmente chegamos a outro limite com uma sequência fundamental parecida com esta:

Isso é chamado de Igreja-Kleene Ordinal. Às vezes é escrito assim:

Igreja-Kleene Ordinal

Este é o menor ordinal que não pode ser criado através de funções recursivas. Até este ponto, todas as funções que criamos usaram a recursão. A Igreja Kleene Ordinal é tão grande que não pode ser alcançada por recursão. Não pode ser descrito através de funções recursivas. Outra maneira de dizer isso é que não há nenhuma função computável que possa atingir esse ordinal. Estranhamente, embora esse ordinal não seja recursivo, ele ainda é contável. A distância entre este ordinal e o Grande Ordinal Veblen é insuperavelmente vasta.

Este ordinal também é igual à taxa de crescimento da famosa função de castor ocupado . (A descrição desta função vem depois.)

É também o ômega do xadrez. Suponha que tivéssemos um tabuleiro de xadrez de tamanho infinito com um número infinito de peças. Qual é o supremo total dos valores de todas as posições que o jogador branco pode forçar uma vitória? Isso é chamado de omega one e o ordinal geralmente é escrito assim:

Ômega 1 do Xadrez

Acredita-se que o ômega 1 do xadrez seja no máximo o ordinal Igreja-Kleene. (Isso não foi provado)

De volta ao ordinal Igreja-Kleene. Se quiséssemos usar este ordinal no FGH, poderia ser assim:

Igreja-Kleene Ordinal no FGH

Podemos ir mais alto que o ordinal Igreja-Kleene? Sim e não. Podemos definir ordinais maiores, mas não temos esperança de descrevê-los com precisão. Ainda assim, isso não vai nos impedir, vamos continuar.

Podemos construir uma hierarquia de ordinais não recursivos. Por exemplo:

Ou podemos fazer isso:

Qual é a taxa de crescimento da função Rayo (n) que foi criada por um filósofo do MIT para ganhar o "nome do maior concurso de números". A função foi nomeada em sua homenagem. Podemos até ir até um infinito aninhamento de ?'s:

A função que mais cresce em Googologia.

Este é o primeiro ponto fixo da Igreja-Kleene. Também pode ser escrito assim:

Se fôssemos escrevê-lo como uma função no FGH, poderia ser assim:

Ponto fixo Igreja-Kleene no FGH

Até onde eu sei, essa função cria um número que excede qualquer coisa que alguém tenha definido. Ela cresce significativamente mais rápido que o Rayo (n).

Subir mais a escada é um pouco louco. Há ordinais para máquinas de Turing de tempo infinito que ficam bem insanas.

Máquinas de Turing de Tempo Infinito

Alan Turing inventou o conceito da máquina de Turing em 1936. Uma máquina de Turing é uma máquina abstrata que manipula símbolos em uma tira de fita de acordo com uma tabela de regras. Isso cria um modelo matemático de computação.

Uma máquina de Turing de tempo infinito é aquela que estende a operação de máquinas de Turing ordinárias para o tempo ordinal transfinito. Anteriormente as máquinas de torneamento tinham um estado de partida e um estado de parada. Com máquinas de Turing com tempo infinito, há um estado limite adicionado para lidar com a situação ao lidar com um limite ordinal. Com isso em mente, podemos definir dois novos ordinais que vão além dos ordinais Igreja-Kleene:

  1. Gama – o supremo dos ordinais escritas
  2. Zeta – o supremo dos ordinais eventualmente graváveis

(Supremum = o menor limite superior.)

Esses dois ordinais são admissíveis (como o ordinal Igreja-Kleene), mas vão além do tamanho. Se você quiser dar uma olhada em um artigo sobre este tópico, você pode ver um aqui . Eu não sei como usar estes ordinais no FGH, então eu apenas os menciono.

O maior número possível

No meu parágrafo de abertura, mencionei um artigo do famoso cientista da computação Scott Aaronson para citar o maior número. Ele propôs a função Busy Beaver como um exemplo de uma função que cria um grande número. Recentemente, ele postou a troca de pilha que ele poderia nomear um número maior – um que poderia potencialmente ganhar o concurso.

Primeiro ele descreve a função de castor ocupado:

Dada uma máquina de Turing M, seja S (M) o número de passos feitos por M em uma fita inicialmente em branco, ou 0 se M rodar para sempre. Então lembre-se que BB (n), ou o número n-Busy Beaver, é definido como o máximo de S (M) sobre todas as máquinas de Turing de n-estado M. BB (n) é facilmente visto crescer mais rápido que qualquer função computável.

Ele admite que a função BB (n) é insignificante comparada às outras funções do FGH. Então ele propõe uma nova função:

Então, vamos definir BB1 (n) como o análogo de BB (n), para máquinas de Turing equipadas com um oráculo que calcule BB0 (n): = BB (n). Da mesma forma, para todos os inteiros positivos k, seja BBk a função Busy Beaver para máquinas de Turing que estejam equipadas com um oracle para BBk ? 1. Não é difícil ver que o BBk cresce mais rápido que qualquer função computável com um oracle BBk-1.

Então ele vai além definindo BB (n) sobre omega:

Então ele generaliza a fórmula sobre todos os ordinais computáveis:

Em seguida, seja ? (n) o maior ordinal computável que pode ser definido (no sentido acima) por uma máquina de Turing com no máximo n estados.

Isso leva ao seguinte:

Segundo Scott:

Tenho uma forte intuição de que as máquinas de Turing são um sistema notacional “maximamente expressivo”, pelo menos para aqueles números que atendem ao meu critério de ser “definido em termos de processos finitos”.

Isso deve colocar a função de Busy Beaver modificada de Scott no topo da FGH para outubro de 2016. Por enquanto eu acredito que este é um bom lugar para parar minha exploração do FGH.

Nossa viagem até o FGH passou de uma função sucessora muito básica até essas funções de crescimento muito rápido que geram números semelhantes aos deuses. Ao longo do caminho, usamos recursão e diagonalização para gerar funções de crescimento mais rápido.

Tudo o que analisamos no FGH ainda é significativamente menor que o cardinal ?1 . Essa é a cardinalidade de todos os números ordinais contáveis. ?1 é o primeiro ordinal incontável. Para citar Donald Trump, é "YUGE".

Eu estou esperando que eu não tenha me enganado muito com este artigo. Eu não tenho formação em matemática, então estou trabalhando em artigos e artigos que li. Eu reconhecidamente não sei muito sobre esses assuntos, mas estou interessado em aprender. Escrever este artigo foi uma ótima lição de aprendizado para mim e eu agradeço todo e qualquer feedback.

Por fim, eu não poderia escrever este artigo se não fosse pela ajuda de outros. Os artigos e vídeos a seguir foram valiosos na criação deste artigo. Você é encorajado a dar uma olhada em alguns deles se quiser mergulhar mais fundo:

  1. Série de David Metzler no YouTube sobre números ridiculamente enormes
  2. Artigos de Adam Goucher sobre Funções de Crescimento Rápido
  3. Artigo de Scott Aaronson sobre Quem pode nomear o número maior?
  4. Acompanhe o artigo de Scott Aaronson sobre Stack Exchange
  5. Site da Sbiis SaiBain em grandes números
  6. Série de Giroux Studio em números extremamente grandes
  7. A Wiki da Googologia na Hierarquia do Crescimento Rápido
  8. Esta questão no Stack Exchange respondida por Deedlit
  9. Grande número de bolinho Fönster página
  10. Cantores Sótão
  11. Fóruns do XKCD sobre quem pode nomear um número maior

Compartilhar isso:

Relacionado

Publicado por joshkerr

Josh é um fundador de startup 8x e investidor anjo.

Deixe um comentário

Você deve entrar para postar um comentário.

Este site usa o Akismet para reduzir o spam. Saiba como seus dados de comentários são processados .