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.
