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 como255. - 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.
code-challenge
brainfuck
busy-beaver
Anton Golov
fonte
fonte
floatoudoubleprimitiva usada para a computação cotidiana em geral. (Nesse ponto, o computador é na maior parte apenas manipulando cordas de que representam a equação)Respostas:
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 é
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.
fonte
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.
fonte
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.
fonte
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
fonte