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!

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

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.

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.

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.

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

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

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

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.

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.

Perl -a → Má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.

Geléia → Sistema 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}, { a→ bc, b→ a, c→ aaa} 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

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.

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.

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.

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.

M → Dica , 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=\sqrt{-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?

$x$$x$

ḅ$x\oplus(x\otimes y)$$x\otimes y$${\oplus}$. 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?

$(x\odot y)\oplus(x\otimes y)$¹×ịß¹¹Ṅ é 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.

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

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.

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]

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

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

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.

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.

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

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

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)

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