Caro Walter, Muito obrigado por compartilhar esse material sobre a conjectura de Collatz e o problema do castor ocupado - eu desconhecia essa conexão.
Parece-me que certa variação do método do Lehtonen [1] de codificação das configurações das computações de uma Máquina de Turing na imagem de uma função de Collatz podem funcionar tanto para a generalização que você propôs quanto aquela do Lu Pei. Além das codificações específicas para cada uma dessas generalizações, também acredito que será necessário um tipo de análise da trajetória dos inteiros nos moldes que o Ferguson explorou [2] - apesar dele o ter feito para séries de potência, penso que a análise para generalizações com funções módulo deve ser análoga. Além do problema da decidibilidade, chamou-me à atenção também a abordagem do Rham et al. [3]. Trata-se de um trabalho em desenvolvimento, mas pelo que entendi é algo sério e bem formulado. Eles desenvolvem uma extensão da aritmética modular, chamada golden arithmetics, que permite avaliar as características dos sistemas dinâmicos associados às funções de Collatz - os gráficos gerados são lindos! Em particular, a golden arithmetics permite ver o problema de Collatz como uma forma de jogo da hidra. Isso indica que talvez a conjectura de Collatz seja independente da aritmética de Peano. A despeito de se conseguir provar isso, creio que se pode descobrir fatos muito profundos estudando generalizações da conjectura de Collatz. Escreverei para você em privado, pois talvez eu consiga ajudá-lo nesta empreitada. Decidi compartilhar publicamente essas observações porque acredito que possa ser do interesse de alguns saber que as preocupações exploradas pelo Gödel e pelo Turing lá nos idos anos 1930 sobre a natureza das continhas que aprendemos na escola ainda nos reserva muitas surpresas, para além do fenômeno da incompletude aritmética e da universalidade computacional. Abraços, Anderson [1] Lehtonen. Two undecidable variants of Collatz’s problems. Theoretical Computer Science 407 (2008) 596-600. [2] Fergson. Entire functions with undecidable arithmetic properties. Journal of Number Theory 223 (2021) 255-266. [3] Rahn, Henkel, Ghosh, Sultanow, Aberkane. An algorithm for linearizing Collatz convergence. 2021. hal-03286608 Em qua., 21 de jul. de 2021 às 17:07, Famadoria <famado...@gmail.com> escreveu: > Te mando. > > Sent from my iPhone > > > On 21 Jul 2021, at 14:47, Eduardo Ochs <eduardoo...@gmail.com> wrote: > > > > Os mortais querem saber os detalhes do que os deuses demonstraram pelo > telefone > > > >> On Wed, 21 Jul 2021 at 14:36, Walter Carnielli <walte...@unicamp.br> > wrote: > >> > >> Oi Doria, > >> > >> mas se você se provaram, mesmo sem saber o significado, pode ser muito > interessante . > >> > >> Como foi essa prova? > >> Onde está essa prova ? > >> > >> abraço > >> W. > >> > >> Em qua., 21 de jul. de 2021 09:54, Famadoria <famado...@gmail.com> > escreveu: > >>> > >>> O Kreisel, há uns trinta anos, repassou ao Newton e a mim uma > conjectura segundo a qual a função contraexemplo para P=NP cresceria nos > picos ao menos tão rápido quanto o Busy Beaver. Embora tenhamos dúvidas > sobre o significado disso, provamos esse resultado nalgum canto. > >>> > >>> Sent from my iPhone > >>> > >>>> On 20 Jul 2021, at 17:56, Walter Carnielli <walte...@unicamp.br> > wrote: > >>>> > >>>> O "Problema do Castor Ocupado" (Busy Beaver ) foi proposto por TIbor > >>>> Rado em 1962 como um exemplo concreto de uma função que nao é > >>>> computável por Máquinas de Turing (cresce mais rápido que qualquer > >>>> função computável). > >>>> > >>>> Rado propôs em 1962 uma competição, para que se escrevesse a menor > >>>> máquina Busy Beaver (BB). Computadores cada vez mais poderosos > >>>> tornaram possível computar limites inferiores para esses valores. > >>>> > >>>> > >>>> https://arxiv.org/abs/0906.3749 > >>>> > >>>> Como apareceu na Lista FOM, Nick Drozd acaba de anunciar uma Máquina > >>>> de Turing de 4 estados e 2 símbolos que executa 32.779.478 de > >>>> operações e depois disso produz uma fita em branco e segue para a > >>>> esquerda sem parar (para sempre), > >>>> > >>>> Esta minúscula Máquina de Turing é a campeã até agora da competição > >>>> BB, mas o mais interessante são as conexões desse problema com o > >>>> Problema de Collatz. Não deixa de indicar uma "incomputabilidade" > >>>> global dos problemas de Collatz, conforme > >>>> > >>>> > >>>> https://www.sligocki.com/2021/07/17/bb-collatz.html > >>>> > >>>> Para quem se interesse, seguem os trabalhos sobre indecidibilidade > >>>> de casos mais abstratos de variantes do Problema de Collatz: > >>>> > >>>> Conway, "Unpredictable iterations", 1972 > >>>> Kurtz and Simon, "The Undecidability of the Generalized Collatz > Problem", 2007 > >>>> Lehtonen, "Two undecidable variants of Collatz’s problems", 2008 > >>>> > >>>> Minha própria versão dos Problemas de Collatz ainda aguardam > >>>> algum resultado de indecidibilidade,na direção do que conjecturei > >>>> (mas nao consegui provar nada...) > >>>> > >>>> > >>>> http://www.math.nthu.edu.tw/~amen/2015/AMEN(150711).pdf > >>>> > >>>> No capítulo 8 de "Computabilidade, funções computáveis, lógica e os > >>>> fundamentos da matemática". damos uma receita detalhada de como > >>>> demonstrar que o Castar Ocupado ganha de qualquer Máquina de Turing. > >>>> > >>>> Abraços, > >>>> > >>>> Walter > >>>> > >>>> =========================== > >>>> Walter Carnielli, Professor > >>>> Centre for Logic, Epistemology and the History of Science and > >>>> Department of Philosophy > >>>> University of Campinas –UNICAMP > >>>> 13083-859 Campinas -SP, Brazil > >>>> Phone: (+55) (19) 3521-6517 > >>>> Institutional e-mail: walter.carnie...@cle.unicamp.br > >>>> Website: http://www.cle.unicamp.br/prof/carnielli > >>>> > >>>> -- > >>>> Você está recebendo esta mensagem porque se inscreveu no grupo > "LOGICA-L" dos Grupos do Google. > >>>> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, > envie um e-mail para logica-l+unsubscr...@dimap.ufrn.br. > >>>> Para ver esta discussão na web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAOrCsLe4JRsdraC53w00h%3DOsWVrwuam9ceMRXVE62sJ9cSkR2Q%40mail.gmail.com > . > >> > >> -- > >> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos > Grupos do Google. > >> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, > envie um e-mail para logica-l+unsubscr...@dimap.ufrn.br. > >> Para ver essa discussão na Web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAOrCsLca-DJ%3DzAFexViR4eErqviz8QgvfAxwhjXKnU2E_49Pbw%40mail.gmail.com > . > > -- > Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" > dos Grupos do Google. > Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie > um e-mail para logica-l+unsubscr...@dimap.ufrn.br. > Para ver esta discussão na web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/5DF668ED-4901-477C-A799-B2B05C3B95D0%40gmail.com > . > -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+unsubscr...@dimap.ufrn.br. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAJrBeCUzCu%2BdD3gDAjdX6PaUu8jXa8A%2BMt%2B7S8UP9EcugqK%2B7Q%40mail.gmail.com.
