O maior número representável em 64 bits
Quão grande um número pode realmente ser representado com apenas 64 bits depende menos de limites do hardware do que de como esses bits são interpretados. Os comentaristas contrastam formatos numéricos fixos, como inteiros e floats IEEE 754, com esquemas que codificam programas inteiros de cálculo lambda ou máquinas de Turing, permitindo que 64 bits representem valores inimaginavelmente grandes (por exemplo, via construções do tipo Busy Beaver), mas ao custo de arbitrariedade, não computabilidade e aritmética pouco útil. Grande parte do debate gira em torno de quais restrições são necessárias para evitar codificações de “trapaça” e se modelos como o cálculo lambda fornecem uma base suficientemente natural e não trivial para definir tais números máximos.
Arbitrariedade das Codificações de 64 bits
- Vários comentários argumentam que qualquer string de 64 bits pode denotar qualquer conjunto escolhido de 2⁶⁴ valores; sem restrições, “o maior número representável” é uma formulação mal colocada.
- Outros contrapõem que isso é pedante: a versão interessante pergunta pelo maior número não trivial sob uma interpretação fixa e pré-existente.
Cálculo Lambda, Busy Beaver e Complexidade de Kolmogorov
- A discussão concorda que o artigo usa efetivamente o cálculo lambda como uma linguagem descritiva compacta e “natural”, e então pergunta pelo maior número descritível em 64 bits dessa linguagem.
- Isso se liga ao crescimento no estilo Busy Beaver: codificar um programa (por exemplo, um termo lambda) cuja saída cresce mais rápido do que as notações usuais para números grandes.
- Alguns observam que isso se conecta à complexidade de Kolmogorov / descrições mínimas, em que diferentes formalismos universais diferem apenas por fatores constantes.
Quão “Arbitrário” é o Cálculo Lambda Binário?
- Um lado: o cálculo lambda está entre os formalismos de computação menos arbitrários; suas codificações são, portanto, linhas de base significativas.
- Outro lado: codificações binárias específicas (índices de de Bruijn, codificação unária, formato auto-delimitado) ainda envolvem escolhas de projeto, então não são unicamente canônicas.
- Os defensores respondem que essas escolhas são mínimas, eficientes em bits e próximas da semântica da linguagem.
Números Computáveis vs. Não Computáveis
- Esclarecimentos: todo inteiro finito é computável; a maioria dos números reais não é.
- A discussão se concentra em valores de Busy Beaver (inteiros, mas a função é não computável) e na constante de Chaitin (um real não computável canônico).
- Há uma troca sobre se “conhecer” um valor via um oráculo o tornaria computável; o consenso: não, a não computabilidade diz respeito à existência de um algoritmo, não a um conhecimento oracular hipotético.
“Trapacear” com Sistemas Numéricos Personalizados
- Alguns propõem esquemas triviais de 64 bits em que, por exemplo, o padrão de bits “1” significa “um número nomeado enorme” ou “execute o algoritmo do artigo”.
- Outros rotulam isso como “trapaça”: você está efetivamente embutindo a resposta no interpretador em vez de derivá-la de um formalismo geral e fixo.
- Uma restrição sugerida recorrente: o esquema de representação deve ser anterior ao concurso específico, e o interpretador não deve conter conhecimento codificado do número gigantesco.
Outros Sistemas Numéricos e o Infinito
- IEEE754 doubles, infinito, posits e unums são mencionados, mas seus intervalos são apontados como minúsculos em comparação com números do tipo Busy Beaver codificados em cálculo lambda.
- Alguns sugerem contar cardinais infinitos (alephs), mas o foco original é esclarecido como sendo apenas números finitos.