Em Teoria da Computação, o algoritmo do castor (busy beaver) é uma máquina de Turing que, após iniciada em uma fita vazia (todas as posições em branco ou com 0), executa o maior número de passos possível, mas eventualmente para. Esta máquina atinge o limite na quantidade de tempo e espaço que uma máquina de Turing com parada da mesma classe pode consumir.

A função busy beaver quantifica estes limites e é um exemplo de uma função não computável. Na verdade, pode ser mostrado que ela cresce mais rapidamente do que qualquer função computável. O conceito foi introduzido pela primeira vez por Tibor Radó como o jogo do castor "ocupado" em seu artigo de 1962, "On Non-Computable Functions".

O jogo do castor "ocupado" 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: A máquina executa em uma fita bidirecional infinita (ou sem limites). A função de transição da máquina obtém 2 entradas: o estado atual da máquina; e o símbolo na fita na posição atual e produz 3 saídas: um símbolo a ser escrito sobre o símbolo atualmente na posição da fita (embora possa ser o mesmo símbolo que já havia na fita); uma direção de movimento (esquerda ou direita); e o novo estado para o qual transitar (que pode ser o mesmo que ele estava ou ainda ser o estado de parada). Assim, a máquina de Turing é uma máquina de estados, cuja definição consiste em uma tabela finita de 5-tuplas da forma (estado atual, o símbolo atual, símbolo de escrever, o sentido da mudança, o próximo estado). A máquina para se e quando ela atinge o estado especial de parada.

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) 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.

Agora define-se:

um conjunto finito, não vazio de máquinas de Turing com parada de n-estados, 2-símbolos do tipo descrito na seção anterior (fita infinita nos dois sentidos, uma função de transição definida pelas 5-tuplas, etc.). é o número de 1s deixados na fita após a máquina de Turing ter executado até o fim (até atingir o estado de parada) em uma fita vazia (definida para todas as máquinas com parada em ). (O maior número de 1s escrito por qualquer máquina de Turing com parada com n-estados e 2-símbolos)

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).

Não-Computabilidade de Σ

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).

Para um n suficientemente pequeno, é, de fato, prático calcular os valores específicos da função do castor ocupado. Por exemplo, não é difícil mostrar que Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, e com cada vez mais dificuldade pode ser demonstrado que Σ(3) = 6 e Σ( 4) = 13. Σ(n) ainda não foi determinado para qualquer instância de n> 4, apesar de limites inferiores terem sido estabelecidos (consulte a seção de valores conhecidos abaixo).

Função de deslocamentos máximos 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:

  o número de deslocamentos M faz antes de parar, para qualquer M em En,   o maior número de deslocamentos feitos por qualquer máquina de Turing que pára de n-estados e 2-símbolos.

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.

Desigualdades relacionando Σ e S incluem o seguinte (de [Ben Amram, et al., 1996]), que são válidas para todo n ≥ 1:

e um melhoria por análise assintótica (de [Ben Amram, Petersen, 2002]): existe uma constante c, tal que para todo n ≥ 2,

Valores conhecidos

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 é uma notação de Knuth e A é a função de Ackermann).

Deste modo

(com termos na torre exponencial).

, onde o número g1 é o valor enorme de partida na seqüência que define o número de Graham.

Em contraste, o limite atual em Σ(6) é que é menos que , minúsculo em comparação.

Generalizações

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:

Σ(n, m): o maior número de não-zeros escritos por uma máquina de n-estados, m-símbolos iniciada em uma fita inicialmente branca antes de parar, e S(n, m): o maior número de passos necessários para uma máquina de n-estados, m-símbolos iniciada em uma fita inicialmente branca antes de parar.

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.

Aplicaçõ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.Chaitin 1987

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.)

Agora, este programa é simulado por uma máquina de Turing de n-estados, assim, se sabemos S(n), podemos decidir (em uma quantidade finita de tempo) se ou não ela vai parar, simplesmente executando a máquina com este número de passos. E se, após S(n) passos, a máquina não parar, nós saberemos que ela nunca irá e que, portanto, não há contra-exemplos para a conjectura dada (isto é, nenhum número par que não é a soma de dois números primos). Isso provaria que a conjectura é verdadeira.

Assim, os valores específicos (ou limites superiores) para S(n) poderiam ser utilizados de forma sistemática para resolver muitos problemas abertos em matemática (em teoria). No entanto, os resultados atuais sobre o problema do castor ocupado sugerem que isto não será prático, por duas razões: