O castorzinho ocupadíssimo
71 views
Skip to first unread message
Walter Carnielli
Jul 20, 2021, 8:56:14 PM7/20/21
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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.c...@cle.unicamp.br
Website: http://www.cle.unicamp.br/prof/carnielli
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.c...@cle.unicamp.br
Website: http://www.cle.unicamp.br/prof/carnielli
Famadoria
Jul 21, 2021, 12:54:28 PM7/21/21
to Walter Carnielli, Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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 <walt...@unicamp.br> wrote:
>
> O "Problema do Castor Ocupado" (Busy Beaver ) foi proposto por TIbor
> --
> 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+u...@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.
Sent from my iPhone
> On 20 Jul 2021, at 17:56, Walter Carnielli <walt...@unicamp.br> wrote:
>
> O "Problema do Castor Ocupado" (Busy Beaver ) foi proposto por TIbor
> 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+u...@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.
Walter Carnielli
Jul 21, 2021, 5:36:35 PM7/21/21
to Famadoria, Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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.
Eduardo Ochs
Jul 21, 2021, 5:47:42 PM7/21/21
to Walter Carnielli, Famadoria, Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
Os mortais querem saber os detalhes do que os deuses demonstraram pelo telefone
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
> 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+u...@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.
Famadoria
Jul 21, 2021, 8:07:36 PM7/21/21
to Eduardo Ochs, Walter Carnielli, Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
Te mando.
Sent from my iPhone
> On 21 Jul 2021, at 14:47, Eduardo Ochs <eduar...@gmail.com> wrote:
>
> Os mortais querem saber os detalhes do que os deuses demonstraram pelo telefone
Sent from my iPhone
> On 21 Jul 2021, at 14:47, Eduardo Ochs <eduar...@gmail.com> wrote:
>
> Os mortais querem saber os detalhes do que os deuses demonstraram pelo telefone
Anderson Beraldo de Araújo
Jul 24, 2021, 10:31:11 PM7/24/21
to Famadoria, Eduardo Ochs, Walter Carnielli, Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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.
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
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.
Reply all
Reply to author
Forward
0 new messages