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 <[email protected]> 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 <[email protected]> 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: [email protected] > > 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 [email protected]. > > 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 [email protected]. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAOrCsLca-DJ%3DzAFexViR4eErqviz8QgvfAxwhjXKnU2E_49Pbw%40mail.gmail.com.
