Algoritmo do castor – Wikipédia, a enciclopédia livre

As referências deste artigo necessitam de formatação. Por favor, utilize fontes apropriadas contendo título, autor e data para que o verbete permaneça verificável. (Janeiro de 2014)

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

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:

1. o estado atual da máquina; e
2. o símbolo na fita na posição atual

e produz 3 saídas:

1. 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);
2. uma direção de movimento (esquerda ou direita); e
3. 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) é 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)] ²ⁿ 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:

• ${\displaystyle E_{n}}$ 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.).
• ${\displaystyle \sigma (M)}$ é o número de 1s deixados na fita após a máquina de Turing ${\displaystyle M}$ ter executado até o fim (até atingir o estado de parada) em uma fita vazia (definida para todas as máquinas com parada ${\displaystyle M}$ em ${\displaystyle E_{n}}$).
• ${\displaystyle \Sigma (n)=\max\{\sigma (M)|M\in E_{n}\}}$ (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 E_n, e uma vez que E_n é 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 σ(M₁) = σ(M₂) = Σ (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 A_n que gera o número Σ(n) (ver exemplos). Em outras palavras, existe um infinita seqüência de algoritmos (A₀, A₁, A₂, ...) 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).

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:

• ${\displaystyle s(M)=\,\!}$  o número de deslocamentos M faz antes de parar, para qualquer M em E_n,
• ${\displaystyle S(n)=\max\{s(M)|M\in E_{n}\}=\,\!}$  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:

${\displaystyle S(n)\geq \Sigma (n)\,\!}$

${\displaystyle S(n)\leq (2n-1)\Sigma (3n+3)\,\!}$

${\displaystyle S(n)<\Sigma (3n+6)\,\!;}$

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

${\displaystyle S(n)\leq \Sigma (n+\lceil 8n/\log _{2}n\rceil +c).\,\!}$

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 10²⁸⁷⁹ 1s, com mais de 10²⁸⁷⁹ 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

${\displaystyle \Sigma (2k)>3\uparrow ^{k-2}3>A(k-2,k-2)\quad (k\geq 2)}$,

onde ${\displaystyle \uparrow }$ é uma notação de Knuth e A é a função de Ackermann).

Deste modo

${\displaystyle \Sigma (10)>3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3^{3^{3}}=3^{3^{3^{.^{.^{.^{3}}}}}}}$ (com ${\displaystyle 3^{27}=7.625.597.484.987}$ termos na torre exponencial).

${\displaystyle \Sigma (12)>3\uparrow \uparrow \uparrow \uparrow 3=g_{1}}$, onde o número g₁ é o valor enorme de partida na seqüência que define o número de Graham.

Em contraste, o limite atual em Σ(6) é ${\displaystyle 10^{18267}}$ que é menos que ${\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:

1. Σ(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
2. 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 S_RTM(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.^[1]

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:

• É extremamente difícil provar os valores para a função do castor ocupado (e a função de deslocamento máximo). Isto só foi comprovado para máquinas extremamente pequenas, com menos de 5 estados, enquanto seria presumivelmente necessário pelo menos 20-50 estados para fazer uma máquina útil. Além disso, cada valor exato conhecido de S(n) foi comprovada pela enumeração de todas as máquinas de Turing de n-estados testando ainda a parada em cada uma. Seria preciso calcular S(n) por algum outro método menos direto para que realmente fosse útil.
• Mas, mesmo se ninguém encontrar uma melhor maneira de calcular S(n), os valores da função do castor ocupado (e a função de máximo deslocamento) ficam muito grandes rápidamente. S(6) > 10³⁶⁵³⁴ exigem uma aceleração especial baseada em padrões para ser capaz de simular até a conclusão. Da mesma forma, sabemos que ${\displaystyle S(10)>\Sigma (10)>3\uparrow \uparrow \uparrow 3}$ é um número gigantesco. Assim, mesmo se soubéssemos, digamos, S(30), pode ser completamente irracional executar este número de passos, qualquer que seja a máquina.

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 n_s ser o número de estados desta máquina. Façamos Criar_n_s denotar uma máquina de Turing criando n_s 1s em uma fita inicialmente em branco. Esta máquina pode ser construída de uma forma trivial para ter n_s estados (o estadoi, escreve 1, move a cabeça à direita e muda para o estado i+ 1, exceto o estado n_s, que pára). Façamos N denotar a soma n_s + n_s.

Façamos ComporS denotar a composição Crie_n_s|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 n_s 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).

A não-computabilidade de Σ(n) pode ser provado de forma semelhante. Na prova anterior, deve-se trocar a máquina AvaliaS com AvaliaΣ e Limpa com Incremento - uma MT simples, à procura de um primeiro 0 na fita e substituindo-o por 1.

A não-computabilidade de S(n) também pode ser trivialmente estabelecido por referência ao problema da parada. Como S(n) é o número máximo de passos que podem ser executados por uma máquina de Turing com parada, qualquer máquina que funciona por mais passos devem ser sem parada. Pode-se então determinar se uma máquina de Turing com n estados para executando-a para S(n) passos; se ela ainda não parou, ela nunca irá parar. Como sendo capaz de calcular a S(n) seria uma solução para o problema comprovadamente não-computável da parada, segue-se que S(n) também deve ser não-computável.

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
0	P1,R,H
1	Nunca usado

Resultado: 0 0 1 0 0 (1 passo, um "1" no total)

	A	B
0	P1,R,B	P1,L,A
1	P1,L,B	P1,R,H

Resultado: 0 0 1 1 1 1 0 0 (6 passos, quatro "1"s no total)

	A	B	C
0	P1,R,B	P0,R,C	P1,L,C
1	P1,R,H	P1,R,B	P1,L,A

Resultado: 0 0 1 1 1 1 1 1 0 0 (14 passos, seis "1"s no total).

Note que, ao contrário das máquinas anteriores, este é um campeão apenas para Σ, mas não para S. (S (3) = 21.)

	A	B	C	D
0	P1,R,B	P1,L,A	P1,R,H	P1,R,D
1	P1,L,B	P0,L,C	P1,L,D	P0,R,A

Resultado: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 passos, treze "1"s no total). Executando este exemplo na Máquina de Turing (já pré-programada) existente no site http://morphett.info/turing/turing.html, obtem-se o resultado: 10111111111111 (108 passos, treze "1"s e um "0").

	A	B	C	D	E
0	P1,R,B	P1,R,C	P1,R,D	P1,L,A	P1,R,H
1	P1,L,C	P1,R,B	P0,L,E	P1,L,D	P0,L,A

Resultado: 4098 "1"s com 8191 "0"s intercalados em 47.176.870 passos.

	A	B	C	D	E	F
0	P1,R,B	P1,L,C	P1,L,D	P1,L,E	P1,L,A	P1,L,E
1	P0,L,E	P0,R,A	P0,R,C	P0,L,F	P1,L,C	P1,R,H

Resultado: ≈4,640 × 10¹⁴³⁹ "1"s em ≈2,584 × 10²⁸⁷⁹ passos.

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.

Valores de S(n,m):

	2-estados	3-estados	4-estados	5-estados	6-estados
2-símbolos	6	21	107	≥ 47.176.870	≥ 7,412 × 1036534
3-símbolos	≥ 38	≥ 119.112.334.170.342.540	≥ 1,0 × 1014072	???	???
4-símbolos	≥ 3.932.964	≥ 5,2 × 1013036	???	???	???
5-símbolos	≥ 1,9 × 10704	???	???	???	???
6-símbolos	≥ 2,4 × 109866	???	???	???	???

Valores de Σ(n,m):

	2-estados	3-estados	4-estados	5-estados	6-estados
2-símbolos	4	6	13	≥ 4.098	≥ 3,515 × 1018267
3-símbolos	≥ 9	≥ 374.676.383	≥ 1,3 × 107036	???	???
4-símbolos	≥ 2.050	≥ 3,7 × 106518	???	???	???
5-símbolos	≥ 1,7 × 10352	???	???	???	???
6-símbolos	≥ 1,9 × 104933	???	???	???	???

• The page of Heiner Marxen, who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
• Pascal Michel's Historical survey of busy beaver results which also contains best results and some analysis.
• The page of Penousal Machado's Genetic Beaver Project uses Evolutionary Computation to find new candidates to the busy beaver Problem
• Definition of the class RTM - Reversal Turing Machines, simple and strong subclass of the TMs.
• The "Millennium Attack" at the Rensselaer RAIR Lab on the busy beaver Problem.
• Aaronson, Scott (1999), Who can name the biggest number?
• Weisstein, Eric W. «Busy Beaver». MathWorld (em inglês) 
• Busy Beaver by Hector Zenil, Wolfram Demonstrations Project.