Os mortais querem saber os detalhes do que os deuses demonstraram pelo telefone
On Wed, 21 Jul 2021 at 14:36, Walter Carnielli <[email protected]> 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 <[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ê 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 [email protected]. > 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 [email protected]. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CADs%2B%2B6hktEDxDt5QcoTe5KUnFEqTBWtMOeCuLyuTA0ap0O_crA%40mail.gmail.com.
