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.
