Intérprete de idioma completo Turing

42

Um desafio que achei muito legal é criar um intérprete para um idioma completo de Turing de sua escolha.

As regras são simples:

  1. Você pode usar qualquer idioma para criar esse intérprete, mesmo que seja mais novo que esse desafio.
  2. Você pode usar qualquer idioma completo do Turing, desde que não seja o mesmo que você está escrevendo.
  3. Você não pode simplesmente avaliar o código, por exemplo, usar funções eval.
  4. Uma explicação de como você abordou isso será agradável, mas não necessária.
  5. Isso será pontuado em bytes.
  6. Cada envio deve estar totalmente funcionando, o que significa que todos os recursos que o seu idioma escolhido deve estar presente.

Para ser simples:

Sua tarefa é criar um intérprete funcional para qualquer idioma completo de Turing com qualquer idioma de sua escolha.

Boa sorte!

arodebaugh
fonte
3
Eu recomendaria também uma regra de que o idioma implementado deve ser diferente do idioma usado para implementá-lo, para evitar evalsoluções triviais .
ETHproductions
1
Na verdade, você pode querer apenas banir evalcomandos / funções, pois alguns idiomas têm recursos internos para avaliar o código em outro idioma.
ETHproductions
2
@arodebaugh Para desafios futuros, você pode postar sua ideia na sandbox, onde poderá obter feedback e resolver detalhes como esse antes que os desafios sejam lançados e sejam respondidos.
Martin Ender
1
OK, você provavelmente deve ser um pouco mais específico e dizer algo como "Você não pode simplesmente executar código, através de qualquer método" para evitar outras respostas triviais como a do Bash + perl.
ETHproductions
1
Vídeo relevante: Sobre a plenitude de Turing do PowerPoint (SIGBOVIK)
sergiol 7/17/17

Respostas:

16

Brachylog (2) → Problema de pós-correspondência , 9 bytes

~h=∋ᵐ\cᵐ=

Experimente online!

Entrada é uma lista de listas de strings. (No problema Pós-correspondência, conforme definido na Wikipedia, as listas internas têm dois elementos cada, embora este programa possa realmente lidar com uma generalização para qualquer número de elementos.) Este programa força as soluções para o problema, em ordem de comprimento, até uma solução é encontrada. Sabe-se que o problema de pós-correspondência é capaz de simular uma máquina de Turing e, portanto, soluções de força bruta para ela são completas. Se executado como uma função, e não como um programa, na verdade também produz resultados significativos.

O programa no link TIO acima é o [["a","baa"],["ab","aa"],["bba","bb"]]que copiei da Wikipedia. A solução (que o programa encontrar rapidamente) é ["bbaabbbaa","bbaabbbaa"].

Explicação

Isso é basicamente uma tradução direta do problema de correspondência do Post para o Brachylog.

~h=∋ᵐ\cᵐ=
~h         Find {the shortest possible} list which starts with {the input}
  =        and for which all elements are equal
   ∋ᵐ      such that taking an element of each element,
     \cᵐ   and concatenating elements in corresponding positions,
        =  produces a list all of whose elements are equal.

Basicamente, criamos uma lista com cópias repetidas da entrada (o mínimo possível, o que significa que não perdemos nenhuma possibilidade ao forçar brutalmente), pegamos um elemento de cada cópia e concatenamos os elementos correspondentes (como na correspondência de postagem problema).


fonte
1
E o usual "resumo de coisas que são significativas e salvariam bytes, mas o intérprete Brachylog não pode lidar com isso": os primeiros cinco bytes podem ser expressos como ~dp(o que não significa exatamente a mesma coisa, mas está próximo o suficiente para ser Turing-complete), exceto que o intérprete Brachylog ainda não sabe como reverter d.
12

Geléia → "Adicionar mínimo para transpor", 5 4 bytes

+"Ṃẞ

Experimente online! (executa apenas uma iteração, para evitar tempos limite)

Uma construção muito simples de Turing: tomamos uma matriz quadrada como programa e fazemos um loop para sempre, identificando a linha lexicograficamente menor e, em seguida, aumentando cada elemento da primeira linha pelo primeiro elemento da menor lexicograficamente, cada elemento da segunda linha pelo segundo elemento do menor lexicograficamente, e assim por diante. (O programa Jelly é " +"adicione elementos correspondentes {da entrada e} o mínimo {do original}, loop"; este é um byte mais curto que o meu programa anterior Z+ṂZß, que fez exatamente a mesma coisa. Claramente eu deveria ter me concentrado em jogar golfe no Jelly, não apenas jogando a linguagem implementada.)

O idioma resultante é Turing-completo pelo mesmo motivo que o Kangaroo. O primeiro elemento de cada linha atua como uma contagem de ignorados (embora, em vez de a contagem de ignorados de cada comando seja reduzida quando ignorada, aumentamos a contagem de ignorados de cada comando quando executado, e procuramos o comando com a menor contagem de ignorados do que comandos com contagem de pulos zero; isso acontece da mesma maneira). Garantimos que esse primeiro elemento seja mais alto que os outros elementos (que representam o número de vezes que cada comando aparece no multiset de cada comando), garantindo assim que a primeira linha nunca seja o mínimo; o restante da primeira linha pode ser lixo. O único problema restante é modelar a maneira como os comandos com contagem de pulsos iguais são executados ciclicamente em sequência, mas podemos fazer isso multiplicando todas as contagens de pulados por uma constante grande e adicionando pequenas "iniciais" pular conta para a primeira coluna para servir como desempate. Isso nos dá um desempate das "primeiras execuções de comandos não pulados", não "dos comandos não pulados são executados ciclicamente em sequência", mas a construção de Turing-completeness para o Kangaroo não se importa com essa diferença.


fonte
10

Mathematica interpretando o jogo da vida de Conway, 64 bytes

CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&

O Jogo da Vida de Conway é conhecido por ser Turing completo; e autômatos celulares são a verdadeira obsessão de Stephen Wolfram. CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}é uma regra que transforma uma matriz bidimensional de 0s e 1s de acordo com uma etapa do Jogo da vida de Conway. (Eu acho que o comportamento padrão é que essa matriz envolva suas bordas, então é realmente um toro discreto.) ~Nest~##&Transforma essa regra em uma função que, quando recebe um estado inicial da placa (de qualquer dimensão) e um número inteiro ncomo argumentos, gera o resultado de niterações da regra do Jogo da Vida.

Para sua diversão, você pode usar a versão embrulhada

b = RandomInteger[1,{50,50}];
Manipulate[ArrayPlot[
  CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&
    [b, n] ]
, {{n,0}, 0, 100, 1}]

e percorra 100 gerações em uma placa de 50x50.

Greg Martin
fonte
Se estou entendendo corretamente, isso tem um tamanho fixo de placa? Nesse caso, acho que não pode ser completo para Turing, pode?
DLosc
Qualquer chamada específica para a função tem um tamanho fixo de quadro, mas esse tamanho pode ser arbitrariamente grande. (Note-se que a segunda metade do post descreve um exemplo de observar o código em ação, não o código real em si.)
Greg Martin
O que estou dizendo é que, para que o GoL seja Turing-Complete, ele deve ser capaz de um padrão que cresça infinitamente. (Como uma pistola de asa delta.) Se essa implementação não puder aumentar a matriz de uma etapa para outra, mas envolvê-la toroidalmente, será reprovada no teste de crescimento infinito.
DLosc 17/05
Essa é uma perspectiva razoável, com certeza. Mas implementações de linguagens de programação em computadores físicos nem sequer satisfazem esse teste! Alguém poderia se contentar com uma sequência (hipotética) de computadores físicos com mais e mais memória, cada um capaz de calcular mais um valor dessa função computável; nesse ponto, no entanto, deve-se estar igualmente satisfeito com uma sequência (hipotética) de entradas para esse programa GoL.
Greg Martin
9

Turtled interpretação CT , 49 bytes

Talvez eu consiga jogar golfe

Além disso, isso não gera nada útil. apenas pára se, e somente se, o programa CT dado parar.

este é um que eu fiz há um tempo, na verdade (então joguei golfe agora)

!-l[*+.r_]' !l[ l]r[ u.(;d' u)d(1[ r].[ l])( r)+]

Como funciona:

Turtlèd usa células da grade. Quando digo "escreva algo na grade", quero dizer que um grupo contíguo de caracteres é colocado na grade. exemplo

[ ][ ][ ][ ][ ][ ][ ]
[ ][H][E][L][L][O][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]

para o programa

os dados são inseridos primeiro:

!-l[*+.r_]' 

este é essencialmente um programa para gatos. grava a entrada na grade.

então os comandos são inseridos:

!

o que faz com estes comandos:

esses comandos são "produções". se o bit de dados mais à esquerda for 1, ele copia a produção no final da cadeia de dados. caso contrário, nada acontece. o bit de dados mais à esquerda é removido e usa a próxima produção com o próximo bit de dados mais à esquerda. o programa pára quando não há bits na cadeia de dados. Uma maneira de fazer essas produções é lidar com os bits e o final das produções separadamente. é isso que nosso programa faz. ele copia separadamente os bits da cadeia de comando até o final da cadeia de dados e exclui os bits da cadeia de dados

sobre como este programa faz isso. depois de inserir os comandos, o ponteiro da tartaruga / grade retorna ao bit mais à esquerda da sequência de dados. depois entra em loop

[ u.(;d' u)d(1[ r].[ l])( r)+]

o que ele faz nesse loop, é movido para cima a partir da sequência de dados mais à esquerda e anota o caractere de comando atual (u.). se for;, no final de uma produção, ele se move para baixo e exclui o bit de dados mais à esquerda abaixo dele e volta para cima ( (;d' u)). então, de qualquer maneira, ele desce um ( d). se o bit não foi excluído, significa que deve verificar se é necessário copiar um pouco dos comandos no final. portanto, se esse caractere que é ou foi o banco de dados mais à esquerda for 1, ele será movido para o final da extremidade direita da sequência de dados, copiará o bit da sequência de comandos e voltará para o espaço à esquerda dos dados mais à esquerda bit ( (1[ r].[ l])). agora, ele está no banco de dados mais à esquerda, que era zero, ou à esquerda do banco de dados mais à esquerda. então, movemos para a direita se estiver em um espaço (( r)) então, o ponteiro do comando é incrementado, para que anotemos o próximo comando na próxima iteração do loop. Se não houver mais datatring, isso significa que estaremos em um espaço e o loop terminará. caso contrário, executaremos novamente o loop.

Limão destrutível
fonte
Tente jogar mais isso!
Arodebaugh 28/02
9

Perl → Variante do programador de três estrelas , 26 + 1 = 27 bytes

++$a[$a[$a[$_]]]for@F;redo

Experimente online! (Este link contém um cabeçalho que sai do programa após um número definido de iterações (para que o TIO não atinja o tempo limite) e para imprimir o estado interno a cada iteração (para que ele faça algo observável).)

Execute com -a(penalidade de 1 byte, como você pode ajustá-lo antes da -M5.010produção -aM5.010).

Especificamente, isso implementa o Programador Três Estrelas no qual os comandos são separados por espaços e nenhum comentário é permitido no arquivo, sem extensões de E / S. (Essas alterações não fazem diferença para a conclusão de Turing do idioma, obviamente.) Não há uma prova de conclusão de Turing para programador de três estrelas on-line, mas é de conclusão de Turing (estive compartilhando uma prova de esboço de seu Turing -completude com outros esoprogramas, mas parei de trabalhar na linguagem quando descobri que era realmente fácil programar uma vez que você superava o choque original).

O programa realmente não precisa de muita explicação; Programador de três estrelas tem uma especificação muito simples, e esta é uma tradução direta dele. Os únicos pontos sutis: @Fé a entrada para o programa em forma de matriz (isso é uma conseqüência de -a); e redorepetirá o programa inteiro, pois está em um loop implícito (também uma conseqüência de -a).


fonte
1
Eu acho que faz mais sentido para a seta significar "é reduzido a" do que "interpreta".
Quinta-
9

assembly x86 (sintaxe da Intel / MASM) -Brainfuck 2127 bytes.

Ainda capaz de golfe

.386
.model flat,stdcall
.stack 4096
include \masm32\include\masm32.inc
includelib \masm32\lib\masm32.lib
ExitProcess proto,dwExitCode:dword
.data
bfsrc BYTE 200 dup(0) 
bfcells BYTE 100 dup(0) 
loopStack DD 5 dup(0) 
charBuf BYTE 5 dup(0) 
newline BYTE 10,0 
prompt BYTE "$",0 
hr BYTE 50 dup('-'),0 
space BYTE ' ',0
.code
EvalBf proc
    start:
    invoke StdOut, addr prompt
    invoke StdIn, addr bfsrc,200
    cmp bfsrc,0
    je exit
    mov eax,0 
    mov ebx,0 
    mov ecx,0 
    processInstruction:
    cmp BYTE PTR bfsrc[ebx], '+'
    je plus
    cmp BYTE PTR bfsrc[ebx], '-'
    je minus
    cmp BYTE PTR bfsrc[ebx], '>'
    je fwd
    cmp BYTE PTR bfsrc[ebx], '<'
    je back
    cmp BYTE PTR bfsrc[ebx], '['
    je open
    cmp BYTE PTR bfsrc[ebx], ']'
    je close
    cmp BYTE PTR bfsrc[ebx], '.'
    je dot
    jmp processNextInstruction
    plus:
    inc BYTE PTR bfcells[eax]
    jmp processNextInstruction
    minus:
    dec BYTE PTR bfcells[eax]
    jmp processNextInstruction
    fwd:
    inc eax
    jmp processNextInstruction
    back:
    dec eax
    jmp processNextInstruction
    open:
    mov loopStack[ecx*4],ebx
    inc ecx
    jmp processNextInstruction
    close:
    dec ecx
    cmp BYTE PTR bfcells[eax], 0
    je processNextInstruction
    mov ebx,loopStack[ecx*4]
    inc ecx
    jmp processNextInstruction
    dot:
    mov dl, BYTE PTR bfcells[eax]
    mov BYTE PTR charBuf[0], dl
    mov BYTE PTR charBuf[1],0anything
    push eax
    push ecx
    invoke StdOut, addr charBuf
    pop ecx
    pop eax
    jmp processNextInstruction
    processNextInstruction:
    inc ebx
    cmp BYTE PTR bfsrc[ebx], 0
    je done
    jmp processInstruction
    done:
    invoke StdOut, addr newline
    mov eax, 0
    printNext:
    cmp eax, 100
    jge reset
    push eax
    invoke dwtoa, BYTE PTR bfcells[eax], addr charBuf
    invoke StdOut, addr charBuf
    invoke StdOut, addr space
    pop eax
    inc eax
    jmp printNext
    reset:
    invoke StdOut, addr newline
    invoke StdOut, addr hr
    invoke StdOut, addr newline
    jmp start

    exit:
    invoke ExitProcess,0
EvalBf endp
end EvalBf
Christopher
fonte
3
Normalmente, as respostas da montagem são contadas no tamanho do código da máquina resultante, para que você não precise jogar golfe na montagem, apenas minimize o número / tamanho das instruções.
Robert Fraser
@RobertFraser uhh Não sei como contar isso: P
Christopher
3
Na verdade, no começo eu de alguma forma ler o título como "x86 asm implementado em Brainfuck" e foi um bocado impressionado :)
quetzalcoatl
@Quetzalcoatl Isso seria impressionante
Christopher
1
pls golf nomes variável / etiqueta ty
ASCII-only
8

Pip interpretando sistemas de tags cíclicos , 16 bytes

YqWyyPBg@++vXPOy

Toma as produções do sistema de tags como argumentos da linha de comandos e a sequência de dados inicial de stdin.

O código acima é meio difícil de verificar porque não produz nenhuma saída (então o único comportamento observável é "termina" vs. "não termina"). Portanto, aqui está uma versão desmontada que gera a sequência de dados após cada etapa e também termina após 20 etapas, para que o TIO não precise lidar com toneladas de saída de loops infinitos: Experimente on-line!

Sistemas de etiquetas cíclicas

Os sistemas de tags cíclicos são um modelo computacional extremamente simples, porém completo, de Turing . Eles consistem em uma lista de produções que definem operações em uma sequência de dados . As produções e a sequência de dados consistem em 1 e 0.

A cada etapa, o caractere mais à esquerda da sequência de dados é removido.

  • Se o caractere for 1, a produção atual será anexada ao lado direito da sequência de dados.
  • Se o caractere for 0, nada será acrescentado.

Em ambos os casos, a produção atual passa para a próxima produção da lista, ciclicamente: se estivéssemos na última produção, passamos para a primeira. A execução continua até que a sequência de dados esteja vazia.

Explicação

                  g is list of cmdline args; v is -1 (implicit)
 q                Read a line of stdin for the data string
Y                 and yank it into the y variable
  Wy              While data string is nonempty:
       g@++v       Retrieve the next production from g (using cyclic indexing)
             POy   Pop the first character of y
            X      String-multiply: result is the production if the first character of y
                   was 1, or empty string if it was 0
    yPB            Push that string to the back end of y
DLosc
fonte
Ei, acabei de lembrar que você não precisa inserir a sequência de dados; pode ser apenas 1fonte: esolangs links para este arxiv.org/abs/1312.6700 . Vou editar a minha resposta em breve, e se isso ajuda a sua resposta você deve (TBH sua entrada parece suficiente golfy na verdade)
Destrutível Lemon
8

Funções de Collatz Generalizadas Iteradas -> Python 2, 46 bytes

a,b,x,m=input()
while-~x%m:x=x/m*a[x%m]+b[x%m]

Chame essa função com uma lista de m-1 a's eb's, o valor inicial x e o divisor m, que coletivamente constituem um "programa" para IGCF. Em vez de usar uma terceira matriz para indicar em quais módulos parar, isso simplesmente pára sempre que o módulo é m-1. Essa simplificação significa que pode ser necessário um esforço extra para converter um determinado programa Fractran nessa variante, mas economiza alguns bytes no intérprete.

Experimente online! Este TIO demonstra como adicionar 5 + 5 com esse idioma. O programa a = [3], b = [0], m = 2 adiciona e, começando com 7776 = 2 ^ 5 * 3 ^ 5, eventualmente produz 59049 = 3 ^ 10.

quintopia
fonte
Dang bom trabalho. Eu estava esperando para ganhar a recompensa, mas bom trabalho
Christopher
7

Variante ResPlicate -> Python 2, 47 bytes

l=input()
while l:l=l[2+l[0]:]+l[2:2+l[0]]*l[1]

Esta função interpreta uma variante do ResPlicate

  • para o qual um programa é uma lista python de tamanho uniforme com elementos pares em índices pares.
  • sem E / S.
  • para o qual tentar copiar mais valores do que o restante da fila simplesmente copia o restante da fila (ou seja, o bit copiado não é preenchido com zeros no comprimento necessário).

A última alteração significa que alguns programas ResPlicate (que atendem à primeira condição) não se comportarão da mesma forma nesta variante, mas, felizmente, os intérpretes do BCT não exigem a funcionalidade removida e, portanto, o idioma permanece TC.

Experimente online! Esse TIO possui uma impressão inserida para mostrar que funciona e um cabeçalho que mata o programa após 1 segundo e um exemplo que consegue gerar mais saída do que o TIO pode suportar naquele segundo.

quintopia
fonte
2
Por que não l=input()? Seria um byte mais curto.
Feersum 8/17/17
7

Perl -aMáquina I / D , 24 bytes

$p=$a[$p]+=$_ for@F;redo

Experimente online! (contém um cabeçalho que imprime o estado interno e pára após 10 iterações, para que o comportamento seja observável)

Sobre o idioma

Passei os últimos dias trabalhando na máquina de I / D , uma das minhas idéias mais recentes para linguagens de programação muito simples. Funciona da seguinte forma: o armazenamento de dados consiste em uma RAM ilimitada, inicialmente todos os zeros. Cada elemento pode armazenar um número inteiro ilimitado (embora, na prática, a maioria dos programas de máquina de E / D armazene apenas números inteiros pequenos na maioria deles, e utiliza os números inteiros não limitados apenas como forma de endereçar células com endereços grandes). Há também um ponteiro de dados, que aponta para uma célula (ou seja, mantém o endereço como uma célula); inicialmente também é zero.

Existem apenas dois comandos:

  • I: Incremente a célula para a qual o ponteiro de dados aponta. (O ponteiro de dados em si permanece inalterado.)
  • D: Desreferencia o ponteiro dos dados, isto é, leia o valor da célula para a qual o ponteiro de dados aponta. Em seguida, armazene o valor resultante que você lê novamente no ponteiro de dados.

A execução simplesmente executa o programa em um loop repetidamente, para sempre.

É bastante surpreendente que um idioma tão simples seja o Turing completo, por isso tenho trabalhado para provar isso. Aqui está a prova . É bem parecido com (mas mais simples que) a prova para o Programador Três Estrelas, uma linguagem muito semelhante (e, de fato, este envio usa o mesmo "shell" básico do OISC em torno do programa, diferindo apenas nas instruções reais implementadas).

Sobre o programa

Uso

A entrada deve ser fornecida na entrada padrão e é um programa de máquina de E / D sem comentários e usando a sintaxe RLE / OISC. (A máquina de E / D possui duas sintaxes equivalentes e diferentes, mas, para fins de golfe, este programa suporta apenas uma delas.) Nessa sintaxe, um programa é uma sequência de números em decimal, representando o comprimento das execuções de Icomandos entre os Dcomandos. (Você pode especificar dois ou mais Dcomandos consecutivos colocando uma "execução de 0 Icomandos" entre eles, para que a sintaxe seja totalmente geral.)

Explicação

Como pode ser visto no programa, isso não está implementando os comandos Ie Dindividualmente. De fato, é um intérprete de otimização (levemente) (puramente porque é mais curto para escrever dessa maneira). A chave é ver que uma execução de n comandos de incremento incrementa o destino do ponteiro de dados n vezes, ou seja, adiciona n a ele; e uma execução de comandos de incremento 0 também pode ser implementada dessa maneira, pois adicionar 0 à memória não tem efeito. Portanto, a operação que realmente implementamos é alternar entre implementar um run-of- Is e a D. Ou, em outras palavras, "adicione nao valor apontado pelo ponteiro de dados (armazenando-o novamente no valor apontado pelo ponteiro de dados), depois leia o valor apontado pelo ponteiro de dados e armazene-o no ponteiro de dados ". Isso é claramente mais detalhado do que precisa para ser, e podemos simplificar ainda mais isso para "adicionar n ao valor apontado pelo ponteiro de dados e armazenar esse valor no destino do ponteiro de dados e no próprio ponteiro de dados".

Então isso faz parte do núcleo do nosso programa. Estamos usando uma matriz $apara armazenar a RAM e $pcomo ponteiro de dados (indexação na matriz):

$p=$a[$p]+=$_
         + $_  add {the run length}
   $a[$p]      to the element of $a pointed to by $p
   $a[$p] =    storing the result back into that element
$p=            and also in the pointer itself

Convenientemente, o Perl interpreta os elementos não inicializados da matriz como 0 quando são tratados como números; portanto, a matriz será inicializada lentamente em zeros para nós, sem nenhum código explícito para isso. (Um problema em potencial é a precisão numérica quando os números aumentam; no entanto, isso só acontecerá se a quantidade da matriz usada exceder o espaço de endereço da máquina (números inteiros Perl são grandes o suficiente para conter ponteiros), algo que não pode acontecer em uma máquina idealizada.)

Finalmente, tudo o que precisamos fazer é colocar esse programa em alguns loops. O for@Floop, combinado com a -aopção de linha de comando, passará pelos campos da entrada padrão (a definição padrão de "campo" aqui será dividida em espaço em branco). O redoloop colocará o programa inteiro em um loop implícito (que não seja, convenientemente, a leitura da entrada padrão), o que fará com que o programa execute um loop repetidamente, conforme exigido pela semântica da máquina de I / D.

ais523
fonte
Bem vindo de volta! Não precisamos mais marcar sinalizadores para intérpretes, observe que este é 'Perl com -a'. codegolf.meta.stackexchange.com/a/14339/9365
Dom Hastings
6

GeléiaSistema com 2 etiquetas , 8 bytes

µḢị⁴⁸;Ḋß

Experimente online!

Eu tenho uma recompensa em favor de linguagens práticas, mas pensei que eu poderia tentar vencer a tarefa original enquanto estava nela (pois não posso exatamente ganhar minha própria recompensa).

Implementa uma variante de sistemas de tags sem estado de parada, pois não é necessário para a integridade de Turing. Os estados são numerados de 1, consecutivamente, e a sequência inicial vem antes do programa.

Por exemplo, Wikipedia dá um exemplo de um sistema de tag { a, b, c}, { abc, ba, caaa} com corda inicial aaa; neste formato de entrada, que é [1,1,1], [[2,3],[1],[1,1,1]]. (Os sistemas de tags não possuem uma sintaxe fixa, e isso parece ser uma maneira razoável de fazer isso.)

O link do TIO foi adicionado ("escreva o estado interno e uma nova linha para o stdout") para mostrar que o programa está realmente funcionando.

Explicação

µḢị⁴⁸;Ḋß
           {implicit: initialise internal state from first argument}
µ          Disregard the second command-line argument by default
 Ḣ         Take the first element, removing it from the internal state
  ị⁴       Use the value to index into the second argument
    ⁸;     Prepend (the rest of) the internal state
      Ḋ    Discard the first element of the internal state
       ß   Loop forever

fonte
6

BF / P "implementado em uma máquina de Turing, 842 bytes

Tabela de transição (vinculada por causa do comprimento)

Tabela de transição, versão menos golfe

Simulador de máquina de Turing que usei

Isso certamente não vai ganhar nenhum prêmio por tamanho, mas é algo que eu sempre quis fazer, já que o BF é tão semelhante a uma Máquina de Turing. Cada célula armazena um valor de 0x0- 0xF. No entanto, a largura está longe do site da Turing Machine, sem travar o navegador. As funções ,e .(entrada e saída) não estão definidas, por isso é um pouco mais parecido com P "do que com BF verdadeiro.

Para executá-lo, cole a tabela de transição no simulador da Turing Machine, defina a entrada para algum código BF e pressione executar.

A fita da TM armazena o código BF e os dados BF, com um único espaço no meio. Ele monitora sua posição no código, modificando o caractere que está executando no momento ( [-> (, etc) e sua posição nos dados com um ^na frente da célula. Depois de ler um caractere de comando, ele se move até atingir o cursor, move uma célula para a direita e executa a função apropriada. Em seguida, ele retorna, procurando um dos caracteres de comando "modificado" no código BF e passa para o próximo, repetindo todo o processo. Depois de ficar sem código, ele pára.

A melhor maneira de entender como funciona é executando a versão não-gasta, colocando-a no modo de etapa e observando quais linhas levam a quais outras e o que cada estado / bloco de linhas faz.

As versões de golfe e não de golfe são exatamente iguais em termos de como funcionam, mas a versão não de golfe tem nomes mais amigáveis ​​ao ser humano e é dividida em seções.

a52
fonte
1
O limite de pós comprimento é mais do que suficiente para caber tabela de transição
ASCII-only
6

C implementando a (2,3) Turing Machine , 236 205 bytes ( 46 31 a menos se você não se importa com entradas estranhas)

Agradecimentos ao Appleshell por -11 bytes, VisualMelon por -12 bytes e Johan du Toit por -7 bytes.

O CeilingCat criou uma versão que usa apenas 144 bytes, veja aqui .

(Adicionei algumas quebras de linha aqui para que você não precise rolar, mas normalmente a maioria delas seria excluída)

#define c char
j;i;k;c s,d[256];c main(){c*p=d+128;gets(d);
for(;k<256&&d[k];)d[k++]-=48;for(;++j<256;)
{c t=*p;*p=-t*t+(2-s)*t+1+s;p+=(s^t==0)*2-1;s=s?t%2:!t%3;
for(i=0;++i<256;)printf("%d",d[i]);puts("");}}

Experimente online!

Para usar: Insira uma sequência de até 256 unidades, zeros e dois para inicializar a fita. Quaisquer valores não inicializados serão zero. (Valores diferentes de 0, 1 e 2 podem causar comportamento indefinido.) O programa iterará mais de 256 etapas. O número de etapas que ele repete pode ser aumentado modificando o código, mas obviamente isso requer mais caracteres.

É uma entrada bastante longa, mas esta é a primeira vez que faço uma delas e não usei um idioma dedicado ao golfe. Eu me diverti muito, mesmo que fosse mais do que eu esperava.

Muitos bytes são do processamento de entrada e saída, e eu perdi um total de 42 bytes ao aceitar 0, 1 e 2 em vez de NUL, SOH, STX. (Para mudar isso, exclua k;da frente e for(;k<256&&d[k];)d[k++]-=48;da segunda linha.)

A tabela de transição, especialmente a linha *p=-t*t+(2-s)*t+1+s;(que define os valores na fita) provavelmente também poderia ser compactada.

a52
fonte
1
Uau, e este é o seu primeiro código de golfe aqui! Maravilhoso!
Zacharý
Você pode encurtar as declarações de variáveis globais como este: k,j;c s,d[256];( intestá implícito em C, então você também pode mover ia declaração global para salvar 3 bytes mais)
Appleshell
Obrigado Apple, eu vou fazer isso.
a52
Você pode mover a verificação do terminal nulo da string dentro do loop for. Inclinar k++e remover o {}salva mais alguns bytes: for(;k<256&d[k];)d[k++]-=-48;como jé apenas um cronometrista (o valor nunca é usado), você pode substituí-lo (e i) kcontando ao contrário: você sabe k==256após o primeiro ciclo, então conte até zero no segundo for(;k>0;), que sai k==-1, então o último loop pode se tornar for(;++k<256;). (Aviso: eu costumo jogar golfe C#, mas isso pareceu compilar).
VisualMelon 7/17
1
@VisualMelon Eu determinei o problema. Eu precisava usar k<256&&d[k], não &, porque d[k]estava sendo avaliado em k==256. Além disso, como knão havia mais garantia de ser 256posterior a esse loop, tive que redefini-lo posteriormente para garantir 256 etapas. (Se você (ou seja, VisualMelon) tem alguma outra sugestão, nós provavelmente deve colocá-los em bate-papo para que não fique muito muitos comentários)
a52
5

Röda implementando o Fractran , 114 112 106 bytes

1 byte economizado graças a @fergusq, reorganizando os parâmetros

f&n,a{x=1{x=0;(a/" ")()|[_/`/`]|[parseInteger(_[0],_1[1])]|{|q,w|{n*=q/w;x=1}if[n%w<1,x<1]}_,_}while[x>0]}

Experimente online!

Chame a função assim: f reference_to_input program. A saída será armazenada no local do input.

Kritixi Lithos
fonte
O ponto e vírgula depois e[1]é redundante. Além disso, você pode salvar um byte alterando ordem parâmetro: f&n,a.
Fergusq #
@fergusq Agradecimentos para o f&n,atruque, e eu estava prestes a remover o ponto e vírgula quando você comentou :)
Kritixi Lithos
5

Clojure, 82 81 bytes (Máquina de Turing)

Atualização: removeu um espaço de t{} s.

#(loop[p 0 t{}s 1](if-let[[S M N](%[(or(t p)0)s])](recur(+ p M)(assoc t p S)N)t))

Implementa a máquina de Turing como um loop, retorna a fita quando o estado de parada é atingido. Nas regras de transição de estado, isso é indicado omitindo o estado de transição. A settins Npara nile a subsequente if-letabortará como a transição de estado correspondente não é encontrada a partir da entrada de hash-mapa %. Na verdade, qualquer valor para esse estado funcionará, como :abort0 ou -1.

Sem jogar com um exemplo de castor ocupado de 3 estados e 2 símbolos da Wikipedia .

(def f #(loop[pos 0 tape {} state 1]
          (if-let [[sym move next-state](%[(get tape pos 0)state])]
            (do (println [pos tape state])
                (recur(+ pos move)(assoc tape pos sym)next-state))
            tape)))

(f {[0 1] [1  1 2]
    [0 2] [1 -1 1]
    [0 3] [1 -1 2] 
    [1 1] [1 -1 3]
    [1 2] [1  1 2]
    [1 3] [1  1]})

{0 1, 1 1, -1 1, -2 1, -3 1, 2 1}

Experimente online .

Em um único núcleo de 6700K, ele executa o castor de dois estados com 5 símbolos (47,1 milhões de etapas) em cerca de 29 segundos ou 1,6 milhão de etapas / segundo.

NikoNyrh
fonte
5

MDica , 4 bytes

Ṅ×ịß

Experimente online!

O link TIO adiciona um rodapé para chamar a função com o exemplo do programa Tip mostrado na página Esolang (o "invólucro automático" de M para chamar funções como se fossem programas que não possam lidar com números racionais ou de ponto fixo, ou pelo menos eu não descobri como contar, então preciso transformar a função em um programa completo manualmente para poder executá-lo.)

Na verdade, isso imprime saída de depuração útil; o programa não pode ser escrito em 3 bytes em M porque um programa que consiste em exatamente três díades aciona um caso especial no analisador, então tive que adicionar um comando extra para evitar o caso especial. Torná-lo (imprimir com nova linha), pelo menos, proporciona uma finalidade útil.

ıi=1

Não implementa E / S (exceto halt / no-halt). AE / S é uma extensão do Tip (não faz parte do próprio idioma) e não é necessária para a conclusão de Turing.

Explicação / Antecedentes

Ṅ×ịß
Ṅ     Print {the left argument} and a newline; also resolves a parser ambiguity
  ị   {The left argument}th element of {the right argument}, wrapping on OoB
 ×    Multiply {the left argument} by {the chosen element}
   ß  Recursive call; arguments: {the product} and {the same right argument}

[1,2,3][1,2,3,1,2,3,1,2,3,…]rx+s, que é um polinômio, e a "conversão de base" incorporada por muitas línguas de golfe é, na verdade, um avaliador polinomial de uso geral disfarçado. Então, tudo o que precisamos fazer é indexar em uma lista de listas de dígitos, convertê-los com base e pronto, certo?

xx

x(xy)xy. Claro, poderíamos substituir o comportamento do encadeamento para praticamente qualquer coisa que desejássemos, mas isso custaria um byte inteiro, e as entradas do idioma do golfe para essa pergunta estão ficando tão curtas que um byte é muito.

Então olhei para trás e reavaliei um pouco. Existem operações que poderíamos usar em vez da avaliação polinomial? Idealmente, aqueles que são comutativos, para que não tenhamos que nos preocupar com a ordem dos argumentos? Logo depois, percebi que as funções Collatz são mais complexas do que precisam.

s

E, é claro, diferentemente da conversão base ( ), a multiplicação ( ×) é comutativa e, portanto, não importa em que ordem os argumentos são colocados. Portanto, tudo o que precisamos escrever é ×ịe, em seguida, colocar o programa em uma recursão infinita com ß, e temos uma linguagem completa de Turing. Direita?

(xy)(xy)¹×ịß¹¹ é uma boa opção porque produz saída de depuração útil.

Três bytes são possíveis? A menos que eu esteja perdendo alguma coisa, não com esta escolha específica de linguagem de implementação e implementação, mas neste momento certamente parece que seria possível de alguma forma, pois existem muitas maneiras de fazê-lo em quatro e tantos Turing-complete idiomas que você pode implementar.

ais523
fonte
Depois de pensar um pouco mais sobre isso, podemos reduzir isso para três bytes usando e em vez de ×e ; o idioma resultante não é exatamente o mesmo que Tip, mas é bastante semelhante e quase certamente completo por Turing pelo mesmo motivo. Infelizmente, não está implementado em M, e não consigo encontrar nenhuma maneira de fazer o Jelly fazer cálculos de precisão arbitrária quando uma das entradas é um número real não inteiro. Porém, se alguém conhece algum outro idioma de golfe onde essa construção possa funcionar, fique à vontade para tentar.
Ais523
4

C interpretando Brainfuck, 187 bytes

t[999],*p=t,c,i,l;f(char*t){for(i=0;c=t[i];i++){c^62?c^60?c^43?c^45?c^46?c^44?c^91:(*p=getchar()):putchar(*p):--*p:++*p:--p:++p;if(c==93&&*p)for(l=1;l>0;)c=t[--i],c==91?l--:c==93?l++:0;}}

Experimente online

Johan du Toit
fonte
3
Welp, provavelmente haveria uma resposta usando BF.
Zacharý
4

Lua interpretando Brainf ***, 467 bytes

b,r,a,i,n,s=0,io.read,{0},1,1,"><+-.,[]"c,f=r(),{function()n=n+1;a[n]=a[n]or 0;end,function()n=n-1;a[n]=a[n]or 0;end,function()a[n]=a[n]+1;end,function()a[n]=a[n]-1;end,function()io.write(string.char(a[n]))end,function()a[n]=io.read():byte()end,function()i=a[n]~=0 and i or c:find("]",i)end,function()if a[n]~=0 then b,x=1,""repeat i=i-1 x=c:sub(i,i)b=x=="["and b-1 or x=="]"and b+1 or b until b==0 and x=="["end end}repeat f[s:find(c:sub(i,i),1,1)]()i=i+1 until i>#c

Eu sei que ainda há algum emagrecimento que posso fazer mais tarde, mas é aqui que o meu primeiro passe terminou. Toma o código brainf da entrada padrão.

Blab
fonte
2
+1 para o brains, sempre é divertido quando os jogadores atribuem a uma lista de variáveis.
Zacharý
4

CJam → Variante ResPlicate, 15 14 13 bytes

-1 byte graças a @ ais523

l~{(/((*+e_}h

A variante é igual à desta resposta , exceto que o número de itens retirados da fila é um a menos que o número superior na fila.

A l~{ ... }hpeça apenas pega uma matriz como entrada e se repete até que ela esteja vazia.

Explicação para o loop principal:

    e# Stack:             | [3 2 1 1 2 2 2 1]
(   e# Pop first element: | [2 1 1 2 2 2 1] 3
/   e# Split chunks:      | [[2 1 1] [2 2 2] [1]]
(   e# Pop first:         | [[2 2 2] [1]] [2 1 1]
(   e# Pop first:         | [[2 2 2] [1]] [1 1] 2
*   e# Repeat array:      | [[2 2 2] [1]] [1 1 1 1]
+   e# Concatenate:       | [[2 2 2] [1] 1 1 1 1]
e_  e# Flatten:           | [2 2 2 1 1 1 1 1]
Esolanging Fruit
fonte
Você realmente não precisa do incremento aqui. Basta especificar que os comprimentos dos blocos devem ser incrementados em 1 no programa original; isso não prejudica a integridade de Turing do ResPlicate (existem construções de TC nas quais comprimentos de blocos e contagens de repetição nunca são misturados).
3

Chip , 20 + 3 = 23 bytes (Regra 110)

AZZ
>}/a
`)\'E~Zte*f

+3 para bandeira -z

Experimente online!

Esse envio não é perfeito, pois o Chip ainda não possui capacidade de loop, portanto a saída deve ser transmitida como entrada para simular várias gerações, com algo assim (é claro, você pode executar esse loop indefinidamente, e Chip pode lidar com entradas arbitrariamente longas, portanto, essa combinação é Turing Complete).

Essa implementação recebe entrada e saída na forma de ASCII 0s e 1s. A lógica aqui é a seguinte:

p := value of left neighbor cell    AZZ
q := value of current cell          AZ
r := value of right neighbor cell   A

q' := ((r xor q) and p) or          >}/a
      ((r or q) and ~p)             `)\'

O restante dos elementos é para limpeza: e*fcausa a saída numérica ASCII e E~Ztfinaliza a execução dois bytes após o esgotamento da entrada (já que a largura aumenta 2 por geração).

Phlarx
fonte
3

Clojure, 75 bytes (sistema de etiquetas cíclicas)

Atualização 1: substituída some?por nil?.

Atualização 2: corrigida uma falta Sno ramo de if s.

#(loop[[p & P](cycle %)[s & S]%2](if(nil? s)S(recur P(if s(concat S p)S))))

Implementa o sistema de tag cíclico , retorna nilse o programa for interrompido e repetir para sempre. Clojure realmente brilha aqui com infinitas sequências preguiçosas (como ciclo ) e desestruturação . Uns e zeros são indicados como valores verdadeiros e falsos. Quando a sequência de dados acabar, storna - se nil.

Ungolfed:

(def f #(loop[[p & P] (cycle %) [s & S] %2 i 5]
          (do
            (pprint [p (concat [s] S)])
            (if (and (some? s) (pos? i))
              (recur P (if s (concat S p) S) (dec i))))))

Resultados de exemplo:

(f [[false]] [true true])
[[false] (true true)]
[[false] (true false)]
[[false] (false false)]
[[false] (false)]
[[false] (nil)]

(f [[false true true] [true false] [true false true]] [true])
[[false true true] (true)]
[[true false]      (false true true)]
[[true false true] (true true)]
[[false true true] (true true false true)]
[[true false]      (true false true false true true)]
[[true false true] (false true false true true true false)]
NikoNyrh
fonte
2

Regra de interpretação do JavaScript 110 , 131 bytes (99 bytes? 28 bytes?)

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}
c=(l,n)=>!n?l:c(b(0+l+0),n-1)

Como você pode ver, o código define 3 funções, a, be c. Talvez seja possível salvar bytes combinando-os na função 1 (não vejo como), mas é bom que se separem porque cada um deles já cumpre esse desafio em algum sentido.

A função arecebe 3 números como entrada e calcula um polinômio estranho deles. Quando esses três números são 0ou 1podem ser vistos como células da Regra 110. A paridade da saída de apode então ser vista como o valor da célula do meio na próxima geração. Portanto, de certa forma, essa função simples já é um 'intérprete' da Regra 110 (28 bytes):

a=(p,q,r)=>(q+r+q*r+p*q*r)%2

Podemos então criar uma nova função bque avalie atodos os caracteres de uma sequência de uns e zeros. Este bé, então, de uma maneira melhor do que a, um intérprete Regra 110. Tomando o mod 2 após a avaliação de um salvamento entre colchetes (99 bytes):

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}

Para realmente calcular uma função com a Regra 110, o usuário deve especificar o estado inicial e o número de gerações após as quais a saída será 'exibida'. Podemos criar uma terceira função cque utiliza uma sequência de uns e zeros, e um número inteiro positivo n, que avalia ba sequência de ntempos. Assim, podemos realmente ver a Regra 110 como uma linguagem de programação, onde um programa é um estado inicial e um número n, e a saída é o estado após ngerações. A função cagora é um intérprete real para essa linguagem de programação, portanto o código final para esse desafio é o que apresentei acima.

Jens Renders
fonte
Isso calcula 110 com o fundo apropriado? Uma resposta anterior foi excluída porque não tinha o plano de fundo.
Wheat Wizard
@WheatWizard o fundo é parte da entrada, a sua resposta não deveria ter Nbeen suprimido para que
Jens Renders
O fundo deve ser infinito, você pode receber informações infinitas?
Assistente de trigo
@WheatWizard ele não tem que ser infinito, tem que ser capaz de se tornar arbitrariamente grande, e pode
Jens Renders
1
A regra 110 não é Turing completa se você decidir antecipadamente a geração e precisar de informações infinitas na construção que conheço. Mesmo que alguém tenha encontrado uma construção com um estado inicial finito, não é possível saber a memória ou o tempo necessário antes da execução do programa, pois assim você pode resolver o Problema da Parada.
Ørjan Johansen
2

JS -> Nova linha 854 bytes

(function(d){var b=0;var n=!0;var c=[];var h=[];var e=0;var l=[];var m=0;var f=2;var a=0;var g=!1;var k=function(a){if(a===1)return!1;if(a%2===0&&a!==2)return!1;if(a%3===0&&a!==3)return!1;if(a%5===0&&a!==5)return!1;if(a%7===0&&a!==7)return!1;for(var b=7;b<d.round(d.sqrt(a))+1;b++)if(a%b===0)return!1;return f=a,!0;};var j=0;var i=0;var o=function(q){var o=d.__split(q,'\n');d.println(o);for(var n=0;n<o.length;n++)if(n>=f^2&&n<=f+1^2&&k(n)){f=n;for(var p=0;p<o[n].length;p++){if(o[n]==='+'&&(a+=c[b],b++),o[n]==='-')if(g===!0&&a<=0)break;else a-=c[b],b++;if(o[n]==='*'&&(a*=c[b],b++),o[n]==='/'&&(a/=c[b],b++),o[n]==='s'&&(a=d.sqrt(a)),o[n]==='%'&&(a%=c[b],b++),o[n]==='a'&&l.push(a),o[n]==='g'&&(a=c[b],b++),o[n]==='q'&&c.push(a),o[n]==='i'&&a++,o[n]==='d')if(g===!0&&a<=0)break;else a--;o[n]==='r'&&(g=!0),o[n]==='w'&&(g=!1),o[n]==='['&&(j=n),o[n]===']'&&a>0&&(n=j,h[e]--),o[n]==='{'&&(i=n),o[n]==='}'&&h[e]>0&&(n=i,h[e]--),m=a,o[n]==='k'&&e++;}}};});

Super golfed graças ao google.

Christopher
fonte
Acho que você postou esta resposta para o desafio errado. Você queria publicá-lo neste desafio ?
1
Nesse caso, você precisa modificar a implementação para apontar para as diferentes condições de vitória; isso é código-golfe , não popularidade-concurso . Por exemplo, você tem muitos nomes de variáveis ​​que podem ser claramente mais curtos, o que significa que esta solução não é um candidato sério. Talvez você possa excluí-lo por enquanto e depois excluí-lo quando tiver tempo para jogar golfe.
1
No entanto, respostas que não fazem uma tentativa séria de otimizar a condição de vitória são contrárias às regras . Esse é um motivo suficientemente bom para excluí-lo até que você possa se adequar às regras.
1
Você pode combinar todas as varinstruções:var b=0,n=!0,c=[],h=[],e=0,l=[],m=0,f=2,a=0,g=!1;
Esolanging Fruit
1
Pls remove all varty
somente ASCII
1

Clojure, 87 bytes (Regra 110)

O crédito pelo código de paridade vai para Jens Renders! Eu estava realmente lutando para expressar isso e eu ia converter o [p q r]binário em um número inteiro e usar uma tabela de pesquisa.

#(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%)

Aqui, partitiona desestruturação de Clojure torna a aplicação lógica bastante simples. Essa função retorna uma sequência infinita de estados, de modo que o responsável pela chamada é responsável takepor quantos forem necessários ou apenas nthpara pular para um estado específico. Se o preenchimento com zero fosse dois elementos em vez de apenas um, a fita aumentaria constantemente, evitando problemas de contorno. Agora permanece a largura original.

Exemplo:

(def f #(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%))

(pprint (take 5 (f '(0 0 0 0 0 1 1 1 0 0 1 0 0))))
((0 0 0 0 0 1 1 1 0 0 1 0 0)
 (0 0 0 0 1 1 0 1 0 1 1 0 0)
 (0 0 0 1 1 1 1 1 1 1 1 0 0)
 (0 0 1 1 0 0 0 0 0 0 1 0 0)
 (0 1 1 1 0 0 0 0 0 1 1 0 0))
NikoNyrh
fonte
1
Se você trabalhar apenas com a largura original, não será possível concluir o Turing, porque ele possui apenas memória finita. (De fato, todas as construções conhecidas de completude de Turing da Regra 110 exigem o "preenchimento" usado para expandir a largura à medida que o programa passa a ter um padrão especificado na entrada do usuário e diferente à esquerda e à direita, em vez de apenas zeros.)
Entendo, isso dificulta sua simulação. Do Clojure cycleseria capaz de construir o padrão de preenchimento infinito, mas executar o primeiro passo seria tomar uma quantidade infinita de tempo: /
NikoNyrh
Pensando bem, não seria muito complicado considerar esses padrões de preenchimento como argumentos adicionais e expandir a fita simulada em 1 bloco à esquerda e à direita. A velocidade das informações aqui é de 1 bloco / iteração, portanto, apenas precisamos simular o "cone de luz" ao redor do bloco central que possui a estrutura assimétrica. (CMIIW)
NikoNyrh
1

APL (Dyalog) → Variante Fractran , 15 bytes

(⊃0~⍨××0=1|×)⍣≡

Experimente online!

A função recebe os racionais como uma lista de números em vez de duas listas contendo o numerador e o denominador e gera o resultado se o programa terminar. Isso implementa uma variante do Fractran que possui o 1/1 racional (= 1) no final do programa. O 1 não tem efeito sobre a completude de Turing (tanto quanto eu entendo) porque a entrada para o programa só atinge a 1 quando nenhuma das outras racionalidades funciona e, quando funciona, a entrada não é alterada. Isso é usado apenas para que a função saiba quando terminar.

O link TIO executa a função por 2 iterações (para que você possa ver a saída porque o programa não termina) na primeira entrada e executa a segunda entrada até a conclusão, após o que retorna a saída.

(⊃0~⍨××0=1|×)⍣≡ toma a lista de argumentos como o argumento da esquerda, a ser referido como ⊣, e a entrada como o argumento da direita, a ser referido como referred

(⊃0~⍨××0=1|×) trem de função

  • 1|×obter a parte após o ponto decimal (módulo 1) do produto ×de ⊣ e ⊢

  • 0= é igual a 0?

  • ×× multiplique esse resultado por ⊣ × ⊢, sempre que o racional × ⊢ não for um número inteiro, ele será substituído por 0

  • 0~⍨ remova todos os 0s

  • pegue o primeiro elemento

até a entrada não mudar, observe que o resultado de (⊃0~⍨××0=1|×)é reutilizado como entrada; portanto, se ele parar de mudar (como resultado de 1 no final), o programa para

Kritixi Lithos
fonte
1

JavaScript: Cálculo Lambda ( 123 114)

Representado usando indicadores Debruijn em duplos.

V=function b(c,d){if(!isNaN(c)){for(;--c;)d=d[1];return d[0]}return 0==c[0]?e=>b(c[1],[e,d]):b(c[0],d)(b(c[1],d))}

O combinador S é [0, [0, [0, [[3, 1], [2, 1]]]]]

K é [0, [0, 2]]

Eu sou [0, 1]

Editar: raspou 9 bytes substituindo "number"==typeof cpor!isNaN(c)

SYZYGY-DEV 333
fonte
0

APL (Dyalog Unicode) , SBCS de 15 bytes

Programa completo que implementa um executor de autômato celular unidimensional generalizado. Isso inclui a Regra 110, que é Turing completa. Solicita ao stdin o estado inicial, o número de iterações (ou para continuar até estável ou {⍵≡⎕←⍺}para exibir todos os valores intermediários até estável) e o conjunto de regras.

⎕∊⍨∘(⊢∘⊂⌺3)⍣⎕⊢⎕

Experimente online! (4 iterações da Regra 110)

 solicitar o estado inicial e

 rendimento que (separa o estado do número de iterações)

⍣⎕ solicite o número de iterações e aplique a seguinte função várias vezes:

() Aplique a seguinte função tácita:

  ⌺3 obtenha todos os bairros de comprimento 3 (com informações sobre se estão no limite) e aplique a seguinte função tácita a cada par:

    coloque o bairro

    e

    rendimento que (descartando as informações sobre estar na borda)

 então

∊⍨ verifique se são membros de

 solicitar a lista de bairros que levam a estar na próxima iteração

Adão
fonte