Por que BB(3, 3) é difícil: Bigfoot
(sligocki.com)- A máquina de Turing de 3 estados e 3 símbolos Bigfoot é um caso em que, para provar se para ou não a partir da fita vazia, é preciso resolver um problema análogo ao de Collatz, mostrando que (BB(3, 3)) pode ser tão difícil quanto isso
- Essa máquina é uma das 160 candidatas não resolvidas de (BB(3, 3)) no bbchallenge.org e é definida pela tabela de transição
1RB2RA1LC_2LC1RB2RB_---2LA1LA - Seu comportamento se reduz a regras iterativas da configuração (A(a,b,c)), nas quais a aumenta ou diminui conforme (b \bmod 6) e só para quando (a) tentaria cair abaixo de 0
- A partir da fita vazia, ela chega a (A(2,1,2)) após 69 passos e, depois de 24 milhões de iterações, cresce até (a = 3,999,888), de modo que a possibilidade de parada parece experimentalmente muito baixa
- A sequência de (b \bmod 6) é determinística, mas no panorama geral parece um passeio aleatório enviesado, com 2/3 para a direita e 1/3 para a esquerda; para provar que roda para sempre, seria preciso mostrar que essa função análoga à de Collatz nunca alcança a transição de parada
Por que Bigfoot torna (BB(3, 3)) difícil
- Para provar a parada ou não parada de uma única máquina de Turing de 3 estados e 3 símbolos, é preciso resolver um problema análogo ao de Collatz
- Portanto, resolver o problema de (BB(3, 3)) pode ser tão difícil quanto resolver esse problema análogo ao de Collatz
- Paul Erdős certa vez disse sobre problemas do tipo Collatz: “Mathematics may not be ready for such problems”
- No texto anterior Mother of Giants, foi tratada uma família de máquinas de Turing encontrada na busca pelo Busy Beaver “Beeping”
- Para essa família, provar o estado de quase-parada (quasihalt) exige simular com eficiência ou resolver completamente um problema análogo ao de Collatz
- Bigfoot é um caso encontrado não em um jogo modificado, mas dentro do jogo normal de Busy Beaver
Casos anteriores de dificuldade no Busy Beaver
- Várias máquinas de Turing construídas por humanos oferecem exemplos em que, para provar certos valores de Busy Beaver, é preciso provar outras proposições matemáticas difíceis
- (BB(745)): exige uma prova da consistência de ZFC
- (BB(27)): exige uma prova da Conjectura de Goldbach
- (BB(15)) e (BB(5,4)): exigem uma prova da conjectura de Erdős de que, para (n > 8), a representação em base 3 de (2^n) contém pelo menos um dígito 2
- No entanto, esses valores de Busy Beaver estão atualmente fora de qualquer alcance prático
- Nos últimos 60 anos, apenas (BB(2), BB(3), BB(4), BB(2,3)) foram provados, e sabe-se que (BB(6) > 10 \uparrow\uparrow 15)
- Antes da análise do Bigfoot, acreditava-se que ainda poderia haver chance de provar (BB(3, 3))
Definição e origem do Bigfoot
- O nome dessa máquina de Turing é Bigfoot, e sua tabela de transição é definida pela seguinte string
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- É uma máquina registrada no bbchallenge
- A tabela de transição é a seguinte
| Estado | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot é uma das 160 holdouts informais restantes de (BB(3,3)) compartilhadas no canal do Discord do bbchallenge.org
- Essa máquina de Turing específica foi compartilhada pela primeira vez em 14 de outubro de 2023 no mesmo canal do Discord por @savask, junto com uma descrição de baixo nível do comportamento
- Análises posteriores revelaram a estrutura análoga à de Collatz e o caráter de passeio aleatório enviesado
Comportamento reduzido à configuração (A(a,b,c))
- Consideremos a configuração geral a seguir
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Quando Bigfoot entra em uma configuração (A(a,b,c)) com (c \ge 1), as regras abaixo descrevem com exatidão todo o comportamento subsequente até parar ou seguir para sempre
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- Essas regras iteram uma função análoga à de Collatz sobre os parâmetros (b) e (c)
- (a) se comporta como um valor acumulado
- se (b \equiv 1 \pmod{6}) ou (b \equiv 4 \pmod{6}), então (a) aumenta
- se (b \equiv 2 \pmod{6}), então (a) diminui
- Bigfoot só para quando (a) tenta diminuir abaixo de 0
Trajetória observada a partir da fita vazia
- Começando da fita vazia, Bigfoot chega à configuração (A(2,1,2)) após 69 passos
- Em simulações posteriores, (a) parece crescer de forma contínua e, após 24 milhões de iterações, chega a (a = 3,999,888)
- Se assumirmos que a sequência de restos de (b \bmod 6) é aleatória uniforme, o processo equivale a um passeio aleatório enviesado na reta numérica
- em cada etapa, a probabilidade de ir para a direita é (\frac{2}{3})
- a probabilidade de ir para a esquerda é (\frac{1}{3})
- Na teoria de cadeias de Markov, é possível provar que, quando a posição atual é (a=n), a probabilidade de no futuro chegar a (a=-1) é ((\frac{1}{2})^{n+1})
- Na prática, a sequência de (b \bmod 6) não é aleatória, mas totalmente determinística, seguindo de forma consistente o padrão ímpar·ímpar·par·par
- Mesmo assim, em grande escala ela mostra uma trajetória parecida com a de uma cadeia de Markov aleatória
- após 24 milhões de etapas, espera-se que a cadeia de Markov ande 8 milhões de vezes para a direita e 4 milhões para a esquerda
- isso fica muito próximo do valor real de (a), em torno de 4 milhões
A heurística de que “provavelmente” não para
- Quando (a \approx 4,000,000), a probabilidade de a cadeia de Markov aleatória atingir (a=-1) é aproximadamente ((\frac{1}{2})^{4,000,000})
- Esse número é tão pequeno que, do ponto de vista científico, pode ser tratado como se o fracasso estivesse garantido
- Se Bigfoot se comporta de modo parecido com a cadeia de Markov, então parece não parar
- Mas isso não é uma afirmação matemática rigorosa, e sim uma heurística experimental
- Não se pode descartar a possibilidade de Bigfoot parar depois de um googolplex de iterações
- John Conway cunhou essa expressão ao explicar a heurística de que a conjectura de Collatz seria “probviously” verdadeira, mas uma prova de Collatz ainda não apareceu
Os dois finais possíveis para Bigfoot
- Bigfoot é uma destas duas coisas
- para
- roda para sempre
- Se parar, isso pode ser provado acelerando suficientemente a iteração da função análoga à de Collatz e simulando até o fim
- Se rodar para sempre, será preciso provar que essa função análoga à de Collatz nunca alcança a transição de parada em (a=0)
- Pela heurística da cadeia de Markov, o segundo caso parece mais plausível, e também muito mais difícil de provar
O nome Cryptids
- Máquinas desse tipo têm seu comportamento reduzido a regras matemáticas relativamente simples, mas essas regras pertencem a uma classe de problemas matemáticos em aberto
- Elas se parecem com criaturas lendárias sobre as quais só existem rumores de que param ou não param, sem que nenhum dos lados apresente evidência concreta
- Foi proposto chamá-las de Cryptids
- É uma analogia com criaturas lendárias como o Monstro do Lago Ness ou o Chupacabra
- Como essa máquina de Turing parece andar de modo aleatório, ela recebeu o nome Bigfoot
Esse comportamento análogo ao de Collatz é realmente difícil?
- A dinâmica dessa função específica análoga à de Collatz parece ser um problema quase não analisado antes
- Ainda existe a possibilidade de encontrar, com um pouco de teoria dos números e computação, alguma propriedade matemática engenhosa que se aplique apenas a esse problema
- Se tal propriedade for descoberta, isso mostrará que a prova de (BB(3,3)) ainda está dentro de um alcance possível
- Em problemas análogos ao de Collatz, as perguntas que se pode fazer empiricamente se dividem em dois tipos
- perguntas cuja prova é relativamente trivial
- perguntas para as quais nenhum matemático conhece um método de prova
- No caso do Bigfoot, o fato de (b) repetir o padrão ímpar·ímpar·par·par, ou o fato de que, após aplicar a regra tradicional de Collatz (3n+1), o resultado sempre se torna par e na etapa seguinte é dividido por 2, pertencem à primeira categoria
- Quase todas as demais perguntas sobre o comportamento de sistemas de Collatz podem ser vistas como exemplos da segunda categoria
Uma formulação alternativa com 81 casos
- Uma formulação alternativa adicionada em 18 de outubro de 2023 reduz a inconveniência da descrição original em (A(a,b,c))
- A descrição original tem três inconvenientes
- os parâmetros (b) e (c) estão entrelaçados
- o módulo 6 da entrada e o módulo 8 da saída têm o fator comum 2
- (b) segue o padrão repetido ímpar·ímpar·par·par
- Matthew House observou que esses problemas podem ser evitados definindo a nova configuração da seguinte forma
[ B(a,b)=A(a,2b+1,2) ]
- Escrevendo (b=81k+r) e agrupando as 4 transições originais em uma única transição, o comportamento análogo à de Collatz do Bigfoot pode ser expresso como uma regra de 81 casos
- Essa formulação resolve as três características da representação anterior em (A) e se parece mais com o problema clássico de Collatz
- Ainda assim, ela é um tanto difícil de manejar, pois exige tratar todos os 81 casos
- Algumas regras dependem da condição (a \ge 2)
1 comentários
Comentários do Hacker News
Mais do que BB(3, 3) em si ser difícil, parece mais correto dizer que ele codifica problemas do tipo Collatz, e que esse tipo de problema em geral é considerado muito difícil
Mas se esta instância específica é necessariamente difícil é outra questão. O comportamento parece bastante enviesado para um lado e, diferentemente do problema clássico de Collatz, não é preciso examinar as trajetórias de todos os inteiros; basta olhar uma única trajetória
Também concordo em certa medida com a distinção entre uma única trajetória e várias trajetórias. Ainda assim, se assumirmos que esta máquina de Turing está em um mundo em que não para, provar uma única trajetória desse sistema pode ser visto como “mais difícil” do que uma única trajetória da conjectura clássica de Collatz. Se a conjectura de Collatz for verdadeira, a prova de qualquer trajetória individual acaba sendo apenas um cálculo finito; já a trajetória única do texto precisa mostrar que ela nunca para, o que exige matemática mais sofisticada
Não quero exagerar. Isso não significa que, para resolver BB(3, 3), seja obrigatório provar a conjectura de Collatz ou algum problema em aberto de uma área da matemática já bem estudada. Ainda assim, acho significativo como um resultado “de segunda melhor opção”: um problema difícil que se parece com um problema bem estudado. Para saber quão difícil é esse problema análogo a Collatz, talvez baste ver quem consegue resolvê-lo
Quero ajudar a entender isto. Há uma máquina de Turing com 748 estados [0], e entendo que essa máquina para somente se ZFC for inconsistente
Essa máquina é um objeto “físico” que pode ser implementado e executado em um computador. A capacidade computacional atual é insuficiente, mas, em princípio, nada impede executar essa máquina por BB(748) passos. Se ela parar, pelo Teorema 1 teremos provado que ZFC é inconsistente; se ela não parar, parece que teremos provado que ZFC é consistente
Esse é o cerne da confusão. Não parece um resultado abstrato, mas uma computação que de fato poderíamos executar e obter um valor
Claro, pelo segundo teorema da incompletude de Gödel, não é possível provar dentro de ZFC a consistência de ZFC. Mas, se a máquina de Turing acima parar, isso pareceria provar que ZFC é consistente, dando a impressão de uma contradição
Onde está o erro? Meu palpite atual é que, na prova do Teorema 1, para mostrar que a máquina de Turing de 748 estados para somente se ZFC for inconsistente, foi usada uma metateoria mais forte que ZFC. Nesse caso, não há contradição. Mesmo que se possa rodá-la por BB(748) passos, isso só mostra que ZFC+ prova a consistência de ZFC, algo que já é conhecido. Por exemplo, ZFC + “existe um cardinal inacessível” desempenha esse papel
Não examinei o artigo em detalhes, então não sei se é realmente isso. Alguém que já pensou profundamente sobre esse problema poderia oferecer algum insight?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Se o deus dos castores ocupados nos dissesse esse valor, em tese poderíamos rodar a máquina de Turing por esse número de passos e, como você disse, provar a consistência ou inconsistência de ZFC. Mas, para humanos calcularem BB(748), seria preciso essencialmente descobrir se essa máquina de Turing específica de 748 estados algum dia para, e também se todas as outras máquinas de Turing de 748 estados param
Mesmo que construíssemos um computador usando toda a matéria e energia do universo, e esse computador fizesse apenas essa tarefa na máxima eficiência fisicamente possível, ele não conseguiria terminar o cálculo
É aí que a matemática se separa da física e da realidade. Podemos falar e raciocinar sobre esses objetos, mas eles já não têm significado físico
Mas provar que ela não para é muito mais difícil. Mesmo executá-la por TREE(3) passos não é uma prova de que ela não vai parar no passo TREE(3)+1
Então, infelizmente, não dá para dizer “é só rodar”
Gostei do estilo do autor. Ajudou a entender o tema sem parecer prolixo, e não é fácil acertar esse ponto de equilíbrio
Materiais relacionados: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... e https://googology.fandom.com/wiki/Googology_Wiki
É isso que quer dizer afirmar que BB é incomputável? Fico me perguntando se, à medida que BB cresce, ele passa a conter toda a matemática e, no fim, seria preciso provar tudo
O restante de toda a matemática é contrabandeado para dentro de BB por meio do problema da parada. Como é possível escrever um programa que para somente quando uma conjectura matemática arbitrária é verdadeira ou falsa, tentar resolver o problema da parada ou BB exige saber toda a matemática[0]. Isso é possível porque a completude de Turing é a fronteira da computabilidade. Aquilo que consegue conter um computador é, por si só, um computador
[0] Na verdade, isso por si só não é o motivo que torna a parada indecidível. A indecidibilidade vem de um programa “puxar a si mesmo para dentro do problema da parada”, como no caso de um suposto decisor de parada que para somente quando diz que ele próprio não vai parar
Há problemas matemáticos que “sabemos” que não podemos nem provar nem refutar. O primeiro teorema da incompletude de Gödel diz que isso ocorre desde que não estejamos no caso em que toda proposição possa ser provada tanto verdadeira quanto falsa. Se toda proposição pudesse ser provada como verdadeira e falsa, esse sistema de prova seria inútil, e provar algo não significaria nada; portanto, seria preciso escolher outro sistema de prova em que isso não aconteça. Assim, normalmente assumimos o primeiro caso: que existem problemas que não conseguimos nem provar nem refutar. Além disso, o segundo teorema da incompletude de Gödel diz que jamais podemos provar que estamos nesse primeiro caso
E dizer que BB é incomputável significa que, quando BB fica grande o suficiente, em algum momento será possível codificar um programa que para somente se for verdadeiro um problema que não pode ser provado nem refutado. Por isso, não podemos provar se esse programa para ou não
Estritamente falando, provar ou refutar algo que não pode ser provado nem refutado equivaleria a provar uma falsidade, e isso, no fim, poderia ser usado para “provar” qualquer proposição; nesse sentido, dizer que “abrange toda a matemática” está correto. Mas isso é uma condição-limite, e entra em ação muito antes de surgir uma máquina de Turing grande o bastante para codificar “todos” os problemas matemáticos. Na prática, não existe um número finito de estados suficiente para codificar todos os problemas matemáticos, porque sempre é possível tornar cadeias aritméticas mais longas
Depois disso, não surpreende que existam BBs que não conseguimos resolver; o interessante passa a ser investigar quais BBs conseguimos resolver e quais não
Não entendo por que a parte “portanto, resolver o problema BB(3, 3) é pelo menos tão difícil quanto resolver esse problema semelhante ao de Collatz” é surpreendente. Na verdade, parece algo quase trivial de provar. Todo problema BB(x, y) não se reduz a um problema do tipo Collatz?
BB(x, y) pode ser facilmente transformado no problema da parada. Encontre, entre todas as máquinas com x estados e y símbolos, quais param, e separe as que não param. Depois execute todas as máquinas que param, um passo de cada vez em conjunto, até que todas tenham parado; o número de passos executados será o valor de BB(x, y)
Pelo que sei, Conway apresentou uma forma de reduzir o problema da parada a problemas do tipo Collatz. Então, por uma redução em duas etapas — de BB para o problema da parada e depois para Collatz — parece possível reduzir BB(x, y), para quaisquer x e y, a um problema do tipo Collatz
O que é necessário é uma redução de Collatz para o problema da parada e depois para B(x,y). A passagem de Collatz para o problema da parada é trivial, mas a do problema da parada para B(x,y) é menos óbvia. É preciso definir exatamente qual subconjunto do problema da parada pode ser reduzido a partir de Collatz e, ao mesmo tempo, não é mais difícil que B(3,3)
O problema da parada parece frequentemente “bloquear” muitas abordagens de teoria algorítmica da informação e de indução baseadas em programas computáveis. Mas fico curioso se há estudos sobre se o problema da parada tem algum impacto material na capacidade de indução no mundo real
Por exemplo, suponha que um oráculo informe se uma máquina de Turing universal monótona arbitrária em execução chegou a um ponto em que não escreverá mais nada na fita de saída. Os resultados de indução obtidos com esse oráculo seriam muito diferentes de uma abordagem que faz busca exaustiva no espaço de programas e, se um programa não produzir saída por um número n suficientemente grande de passos, simplesmente “pula” para o próximo programa?
Estou falando de indução sobre dados “comuns” e compressíveis, não de casos-limite criados de propósito como BB(3,3) ou exemplos adversariais
Como pesquisador de segurança, escrevo fuzzers diretamente. Um fuzzer é uma ferramenta que encontra automaticamente entradas relevantes para a segurança em um programa-alvo. Ele gera e modifica entradas algoritmicamente, as fornece ao programa e observa o que acontece dezenas, centenas ou milhares de vezes por segundo
Se uma entrada faz o programa travar, podemos ver isso como ter “feito o programa parar”. Para criar, para qualquer programa, um fuzzer que encontre todos os bugs em um tempo realista, parece que seria preciso resolver o problema da parada. Na prática, mesmo depois de bilhões de testes, ainda há gente encontrando bugs em decodificadores de imagem, então é correto dizer que os fuzzers que temos não são perfeitos
Ao mesmo tempo, no mundo real, já vi fuzzers penetrarem mais fundo do que o esperado em programas complexos quando recebem tempo suficiente. A validação de entrada feita pelo alvo de teste e a memória e o armazenamento limitados dos PCs modernos colocam o fuzzer, até certo ponto, nos trilhos. A exceção é quando entra criptografia: para um fuzzer, ela é como um atoleiro computacional. Programas bem defendidos e bem especificados funcionam como guardrails próprios que evitam que o fuzzer precise resolver o problema da parada
Então, quanto à detecção de bugs de segurança em programas, vejo assim: exceto em criptografia, fuzzers são fortes para mirar programas que fazem validação rigorosa de entrada. Por outro lado, em programas que não fazem validação rigorosa de entrada, fuzzers nem são tão necessários, e nesses casos eles também não necessariamente funcionam bem
Há alguma intuição para por que o BBB, ou seja, o busy beaver que emite bipes, pode rodar por muito mais tempo antes de quase parar?
Uma coisa que dá para perceber é que, na prática, não é preciso usar o estado de parada. Nesse sentido, um BBB de 3 estados talvez seja parecido com um BB de 4 estados. Fico curioso se há algo além disso
Então dá para fazer um programa ou uma máquina de Turing de tamanho X simular a execução de todos os programas de tamanho Y, com Y >> X. Se ela emitir um bipe sempre que um desses programas parar, o último bipe ocorrerá ao simular aquele que para depois de mais passos que BB(Y). Portanto, BBB(X) > BB(Y) >> BB(X)
Se bem me lembro, por causa basicamente da mesma construção, sabendo BB(N) é possível calcular, de forma muito lenta, o problema da parada para programas de tamanho até N; já sabendo BBB(N), é possível calcular de forma ainda muito mais lenta o problema da parada para máquinas de Turing com um oráculo de parada até esse tamanho
Isso é nerd demais para mim
Fico pensando que conhecimento prévio é necessário para entender isso. Saber apenas cálculo básico é suficiente? Que tópicos ou disciplinas específicos seriam uma boa base?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Acompanhar um livro-texto introdutório de ciência da computação teórica ajudaria a entender a maior parte. Estudantes de graduação em ciência da computação costumam ver isso no 1º ou 2º ano, e não é fácil. Na minha universidade era uma das provas mais temidas
O livro introdutório de Hopcroft & Ullmann é bom. Mas há tanto conteúdo relacionado que é melhor vê-lo como um ponto de partida
Muitos cursos de graduação em ciência da computação devem ter disciplinas com materiais abertos
Como se deve ler
1RB2RA1LC_2LC1RB2RB_---2LA1LA?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Por exemplo, se estiver no estado B e o valor da fita na posição atual da cabeça for 0, escreve 2, move a cabeça uma casa para a esquerda e vai para o estado C
Os 3 caracteres significam o símbolo a escrever, o novo estado e a direção do movimento. O estado
---é a parada(estado, valor da fita)é mapeado para uma tripla(novo valor da fita, direção de movimento da cabeça da fita, novo estado)[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA