Algoritmo do castor

Em seu artigo de 1962, Tibor Radó introduziu o jogo do castor "ocupado" ("the busy beaver game") como se segue: Considerando uma máquina de Turing com um alfabeto binário {0, 1} e n estados operacionais (freqüentemente rotulados de 1, 2, ... n ou A, B, C, ...) e um estado adicional de parada. Sua definição de uma máquina de Turing foi a seguinte: Comece com uma fita em branco (ou seja, cada célula tem um 0 nela). Acione a máquina (aplicando iterativamente a função de transição). Se ela para, anote o número de 1s que sai na fita. O n-state busy beaver (BB-n) game é uma competição para encontrar uma máquina de Turing de n estados que deixa o maior número de 1s em sua fita antes de parar. Radó declarou: a fim de participar neste concurso você deve enviar a descrição de uma máquina de Turing de n-estados que pára junto com o número de passos necessários para um árbitro qualificado, que deve testar a sua validade. É importante que você forneça o número de passos tomadas até a parada, porque se você não informar este número e sua máquina de Turing não parar, não há nenhum algoritmo geral que o árbitro possa usar para provar que não será interrompido. Considerando que, se você especificar o número de passos, juntamente com sua máquina candidata, o juiz pode (dado tempo suficiente) decidir se a sua máquina irá ou não parar neste número de passos. (No entanto, os árbitros podem ter dificuldade em testar os atuais campeões de correção, dado o número extremamente elevado de medidas tomadas.)

A função do algoritmo do castor Σ(n) é definida como o número de 1s que o máquina de Turing campeã imprime se dada uma fita em branco (ou alimentada com 0's ) no início. Radó demonstrou que existe um campeão bem definido para o estado-n do jogo castor ocupado: Há um número finito de máquinas de Turing com n estados e 2 símbolos (especificamente, há [4 (n+1)] 2n delas) . Além disso, é trivial que algumas destas são máquinas com parada, ou seja, existe pelo menos uma máquina de Turnig de n-estados, 2-símbolos que irá parar, para todo n. Uma vez que σ(M) é um número finito, não-negativo para qualquer M em En, e uma vez que En é um conjunto finito não-vazio, Σ(n) é um número bem definido, finito e não-negativo para qualquer n. Esta Σ é a função do castor ocupado e qualquer máquina de n-estados e 2-símbolos M na qual σ(M) = Σ(n) (ie, que atinge o máximo) é chamada de castor ocupado (busy beaver). Note-se que pode haver mais de um castor ocupado de n-estados, por exemplo, se σ(M1) = σ(M2) = Σ (n).

Radó partiu para provar que não há função computável para Σ(n), ou seja, para qualquer função computável dada f, deve haver algum n ( e, por conseguinte, pode-se mostrar, infinitamente muitos n), para o qual Σ(n) > f(n). Σ, portanto, não é computável. Além disso, isso implica que é indecidível por um algoritmo geral se um determinado candidato é um campeão para o algoritmo do castor ocupado (pois se pudéssemos de maneira algorítmica determinar se existe ou não um determinado candidato campeão, poderíamos então determinar o valor apropriado de Σ simplesmente listando todos os candidatos e testá-los). Embora não haja nenhum algoritmo único A que gera o número Σ(n) para cada entrada de n (isto é, a função Σ é não computável), há, para cada entrada n, um algoritmo An que gera o número Σ(n) (ver exemplos). Em outras palavras, existe um infinita seqüência de algoritmos (A0, A1, A2, ...) que "calcula" a função Σ, mas esta seqüência infinita de algoritmos em si não é um algoritmo (porque um algoritmo é, por definição, um objeto finito).

Shen Lin provou que Σ(3) = 6 em seu artigo de 1965 com Radó, Computer Studies of Turing Machine Problems. Para provar isso ele usou uma outra função de extrema para parar máquinas de Turing de n-estados , a função de deslocamentos máximos,S, definida como se segue: Uma vez que estas máquinas de Turing são obrigadas a ter um deslocamento em cada transição ou "passo" (incluindo qualquer transição para um estado de parada), a função de máximos-deslocamentos é, ao mesmo tempo uma função de passos-máximos. Agora, se você conhece S( n), você pode executar todas as máquinas de Turing de n-estados para S(n) passos seqüencialmente e anotar uma máquina que parou com mais 1s na fita, encontrado então um algoritmo para o castor ocupado e o número de 1s que este escreve é Σ(n) (todas as máquinas de Turing de n-estados que pararem terão parado em S(n) passos). Assim, o estudo da função de deslocamentos máximos foi estreitamente relacionado com o estudo da função do castor ocupado.

Os valores da função de Σ(n) e S(n) são apenas conhecidos exatamente para n < 5. O atual campeão para um castor ocupado de 5-estados produz 4.098 1s, em 47.176.870 passos (descoberto por Heiner Marxen e Buntrock Jürgen em 1989), mas continua a haver cerca de 40 máquinas com comportamentos não regulares, que acredita-se que nunca param, mas que ainda não foi comprovada que rodam infinitamente. Até o momento o recorde de um castor ocupado para 6-estados produz mais de 102879 1s, com mais de 102879 passos (encontrado por Terry e Ligocki Shawn em 2007). Como mencionado acima, estes castores ocupados são máquinas de Turing de 2-símbolos. Milton Green, em seu artigo de 1964 "A Lower Bound on Rado's Sigma Function for Binary Turing Machines", construiu um conjunto de máquinas de Turing demonstrando que onde ↑ {\displaystyle \uparrow } é uma notação de Knuth e A é a função de Ackermann). Em contraste, o limite atual em Σ(6) é 10 18267 {\displaystyle 10^{18267}} que é menos que 3 3 3 3 {\displaystyle 3^{3^{3^{3}}}} , minúsculo em comparação.

Para qualquer modelo de computação existem análogos simples do castor ocupado. Por exemplo, a generalização para as máquinas de Turing com n estados e m símbolos define as seguintes funções generalizadas para o castor ocupado: Por exemplo, a mais antiga máquina, em execução, de 3-estados e 3-símbolos encontrada até agora roda 119.112.334.170.342.540 passos antes de parar. A mais longa máquina, em execução, de 6-estados e 2-símbolos que tem a propriedade adicional de inverter o valor da fita em cada passo produz 6.147 1s depois de 47.339.970 passos. Então SRTM(6) ≥ 47.339.970 e ΣRTM(6) ≥ 6.147. Do mesmo modo podemos definir uma analogia para a função Σ de máquina de registos como o maior número que pode estar presente em qualquer registo em parada, para um determinado número de instruções.

Além de constituir um jogo matemático de certa forma desafiador, as funções de castor ocupado tem uma aplicação profunda. Muitos problemas abertos em matemática poderiam ser resolvidos de uma forma sistemática, dando-se o valor de S(n) para um n suficientemente grande. Considere qualquer conjectura que poderia ser desprovada através de um contra-exemplo entre um número contável de casos (por exemplo a Conjectura de Goldbach). Escreva um programa de computador que testa seqüencialmente esta conjectura para valores cada vez maiores (no caso da Conjectura de Goldbach, consideraremos cada número par ≥ 4 seqüencialmente e testaremos se é ou não é a soma de dois números primos). Vamos considerar que este programa seja simulado por uma máquina de Turing de n-estados (embora pudéssemos alternativamente definir a função do castor ocupado por qualquer linguagem de programação bem definida). Se for encontrado um contra-exemplo (um número par ≥ 4 que não é a soma de 2 primos em nosso exemplo), ele pára e avisa-nos. No entanto, se a conjectura é verdadeira, então o nosso programa não será interrompido. (Este programa pára apenas se constatar um contra-exemplo.)

Suponha que S(n) é uma função computável e faça-se AvaliaS denotar uma Máquina de Turing avaliando S(n). Dada uma fita com n 1s se produzirá S(n) 1s na fita e então se irá parar. Faça-se Limpa denotar uma máquina de Turing fazendo a limpeza da seqüência de 1s inicialmente escrita na fita. Faça-se Dobra denotar uma máquina de Turing que avalia a função n + n. Dada uma fita com n 1s se produzirá 2n 1s na fita e então parar. Vamos criar a Dobra | AvaliaS | Limpa e fazer ns ser o número de estados desta máquina. Façamos Criar_ns denotar uma máquina de Turing criando ns 1s em uma fita inicialmente em branco. Esta máquina pode ser construída de uma forma trivial para ter ns estados (o estadoi, escreve 1, move a cabeça à direita e muda para o estado i+ 1, exceto o estado ns, que pára). Façamos N denotar a soma ns + ns. Façamos ComporS denotar a composição Crie_ns|Dobra| AvaliaS|Limpa. Repare que esta máquina tem Nestados. Começando com uma fita inicialmente em branco ele primeiro cria uma seqüência de ns 1s e, em seguida, os dobra, produzindo uma seqüência de N 1s. Então ComporS irá produzir S(N) 1s na fita, e, finalmente, ele irá limpar todos os 1s e depois parar. Mas a fase de limpeza vai continuar pelo menos S(N) etapas, de modo que o tempo de trabalho dos ComporS é estritamente maior que S(N), o que contradiz a definição da função S(n).

Estas são as tabelas das regras para as máquinas de Turing que geram Σ(1) e S(1), Σ(2) e S(2), Σ(3) (mas não S(3)), Σ(4) e S(4), e o melhor limite inferior conhecido para Σ(5) e S(5), e Σ(6) e S(6). Nas tabelas, as colunas representam o estado atual e as linhas representam o símbolo atual de leitura da fita. As entradas da tabela indicam o símbolo a se escrever na fita, a direção do movimento, e o novo Estado (nessa ordem). Cada máquina começa em um estado com uma fita infinita que contém todas as posições preenchidas com 0s. Assim, o símbolo inicial de leitura da fita é um 0. Resultado da execução: (começa na posição sublinhada, para na posição que está em em negrito)

A tabela a seguir lista os valores exatos e alguns limites inferiores conhecidos para S(n, m) e Σ(n, m) para os problemas generalizados do castor ocupado. Os valores exatos conhecidos são mostrados como números inteiros simples e os limites inferiores conhecidos são precedidos por um símbolo de maior ou igual (≥). Nota: as entradas listadas como "???" são limitadas a partir de baixo, pelo máximo de todas as entradas para a esquerda e acima. Estas máquinas, ou não foram investigadas ou foram posteriormente superadas por uma máquina que as precederam. As máquinas de Turing, que permitam atingir estes valores estão disponíveis em ambas as páginas web: Heiner Marxen's e Pascal Michel's. Cada um desses sites também contém uma análise das máquinas de Turing e referências para a prova dos valores exatos.