BB(3, 3) é difícil

• O texto discute uma máquina de Turing de 3 estados e 3 símbolos cuja parada não pode ser provada sem resolver um problema análogo ao de Collatz, e por isso afirma que o problema BB(3,3) é tão difícil quanto resolver esse problema semelhante ao de Collatz.
• O autor menciona uma família de máquinas de Turing (TMs) que exige uma simulação eficiente ou uma solução completa de um problema análogo ao de Collatz para provar se ocorre "quasihalt".
• O autor encontrou exemplos no jogo geral do Busy Beaver e descobriu muitas TMs que fornecem resultados para o jogo Busy Beaver.
• O autor apresenta uma TM chamada "Bigfoot", que é uma das 160 resistências não oficiais restantes do BB(3,3).
• O comportamento de Bigfoot é descrito como a iteração de uma função semelhante à de Collatz sobre b e c, enquanto a mantém uma soma acumulada.
• O autor usa a teoria de cadeias de Markov para descrever o comportamento de Bigfoot e conclui que Bigfoot "provavelmente" nunca para.
• O autor sugere que vivemos em um de dois mundos: um em que Bigfoot para ou um em que ele executa para sempre, e acredita que vivemos no segundo.
• O autor propõe chamar máquinas desse tipo de "Cryptids", fazendo uma analogia com criaturas lendárias como o Monstro do Lago Ness ou o Chupacabra.
• O autor convida ideias sobre como atacar esse problema e expressa esperança de que uma prova para BB(3,3) ainda seja possível.
• O autor conclui dizendo que, pela sua experiência, as perguntas que se pode fazer sobre problemas análogos ao de Collatz se dividem em dois tipos: as relativamente fáceis de provar e as que nem matemáticos sabem como provar.

[GN⁺]

Comentários do Hacker News

• Discussão sobre a complexidade de BB(3, 3), conhecido como um problema do tipo Collatz, mas com o argumento de que talvez não seja necessariamente difícil devido ao comportamento enviesado e ao fato de só precisar considerar uma única trajetória.
• Discussão sobre uma máquina de Turing de 748 estados que para se ZFC (teoria dos conjuntos de Zermelo-Fraenkel com o axioma da escolha) for inconsistente. É expressa confusão sobre as implicações de executar essa máquina por BB(748) passos e sobre uma possível contradição com o segundo teorema da incompletude de Gödel.
• Elogio ao estilo de escrita do autor, por ser claro e conciso e ajudar os leitores a entender o tema sem ser prolixo.
• Levantamento de questões sobre o que significa BB (Busy Beaver) ser não computável e se, conforme BB cresce, seria preciso provar tudo.
• Sugestão de que todos os problemas BB(x, y) podem ser reduzidos a problemas como o de Collatz e, portanto, encontrar BB(x, y) para quaisquer valores de x e y também pode ser reduzido a um problema do tipo Collatz.
• Pergunta sobre por que Beeping Busy Beavers (BBB) podem entrar em quase-parada muito antes de executar por muito mais tempo, com a sugestão de que isso talvez aconteça porque não é necessário usar um estado de parada.
• Dúvida sobre o impacto do problema da parada na indução no mundo real, em um cenário hipotético com um oráculo capaz de decidir se uma dada máquina de Turing imprimirá algo diferente na fita de saída.
• Pergunta sobre o conhecimento prévio necessário para entender esses temas, com pedido de tópicos ou disciplinas específicas que forneçam uma boa base.
• Pergunta sobre como deve ser lida a string específica 1RB2RA1LC_2LC1RB2RB_---2LA1LA.