Castor de cérebro ocupado

13

Escreva um programa de cérebro com até 256 caracteres que execute o máximo de etapas possível, mas não faça um loop infinito. O programa pode não receber nenhuma entrada.

Mais especificamente:

  • Suponha um número infinito de células à direita.
  • A <quando na célula mais à esquerda não faz nada.
  • A -quando o valor da célula é zero, define a célula como 255.
  • Todas as instruções +-<>.contam como uma etapa quando executadas.
  • Quando um [ou ]é encontrado, conta como uma etapa. No entanto, se a condição for verdadeira e fluxo de controle salta, o correspondente ]ou [se não outra vez conta como um passo.
  • A solução que executa mais etapas vence.
  • Se houver algum tipo de padrão em sua solução, é recomendável atribuir uma função para quantas etapas um programa semelhante nlevaria, mas não obrigatório.
  • Para contar as instruções, você pode usar este intérprete modificado :

Exemplo:

++[-]

As instruções encontradas são ++[-]-]e o programa foi executado por 7 etapas.

Anton Golov
fonte
6
Eu ficaria surpreso se o vencedor terminasse sem exceder a contagem do intérprete. Lembre-se de que o castor de 6 estados da TM leva pelo menos 10 ** 36534 etapas.
Peter Taylor
Concordo. Parece altamente provável que você possa escrever um programa de <50 char BF que pode durar anos. Eu vou começar.
Captncraig
Assinado. A página de pesquisa do Busy Beaver em drb.insel.de/~heiner/BB é muito interessante, especialmente o fato de os programas de gravação serem extremamente longos e ainda terem resultados exatos (consulte drb.insel.de/~heiner/BB/bb -xlist.txt ) - simulações lembrar estados, construir "macros" para salvar as etapas de simulação etc.
schnaader
4
@AntonGolov: infelizmente, neste universo, RAMs e HDs não converter para dispositivos de armazenamento infinitas quando você tentar armazenar bignums maiores que 256 ^ tamanho em bytes sobre eles ...
deixou de vez counterclockwis
1
@boothby É perfeitamente possível fazer cálculos exatos envolvendo transcendentais nos computadores atuais. Os componentes dos valores apenas precisam ser armazenados em uma representação mais abstrata do que a normal floatou doubleprimitiva usada para a computação cotidiana em geral. (Nesse ponto, o computador é na maior parte apenas manipulando cordas de que representam a equação)
AJMansfield

Respostas:

15

Aqui está um programa de 41 caracteres que acaba, deixando mais de 10 ↑ (10 ↑ 28) células contíguas definidas como 1 (portanto, o número de instruções executadas é muito maior que isso):

>+>+>+>+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]

Se não me engano, essa é uma tradução correta do programa a seguir na linguagem da variante BF que usa um único bit para cada célula da memória (ou seja, conteúdo da célula 0..1 em vez de 0..255, então '+' age simplesmente para mudar o valor do bit):

>+>+>+>+[+>[>]+[+>[>]+[+>[>]+[<]+<]+<]+<]

O valor exato (o número de 1 bits adjacente) produzido pelo último programa é

3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.


O programa acima inicializa e calcula uma função que cresce como 2 ↑↑ x (na notação de seta para cima Knuth ). Conversão semelhante de um programa variante-BF que inicializa e calcula uma função que cresce como 2 ↑ 23 x fornece o seguinte programa de 256 caracteres:

>+>+>+>+>+>+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+

que eventualmente pára, deixando mais de 2 ↑ 23 6 células adjacentes definidas como 1 (portanto, o número de etapas é enormemente maior que isso).

NB-1 : 2 ↑ 23 6 é um número "inconcebivelmente grande"; por exemplo, mesmo 2 ↑ 4 6 = 2 ↑↑↑↑ 6 já ultrapassa o primeiro termo (3 ↑↑↑↑ 3) na sequência usada para calcular o número de Graham .

NB-2 : Eu acho que é provável que 256 caracteres sejam suficientes para um programa BF inicializar e calcular uma função com saída muito maior que o número de Graham - se eu encontrar tempo, talvez eu tente escrever um.

NB-3 : Caso alguém esteja interessado na origem dos programas acima, aqui estão alguns recursos de programação para "Brainf * ck F" , com vários programas escritos em Python. ("Brainf * ck F", ou apenas "F", é o que chamei de uma variante completa de Turing da linguagem Smallf * ck .) Acabei de carregar esses arquivos, que estão off-line há vários anos e, por enquanto, página da web vinculada é apenas um "arquivo" - consulte o arquivo Busy_Beavers.txt para obter uma discussão detalhada relevante para os programas acima.

res
fonte
Este é um vencedor claro no momento (a menos que eu esteja subestimando os outros). Mais sugestões são bem-vindas, mas vou marcar como aceito por enquanto. Se alguém discordar, por favor, comente.
Anton Golov 20/02/2012
Quando você chega a esse nível, torna-se irreal assumir que você tem um intérprete com memória infinita. Estou começando a pensar que esse seria um desafio melhor com a memória de empacotamento finito, para que possamos executar as respostas.
Captncraig
9

Aqui está um belo personagem de 39 caracteres:

-[>-[>-[-[>+<-]<[>+<-]<[>+<-]>>>]<-]<-]

Basicamente, faz um trenó com 3 espaços de largura que se move para a direita e diminui um. Concluído em 31.919.535.558 instruções, com o loop mais interno executando 256 ^ 3 vezes. Eu ainda tenho muito espaço para estender isso muito longe, com uma taxa de 14 caracteres para outra ordem de magnitude para o tempo de execução.

Funciona em qualquer intérprete com memória ilimitada ou com quebra automática de memória.

Deixo um exercício para o leitor determinar quando a versão melhorada por 2 loops será concluída:

-[>-[>-[>-[>-[-[>+<-]<[>+<-]<[>+<-]<[>+<-]<[>+<-]>>>>>]<-]<-]<-]<-]

Agora, ele passou da noite para o dia e tem mais de 3.000.000.000 de etapas. Ainda não conseguiu uma única iteração do loop externo. Mal conseguiu passar por 15% do segundo loop.

captncraig
fonte
2

Este programa funciona em número infinito de células. Dois valores são inicializados no início com valores ASCII 255. O primeiro valor na primeira rotação do loop principal é dividido em 255 células e eles são inicializados com 255 cada, na segunda rotação do loop principal o valor em 255 células é dividido novamente até 255 * 255 células, da mesma maneira para a rotação 255 do loop principal, o total de células inicializadas será 255 ^ 255. O segundo valor determina quanto tempo o loop principal deve ser repetido.

>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]
Albert
fonte
2

Este programa é quase o mesmo que o meu programa anterior, a diferença é que o valor que determina o loop externo permanece fixo em uma célula específica, para que o número de células inicializadas e o total de etapas no final do programa possam ser aumentados

->>-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]

células inicializadas no final do programa 255 ^ 255

-[>-[>->>[-]-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<-]<-]

células inicializadas no final do programa 255 ^ 255 ^ 3

Eu o modifiquei ainda mais para executar ainda mais número de etapas.

->>>->>-<<<<<[>>>[>]<[[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<[>>>[[<+>-]>]<<[<]]<]>>>>[[<<+>>-]>]<-<<[<]<<-]

inicializa 255 ^ 255 células durante a primeira rotação do principal 255 ^ (255 ^ 255 * 255) células durante a segunda rotação do loop principal 255 ^ {255 ^ (255 ^ 255 * 255) * 255} células durante a terceira rotação do loop principal em desta forma, o loop se repete 255 vezes

Albert
fonte
Parece ótimo! Desculpe por ainda não aceitar uma resposta - preciso dedicar algum tempo para analisá-las e descobrir a ordem de crescimento. Quando você diz "255 ^ 255 * 255", você quer dizer "255 ^ (255 * 255)"? (Eu esperaria "255 ^ 256" de outra forma.)
Anton Golov