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ê 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/C92237A2-F3C5-49F2-A9A5-C1CACCA6EB9A%40gmail.com.
