Resumo:

Para qualquer idioma, qual é a menor quantidade de caracteres únicos para o seu idioma como Turing-Complete ?

Desafio:

Para qualquer idioma de sua escolha, encontre o menor subconjunto de caracteres que permita que seu idioma seja Turing-Complete. Você pode reutilizar seu conjunto de caracteres quantas vezes quiser.

Exemplos:

• JavaScript: +!()[]( http://www.jsfuck.com )

• Brainfuck: +<>[](assume um tamanho de célula de embalagem)

• Python 2: ()+1cehrx(feito de scripts como exec(chr(1+1+1)+chr(1)))

Pontuação:

Esse desafio é pontuado em caracteres , não em bytes . Por exemplo, as pontuações dos exemplos são 6, 5 e 9.

Notas:

• Esse desafio se diferencia dos outros no sentido de que você apenas seu idioma é Turing-Complete (não sendo necessariamente capaz de usar todos os recursos do idioma).

• Embora você possa, não poste respostas sem reduzir os caracteres usados. Exemplo: Brainfuck com 8 caracteres (já que todos os outros caracteres são um comentário por padrão).

• Você DEVE fornecer pelo menos uma breve explicação sobre por que seu subconjunto é Turing-Complete.

Haskell, 4 caracteres

()=;

Com ()=somos capazes de definir S, K e I. As definições devem ser separadas por um ;ou um NL.

Definimos (==)como S (a segunda linha mostra uma versão mais legível):

((=====)==(======))(=======)=(=====)(=======)((======)(=======))
( a     == b      ) c       = a      c       ( b       c       )

(===) como K:

(=====)===(======)=(=====)
 a     === b      = a

e (====)como eu:

(====)(=====)=(=====)
(====) a     = a 

Felizmente (==), (===), (====), etc, são nomes função / parâmetro válidos.

Como @ ais523 aponta, o SKI não é suficiente em uma linguagem fortemente tipada como Haskell, então precisamos adicionar um combinador de ponto de fixação (=====) :

(=====)(======)=(======)((=====)(======))
(=====) f      = f      ((=====) f      )

JavaScript (ES6), 5 caracteres

Agradecemos a @ETHproductions e @ATaco por ajudarem nisso; esse foi um projeto de grupo e, embora a idéia original fosse minha, muitos dos detalhes são deles. Veja a discussão no chat em que este subconjunto JavaScript foi desenvolvido aqui .

[]+=`

Está bem estabelecido que qualquer programa Javascript pode ser escrito com os caracteres ( []()+!), mas cinco caracteres não são suficientes . No entanto, este não é um desafio sobre a criação de JavaScript arbitrário. É um desafio escrever uma linguagem completa de Turing e, usando o fato de que as linguagens completas de Turing não precisam de acesso ao DOM ou mesmo E / S interativa, acontece que podemos escrever um programa com todas as funcionalidades necessárias , mesmo sem capacidade de executar um evalou equivalente.

Bootstrapping básico

JavaScript é muito flexível com tipos. Por exemplo, []é uma matriz vazia, mas +[]é 0 e []+[]é a cadeia nula. Notavelmente, o fato de podermos produzir 0 com esse conjunto de caracteres torna possível simular o efeito dos parênteses no agrupamento; (a)pode ser escrito como [a][+[]]. Podemos usar esse tipo de truque para produzir vários caracteres usando apenas +[]:

• [][+[]]é undefined(sendo o primeiro elemento de uma matriz vazia); tão
• []+[][+[]]é "undefined"(a estrificação de undefined); tão
• [[]+[][+[]]]é ["undefined"](agrupando isso em uma matriz); tão
• [[]+[][+[]]][+[]]é "undefined"(seu primeiro elemento); tão
• [[]+[][+[]]][+[]][+[]]é "u"(sua primeira letra).

ué um dos personagens mais fáceis de criar, mas técnicas semelhantes nos permitem criar vários outros personagens. O mesmo link de antes nos fornece a seguinte lista de caracteres acessíveis +[](esta é a mesma lista que para +[](), exceto ,porque é a única construção que usa parênteses para uma finalidade diferente de agrupamento / precedência):

0123456789acdefinotuvyIN (){}.

Não podemos soletrar muitas palavras úteis desse conjunto de caracteres (lembre-se de que este é o conjunto de caracteres que podemos produzir como seqüências de caracteres ; não conseguimos executá-las sem algum tipo de eval). Como tal, precisamos de outro personagem. Usaremos =, porque será útil mais tarde, mas, por enquanto, usaremos para soletrar o operador de comparação ==. Isso nos permite produzir falsee true, que pode ser modificado e indexado, e imediatamente adicionamos lrsaos caracteres que podemos incluir nas strings.

De longe, a palavra mais importante que isso nos permite escrever, que não podíamos antes, é constructor. Agora, o JavaScript possui uma sintaxe de acesso à propriedade semelhante a:

object.property

mas você também pode escrever assim:

object["property"]

e nada nos impede de usar uma propriedade calculada, em vez de uma string literal. Podemos, assim, fazer algo ao longo das linhas de

object["c"+"o"+"n"+"s"+"t"+"r"+"u"+"c"+"t"+"o"+"r"]

(com as letras geradas conforme descrito acima; o código rapidamente fica muito longo!); isso é equivalente aobject.constructor , o que nos permite acessar os construtores de objetos arbitrários.

Existem vários truques que podemos fazer com isso. Do mundano ao fantástico:

• O construtor de um objeto é uma função. Notavelmente, ele tem um nome e esse nome faz parte da stringification da função. Assim, por exemplo, podemos fazer [[]+[]][+[]]["constructor"]para chegar ao construtor de uma string, cujo nome é String, e depois especificá-lo para chegar à capitalS caractere . Isso amplia um pouco nosso alfabeto, e vamos precisar de alguns dos novos personagens mais tarde.

• Todas as matrizes têm o mesmo construtor; []["constructor"] == []["constructor"]é true(ao contrário [] == [], o que é falso). Isso pode parecer pequeno, mas é muito importante, porque nos fornece um método para armazenar valores persistentemente; podemos definir uma propriedade aleatória no construtor e lê-la novamente mais tarde. (Esse é um dos motivos pelos quais estamos usando, =em vez de uma das outras maneiras de gerar truee false.) Por exemplo, podemos avaliar [[]["constructor"]["a"]=[]]e, posteriormente, ler[]["constructor"]["a"] e recuperar a mesma matriz que armazenamos lá.

  Isso atende a um dos requisitos necessários para a integridade de Turing , a capacidade de armazenar e recuperar quantidades arbitrárias de dados. Podemos criar uma célula contras usando uma matriz de dois elementos, obtendo valores de nosso armazenamento de propriedades do construtor e armazenando-a no lugar de um desses valores, permitindo construir estruturas de dados arbitrariamente grandes na memória; e podemos acessá-lo nesse armazenamento, fazendo o inverso, derrubando-o pedaço por pedaço até que os dados que desejamos se tornem acessíveis. A leitura é destrutiva, mas isso é aceitável porque temos mais de um local para armazenar dados, para que possamos copiá-los enquanto lemos e depois colocar a cópia de volta no local original.

• Ele nos permite chegar ao construtor de uma função (há muitas funções que podemos acessar com nosso alfabeto limitado; []["find"]ou seja, Array.find, é a mais facilmente acessível, mas há outras). Por que isso é útil? Bem, podemos realmente usá-lo para o propósito pretendido de um construtor, e construir funções! Infelizmente, com nosso conjunto de caracteres, não podemos passar ao construtor Function uma string computada. No entanto, o uso de `deixa passar uma string literal (por exemplo []["find"]["constructor"]`function body goes here`); isso significa que podemos definir valores personalizados do tipo de função com qualquer comportamento quando executados, desde que possamos expressar esse comportamento usando inteiramente []+=. Por exemplo, []["find"]["constructor"]`[]+[]`é uma função bastante chata que calcula a cadeia nula, a descarta e sai; esteA função não é útil, mas as mais complexas serão. Observe que, embora as funções não possam aceitar parâmetros ou retornar valores, na prática, esses não são problemas, pois podemos usar o armazenamento de propriedades do construtor para se comunicar de uma função para outra. Outra restrição é que não podemos usar` no corpo de uma função.

  Agora, podemos definir funções personalizadas, mas o que nos impede neste momento é a dificuldade que temos em chamá- las. No nível superior do programa, podemos chamar uma função com`` , mas poder chamar funções apenas a partir do nível superior não nos permite fazer nenhum tipo de loop. Antes, precisamos de funções para podermos ligar um para o outro.

  Conseguimos isso com um truque bastante bacana. Lembra do capital Sque geramos anteriormente? Isso nos permite soletrar "toString". Nós não vamos chamá-lo; podemos converter coisas em strings adicionando []a elas. Em vez disso, vamos substituí- lo. Podemos usar o armazenamento do construtor para definir matrizes persistentes que permanecem por aí. Podemos então atribuir nossas funções criadas aos toStringmétodos das matrizes , e essas atribuições também permanecerão. Agora, tudo o que precisamos fazer é simples +[]na matriz e, de repente, nossa função definida personalizada será executada. Isso significa que podemos usar os caracteres+=[]chamar funções e, portanto, nossas funções podem se chamar - ou a si mesmas. Isso nos dá recursão, o que nos dá laços e, de repente, temos tudo o que precisamos para completar a Turing.

Aqui está um resumo de um conjunto de recursos que fornecem a integridade de Turing e como eles são implementados:

• Armazenamento não vinculado : matrizes aninhadas no armazenamento do construtor
• Fluxo de controle : implementado usando ife recursão:
  • if: converte um booleano em um número e indexa em uma matriz de 2 elementos; um elemento executa a função para o thencaso, quando codificado, o outro elemento executa a função para o elsecaso, quando codificado
  • Recursão : especifique um elemento apropriado do armazenamento do construtor
• Sequenciamento de comandos : [a]+[b]+[c]avalia a, be da cesquerda para a direita (pelo menos no navegador que verifiquei)

Infelizmente, isso é bastante impraticável; não apenas é imensamente grande, dado que as cadeias precisam ser construídas caractere por caractere a partir dos primeiros princípios, também não tem como executar E / S (o que não é necessário para ser completo em Turing). No entanto, se terminar, é pelo menos possível procurar manualmente no armazenamento do construtor posteriormente, para que não seja impossível depurar seus programas e eles não sejam completamente não comunicativos.

Unário , 1 caractere

0

A escolha do personagem realmente não importa; o tamanho do programa define o programa que ele transpila. Enquanto a especificação exige 0caracteres, a maioria dos transpilers parece não verificar isso.

vim, 9 8 7 6 caracteres

<C-v><esc>1@ad

Podemos construir e executar um programa vimscript arbitrário da seguinte maneira:

1. Use a sequência aa<C-v><C-v>1<esc>dd@1<esc>ddddpara obter um <C-a>registro 1.

2. Entre no modo de inserção com a, depois insira um a, que será usado para reinserir o modo de inserção em uma macro posteriormente.

3. Para cada caractere no programa vimscript desejado,

   1. use <C-v><C-v>1<esc>para inserir a sequência literal <C-v>1,

   2. use @1(que é<C-a><cr> , na qual a final <cr>não está em operação por estar na última linha) quantas vezes for necessário para incrementar 1até que o valor ASCII do caractere desejado seja alcançado,

   3. e entre novamente no modo de inserção com a .

4. Exclua a linha (junto com uma nova linha à direita) na 1 registro com <esc>dd.

5. Execute o resultado como pressionamentos de tecla vim usando @1 , e <esc>ddpara excluir a linha inserida pela nova linha à direita da etapa anterior.

6. Execute a sequência arbitrária de bytes resultante com dd@1 . Se começar com a :, será interpretado como código vimscript e será executado devido à nova linha à direita de dd.

Não estou convencido de que esse seja um conjunto mínimo de caracteres, mas é muito fácil provar que é completo em Turing.

Perl, 5 caracteres

<>^es

Como em outras linguagens de script, a idéia é eval usar seqüências arbitrárias. No entanto, nosso conjunto de caracteres não inclui aspas ou operadores de concatenação, portanto, construir seqüências arbitrárias será muito mais complexo. Observe que eval^"seria muito mais simples de lidar, mas tem mais um personagem.

Nossa principal ferramenta é s<^><CODE>ee, que avaliaCODE e avalia sua saída. Mais epode ser adicionado, com o efeito esperado.

Nós obtemos strings usando <>, que é o operador glob, exceto quando não é. O primeiro caractere não pode ser< (se não parecer com o <<operador), os colchetes angulares precisam ser balanceados e deve haver pelo menos um caractere que não seja da letra (caso contrário, será interpretado como o operador de linha de leitura).

Ao armazenar essas strings juntas, podemos obter qualquer combinação de caracteres de ^B^V^S(*-/9;<>HJMOY[`\^begqstv , desde que aceitemos ter algum lixo por perto (os três primeiros são caracteres de controle).

Por exemplo, suponha que queremos obter "v99". Uma maneira de obter v99é "><<" ^ "e>>" ^ "see" ^ "^^^", mas não podemos representar essas strings devido às restrições <>. Então, em vez disso, usamos:

<^<<^>><>>^<^^^^^<>>^<^^^^^^e>^<^^^^^^^>^<^^^^^e>^<^^^^e^>^<e^^es>^<^ee^^>^<^<^^^^^>>^<^<>^^^^>^<^^^^^^^e>^<^^^^^^^^>

Os rendimentos acima Y9;v99;, que, quando avaliados, produzem o mesmo resultado que umv99 (a saber, o caractere com código ASCII 99).

Assim, podemos usar todo o conjunto de ^B^V^S(*-/9;<>HJMOY[`\^begqstvcaracteres para gerar nossa string arbitrária, convertê-la como acima e colá-la em ums<><CODE>eeee para executá-lo. Infelizmente, esse conjunto de caracteres ainda é muito limitado, sem nenhuma maneira óbvia de executar concatenação.

Mas, felizmente, ele contém a estrela. Isso nos permite escrever *b, que avalia a string "*main::b". Então, *b^<^B[MMH^V^SY>(^ B, ^ V e ^ S são caracteres de controle literais) nos fornece o (6, $&);que, quando avaliado novamente, retorna o valor da variável de correspondência do Perl $&,. Isso nos permite usar uma forma limitada de concatenação: podemos acrescentar coisas repetidamente ao $_uso s<^><THINGS>ee, em seguida, usá-lo s<\H*><*b^<^B[MMH^V^SY>>eeepara avaliar $_(\H corresponde a qualquer coisa, exceto espaço em branco horizontal; usamos em vez do ponto, que não está em nosso conjunto de caracteres).

Usando 9-/, podemos facilmente gerar todos os dígitos. Usando dígitos ve concatenação, podemos gerar caracteres arbitrários (vXXX gera o caractere com o código ASCII XXX). E podemos concatená-las, para gerar seqüências arbitrárias. Então parece que podemos fazer qualquer coisa.

Vamos escrever um exemplo completo. Suponha que desejemos um programa que imprima seu próprio PID. Começamos com o programa natural:

say$$

Nós o convertemos em notação v:

s<><v115.v97.v121.v36.v36>ee

Reescrevemos isso usando apenas ^B^V^S(*-/9;<>HJMOY[`\^begqstv(espaço em branco é apenas para legibilidade e não afeta a saída):

s<^><
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-99/-9-99/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-9/9-9/9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><999/9-9/-9-9/-9-9/-9-9/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<\H*><*b^<^B[MMH^V^SY>>eee;
>eee;

Por fim, convertemos o programa acima para apenas <>^es: pastebin . Infelizmente, isso trava o Perl Excessively long <> operator, mas isso é apenas uma limitação técnica e não deve ser levada em consideração.

Ufa, essa foi bastante a jornada. Seria realmente interessante ver alguém criar um conjunto de 5 caracteres que simplifica as coisas.

EDIT: usando uma abordagem ligeiramente diferente, podemos evitar atingir o limite de comprimento <>. Intérprete cerebral totalmente funcional usando apenas <>^es: Experimente on-line! . Perl automatizado para <>^estranspiler: pastebin .

Python 2, 7 caracteres

exc="%\n

Qualquer programa Python 2 pode ser codificado usando esses 7 caracteres ( \né nova linha).

Construindo seqüências arbitrárias

Podemos executar a concatenação aplicando repetidamente o operador de substituição %em uma única string. Por exemplo, se a=1, b=2, c=3, "%d%%d%%%%d" % a % b % cnos fornecerá a string "123". Felizmente, as letras nos execdão acesso %xe %csão basicamente hex()e chr(). Com %c, podemos construir qualquer cadeia, desde que tenhamos os números necessários que representam os caracteres. Podemos então executar essa string como código python usando a execpalavra - chave

Faça números

Podemos acessar 0e começar 1logo com comparações ( ==). Através de uma combinação de dígitos e módulos concatenadores, é possível construir o número 43que representa +em ASCII. Isso nos permite construir os números que precisamos para o nosso código.

Juntar as peças

Omiti vários detalhes nesta explicação, pois eles não são essenciais para entender como os programas sob essas restrições podem ser escritos. Abaixo está um programa Python 2 que escrevi que converte qualquer programa python em uma versão funcionalmente equivalente que usa apenas esses 7 caracteres. As técnicas utilizadas são inspiradas nesta submissão no golfe da anarquia por k. Alguns truques simples também são usados ​​para manter o tamanho dos programas gerados dentro de limites razoáveis.

import sys

var = {
    43: 'e',
    'prog': 'x', # the program will be stored in this variable
    'template': 'c',
    0: 'ee',
    1: 'ex',
    2: 'ec',
    4: 'xe',
    8: 'xx',
    16: 'xc',
    32: 'ce',
    64: 'cc',
    'data': 'cx', # source program will be encoded here
}

unpacker = 'exec"".join(chr(eval(c))for c in {}.split())'.format(var['data'])

source = sys.stdin.read()
charset = sorted(list(set(source+unpacker)))
codepoints = map(ord, charset)

output = (
    # create template for joining multiple characters
    '{}="%c%%c%%%%c%%%%%%%%c"\n'.format(var['template']) +

    # create 1
    '{0}={1}=={1}\n'.format(var[1], var['template']) +

    # create 0
    '{}={}==""\n'.format(var[0], var['template']) +

    # create 3
    # store it at var[43] temporarily
    (
        'exec"{0}=%x%%x"%{2}%{2}\n' +
        'exec"{0}%%%%%%%%=%x%%x%%%%x"%{1}%{2}%{1}\n'
    ).format(var[43], var[0], var[1]) +

    # create 4
    # this step overwrites the value stored at var[0]
    (
        'exec"{1}=%x%%x"%{0}%{1}\n' +
        'exec"{1}%%%%=%x%%x"%{2}%{0}\n'
    ).format(var[43], var[0], var[1]) +

    # create 43
    'exec"{0}=%x%%x"%{1}%{0}\n'.format(var[43], var[0])
)

# create powers of 2
for i in [2, 4, 8, 16, 32, 64]:
    output += 'exec"{0}={1}%c{1}"%{2}\n'.format(var[i], var[i/2], var[43])

for i, c in enumerate(codepoints):
    # skip if already aliased
    if c in var:
        continue

    # generate a new name for this variable
    var_name = ''
    if i < 27:
        for _ in range(3):
            var_name += 'exc'[i%3]
            i /= 3
    else:
        i -= 27
        for _ in range(4):
            var_name += 'exc'[i%3]
            i /= 3
    var[c] = var_name

    # decompose code point into powers of two
    rem = c
    pows = []
    while rem:
        pows.append(rem&-rem)
        rem -= rem&-rem

    # define this variable
    front = 'exec"{}={}'.format(var[c], var[pows.pop()])
    back = '"'
    for i, p in enumerate(pows):
        front += '%'*(2**i) + 'c' + var[p]
        back += '%' + var[43]
    output += front + back + '\n'

# initialise the unpacker
output += 'exec"""{}=""\n"""\n'.format(var['prog'])
i = 0
length = len(unpacker)
while i < length:
    if (length-i) % 4 == 0:
        # concat 4 characters at a time
        w, x, y, z = [var[ord(unpacker[i+j])] for j in range(4)]
        output += 'exec"{}%c={}%%{}%%{}%%{}%%{}"%{}\n'.format(var['prog'], 
                    var['template'], w, x, y, z, var[43])
        i += 4
    else:
        output += 'exec"""{}%c="%%c"%%{}"""%{}\n'.format(var['prog'],
                    var[ord(unpacker[i])], var[43])
        i += 1

# encode source data
output += var['data'] + '="""'
output += '\n'.join(var[ord(c)] for c in source)
output += '"""\n'

# execute the program
output += 'exec"exec%c{}"%{}'.format(var['prog'], var[32])

print output

Experimente online

Mathematica, 5 4 caracteres

I[]

é um caractere Unicode de uso privado , que atua como um operador, Functionpermitindo escrever literais para funções sem nome com argumentos nomeados. O personagem se parece muito com o ↦Mathematica, então vou usá-lo no restante desta resposta para maior clareza.

Usando estes, podemos implementar o S, Ke Icombinadores de lógica combinatória:

I -> II↦II
K -> II↦III↦II
S -> II↦III↦IIII↦II[IIII][III[IIII]]

Um problema sintático com isso é que ↦tem uma precedência muito baixa, o que será um problema se tentarmos passar argumentos para esses combinadores. Você normalmente conserta isso colocando um combinador Centre parênteses (C), mas não temos parênteses. No entanto, podemos usar Ie []agrupar Coutras mágicas com precedência suficientemente alta para que possamos usá-las mais tarde:

I[C][[I[[]]I]]

Finalmente, escrever um aplicativo A x y z(onde Aé um combinator "parenthesised" como mostrado acima, e x, y, zpode ou não ser parenthesised, ou podem ser expressões maiores), podemos escrever:

A[x][y][z]

Isso deixa a questão de como o equivalente entre parênteses realmente funciona. Vou tentar explicá-lo aproximadamente na ordem em que o criei.

Portanto, o que temos sintaticamente para agrupar algo são os colchetes []. Os colchetes aparecem de duas maneiras no Mathematica. Como invocações de funções f[x]ou como um operador de indexação f[[i]](o que é realmente apenas uma abreviação de Part[f, i]). Em particular, isso significa que [C]nem [[C]]é nem sintaxe válida. Precisamos de algo na frente dele. Em teoria, isso pode ser qualquer coisa. Se usarmos o Ique já temos, podemos obter, I[C]por exemplo. Isso permanece sem avaliação, porque Inão é uma função unária (não é uma função).

Mas agora precisamos de uma maneira de extrair Cnovamente, porque, caso contrário, não será realmente avaliado quando tentarmos passar um argumento xpara ele.

É aqui que é útil que f[[i]]pode ser usado para expressões arbitrárias f, não apenas para listas. Assumindo que fele próprio é da forma head[val1,...,valn], então f[[0]]dá head, f[[1]]dá val1, f[[-1]]dá valne assim por diante. Então, precisamos pegar um 1ou -1extrair o Cnovo, porque avalia I[C][[1]]ou I[C][[-1]]avalia C.

Nós pode obter 1a partir de um símbolo arbitrário indefinido como x, mas para isso, precisaríamos de outro personagem para a divisão ( x/xdá 1para indefinido x). A multiplicação é a única operação aritmética que podemos executar sem nenhum caractere adicional (em princípio); portanto, precisamos de algum valor que possa ser multiplicado para dar -1ou 1. Isso acaba sendo o motivo pelo qual eu escolhi especificamente Ipara nossos identificadores. Porque Ipor si só é o símbolo embutido do Mathematica para a unidade imaginária.

Mas isso deixa um problema final: como podemos realmente multiplicar Ipor si só? Não podemos simplesmente escrever IIporque isso é analisado como um único símbolo. Precisamos separar esses tokens sem a) alterar seu valor eb) usando novos caracteres.

O bit final de uma mágica é uma peça de comportamento não documentado: f[[]](ou equivalente Part[f]) é uma sintaxe válida e retorna em fsi. Então, em vez de multiplicar Ipor I, multiplicamos I[[]]por I. A inserção dos colchetes faz com que o Mathematica procure um novo token posteriormente e faça a I[[]]Iavaliação -1conforme necessário. E é assim que terminamos I[C][[I[[]]I]].

Observe que não poderíamos ter uso I[]. Esta é uma invocação sem argumentos da função I, mas como eu disse antes Inão é uma função, portanto isso permanecerá sem avaliação.

Python 2, 8 caracteres

exc'%~-0

Esses caracteres permitem a tradução / execução de qualquer programa Python usando strings de formato e exec. Embora ser capaz de traduzir qualquer programa não seja necessário para a integralidade de Turing, esse é o menor número de caracteres que conheço que o tornam TC de qualquer maneira. Que é tão poderoso é apenas um bônus.

Também podem ser usadas aspas duplas, além de qualquer dígito além de zero. (Agora que penso nisso, 1com certeza gostaria de ser melhor, resultando em programas mais curtos, desde que você poderia usar 1, 11e 111, também.)

Aqui está o programa print:

exec'%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c'%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

Experimente online

O programa base requer

exec''

Cada caractere xadicionado ao programa requer (contagem de caracteres):

• % - 2**(n-1)
• c - 1
• - - ord(x)*2
• ~ - ord(x)*2
• 0 - 1

A exceção é que certas otimizações / atalhos podem ser usados %'0'para tornar o programa codificado mais curto, como o uso do caractere0 vez de 48 -~etc.

Usos práticos (também conhecido como golfe): usei essa tática para resolver esse desafio sem usar um personagem de handicap adicional.

Crédito para a lista de caracteres e um programa de codificação: aqui

Para obter informações sobre como encontrar um limite inferior no tamanho do programa resultante (sem otimizações), consulte este comentário .

O número de bytes necessários aumenta O(2**n), portanto esse método não é recomendado para golfe. Uma solução usando essa restrição de fonte seria insanamente longa.

C (não transportável), 24 18 13 caracteres

aimn[]={};,1+

Isso abrange todos os programas do formulário

main[]={<sequence of constants>};

... onde a sequência de constantes (do formato 1 + 1 + 1 ...) contém a representação do código da máquina do seu programa. Isso pressupõe que seu ambiente permita que todos os segmentos de memória sejam executados (aparentemente verdadeiro para tcc [obrigado @Dennis!] E algumas máquinas sem bit NX). Caso contrário, para Linux e OSX, talvez constseja necessário acrescentar a palavra-chave e, para Windows, você precisará adicionar um#pragma explicitamente marcação do segmento como executável.

Como exemplo, o programa a seguir escrito no estilo acima é impresso Hello, World!no Linux e OSX em x86 e x86_64.

main[]={111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+11111+11111+11111+11111+11111+11111+11111+11111+111+11+11+11+11+11+11+1+1,1111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1+1+1,111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+111+111+11+11+11+11+11+11+11+1,1111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+11+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+1+1+1+1+1+1+1,1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1,1111111111+111111111+111111111+111111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1,111111+111111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11+11+11+11+11,11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+11+11+11+1,111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1+1,11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1+1};

Experimente online!

Retina , 6 caracteres

$%`{¶

Bem como feeds de linha (0x0A).

Por um lado, estou surpreso por ter conseguido chegar tão baixo. Por outro lado, estou muito infeliz com a inclusão de %¶. Cada um deles $`{é reutilizado para dois ou até três propósitos, mas %¶ juntos servem apenas a um propósito. Isso os faz parecer um desperdício e destrói levemente a elegância da abordagem. Espero que haja uma maneira de superar essa construção.

Vamos para a prova. Vou descrever uma maneira simples de converter sistemas de tags cíclicos para Retina usando os caracteres acima.

Primeiro, usaremos `e {para o alfabeto binário em vez de 0e 1. Eles são convenientes, porque não precisam ser escapados em uma regex, mas têm significado para Retina ou na sintaxe de substituição. Estou usando `para 0e {para 1, mas essa escolha é arbitrária. Além disso, vamos reverter a string (e as produções) na memória, porque trabalhar com o último caractere nos permite usar $e $`não ^e $'maximizar a reutilização de caracteres.

Se a palavra inicial for denotada por Se a produção ith (invertida) for chamada , o programa resultante terá a seguinte aparência:pi

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Essa construção cresce inevitavelmente na memória toda vez que uma produção é aplicada e é improvável que termine - na verdade, no ponto em que o sistema de tags cíclicos terminaria (quando a cadeia de trabalho ficar vazia), o comportamento do programa Retina resultante se tornará basicamente indefinido.

Vejamos o que o programa faz:

S

Começamos inicializando a string de trabalho na palavra inicial.

{`

Isso envolve o restante do programa em um que é executado até que ele não mude a sequência resultante (ei, detecção ingênua de loop infinito embutida de graça ...). Os dois feeds de linha não são realmente necessários, mas separam o loop mais claramente das produções individuais. O restante do programa passa por cada uma das produções e, devido ao loop, estamos efetivamente processando-as ciclicamente repetidamente.

Cada produção é processada em dois estágios. Primeiro, lidamos com o caso do símbolo inicial (ou no nosso caso, à direita) {; nesse caso, usamos a produção:

{$
¶pi$%``

A regex corresponde apenas se a sequência terminar {. Se for esse o caso, substituímos por:

• Um avanço de linha ( ¶). Trabalharemos apenas com a última linha da string de trabalho, então isso efetivamente descarta a string de trabalho até agora (e é por isso que o uso de memória do programa aumentará e aumentará).
• A produção atual ( ), que estamos anexando à string de trabalho (onde o sistema de tags cíclicas a anexa).pi
• A sequência de trabalho restante anterior ( $%`). É por isso que precisamos inserir ¶: $%`pega tudo o que resta da partida, mas apenas na mesma linha. Portanto, isso não vê todo o lixo que resta de produções anteriores. Esse truque permite combinar algo no final da sequência de trabalho para inserir algo no início da sequência de trabalho, sem precisar usar algo como (.+)e$1 que explodiria significativamente o número de caracteres que precisamos.
• Um único bastão ( `). Isso efetivamente substitui o símbolo {( 1) correspondente ao símbolo `( 0), para que o próximo estágio não precise saber se já processamos a produção atual ou não.

A segunda parte de cada produção é o caso trivial em que a produção é ignorada:

``$

Simplesmente excluímos um final `. A razão pela qual precisamos de dois `na primeira linha é que o Retina considera o primeiro backtick o divisor entre configuração e regex. Isso simplesmente fornece uma configuração vazia para que possamos usar backticks no próprio regex.

Java 7, 18 e 17 caracteres

\bcdefu0123456789

Todo o código-fonte java pode ser reduzido para pontos de código unicode. "a" não é necessário, pois é usado apenas para *:jJzZ. O Asterisk é usado para multiplicar ou bloquear comentários. A multiplicação é apenas uma adição repetida e você pode usar comentários de linha única (ou simplesmente omiti-los). Os dois pontos são usados ​​para operadores ternários, nos quais você pode usar uma instrução if e foreach loops, que podem ser substituídos pelo normal para loops. j e z não fazem parte de nenhuma palavra-chave em java.

Tentar remover qualquer outro caractere exige que adicionemos pelo menos um dos caracteres exigidos no Java Boiler Plate class a{public static void main(String[]a){}}. Ver abaixo:

1 -> a (which has already been removed)
2 -> r (required for "String")
3 -> S (required for "String")
4 -> t (required for "static")
5 -> S (required for "String")
6 -> v (required for "void")
7 -> g (required for "String")
8 -> ( (required for "main(String[]a)"
9 -> i (required for "static")
b -> { (required for "class a{")
c -> l (required for "class")
d -> } (required for "(String[]a){}}")
e -> n (required for "main")
f -> o (required for "void")

Aqui está um exemplo com o programa Hello World Experimente online!

Java 8, 16 caracteres

\bdefu0123456789

Obrigado ais523 por apontar isso. O Java 8 permite que as interfaces tenham métodos estáticos, o que significa que podemos eliminar "c" porque não precisamos dele para o "l" na "classe". Como "c" é usado ,<lL\|, acabamos perdendo um pouco mais a funcionalidade java do que quando removemos "a", mas ainda temos o suficiente para estar completo. Experimente online!

Labirinto , 5 caracteres

~{}

Alimentações de linha positivas (0x0A) e espaços (0x20).

Vou esboçar uma prova na forma de uma redução do Smallfuck (uma variante Brainfuck reduzida que usa células de 1 bit). Observe que o próprio Smallfuck não é completo em Turing porque o idioma especifica que sua fita precisa ser finita, mas vamos assumir uma variante do Smallfuck com uma fita infinita, que seria então completa em Turing (como Labyrinth não tem memória restrições de design).

Uma invariante importante durante toda essa redução será que todo programa (ou subprograma) resultará em um programa (ou subprograma) de labirinto que inicia e termina na mesma linha e abrange um número par de colunas.

O labirinto possui duas pilhas que são inicialmente preenchidas com uma quantidade infinita (implícita) de 0 s. {e }mude o valor máximo entre essas pilhas. Se considerarmos que o topo da pilha principal é a "célula" atual, essas duas pilhas podem ser vistas como as duas metades semi-infinitas da fita infinita usada pelo Smallfuck. No entanto, será mais conveniente ter duas cópias de cada valor de fita nas pilhas, para garantir a invariante mencionada acima. Portanto, <e >será traduzido para {{e }}, respectivamente (você pode trocá-los, se quiser).

Em vez de permitir que os valores das células 0 e 1, estamos usando 0e -1, com o qual podemos alternar ~(negação bit a bit). Os valores exatos não importam para os propósitos da integridade de Turing. Temos que alterar as duas cópias do valor na pilha, o que nos dá uma tradução uniforme novamente: *torna - se ~}~{.

Isso deixa os comandos de fluxo de controle []. O labirinto não possui fluxo de controle explícito, mas o fluxo de controle é determinado pelo layout do código. Exigimos os espaços e os feeds de linha para fazer esse layout.

Primeiro, observe que ~~ é uma operação, pois os dois ~cancelam efetivamente. Podemos usar isso para ter caminhos arbitrariamente longos no código, desde que o comprimento seja par. Agora podemos usar a seguinte construção para traduzir AA[BB]CCpara o labirinto (estou usando letras duplas para que o tamanho de cada trecho no labirinto seja uniforme, conforme garantido pelo invariante):

      ~~~~
      ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Aqui, .. é um número adequado ~que corresponde à largura de BB.

Mais uma vez, observe que a largura da construção permanece uniforme.

Agora podemos ver como esse loop funciona. O código é inserido via AA. O primeiro~~ não faz nada e nos permite chegar à junção. Isso corresponde aproximadamente a [:

• Se o valor atual da célula for zero, o IP continuará em frente, o que acabará sendo ignorado BB. A ..parte ainda é um no-op. Então chegamos a um single ~em outro cruzamento. Agora sabemos que o valor atual é diferente de zero, portanto o IP faz a curva para o norte. Ele gira em torno da curva no topo, até chegar a outro cruzamento depois das seis ~. Portanto, nesse ponto, o valor atual ainda é diferente de zero e o IP faz a curva novamente para mover para leste em direção a CC. Observe que os três ~antes do CCretorno retornam o valor atual 0, como deveria ser quando o loop foi ignorado.
• Se o valor atual da célula no início do loop for diferente de zero, o IP fará a curva para o sul. Corre mais seis ~antes de chegarBB (que não faz nada) e depois outros seis ~antes de chegar ao próximo cruzamento. Isso corresponde aproximadamente ao ].
  • Se a célula atual for zero, o IP continuará se movendo para o norte. O próximo ~torna o valor diferente de zero, para que o IP use essa segunda junção, que mescla o caminho com o caso em que o loop foi ignorado completamente. Novamente, os três ~retornam o valor a zero antes de chegar CC.
  • Se a célula atual for diferente de zero, o IP fará a curva para oeste. Existem ~antes da próxima junção, o que significa que, neste ponto, o valor atual é zero, para que o IP continue indo para o oeste. Depois, haverá um número ímpar ~antes de o IP alcançar a junção inicial novamente, para que o valor seja retornado -1e o IP se mova para o sul na próxima iteração.

Se o programa contiver loops, o primeiro AAprecisará ser estendido para a parte superior do programa, para que o IP encontre a célula correta para iniciar:

~     ~~~~
~     ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

É isso. Observe que os programas resultantes dessa redução nunca serão encerrados, mas isso não faz parte dos requisitos da integridade de Turing (considere a Regra 101 ou Fractran).

Finalmente, ficamos com a questão de saber se isso é ideal. Em termos de caracteres de carga de trabalho, duvido que seja possível executar melhor que três comandos. Pude ver uma construção alternativa baseada em máquinas Minsky com dois registros, mas isso exigiria =()ou =-~, tendo apenas um comando de manipulação de pilha, mas depois dois comandos aritméticos. Eu ficaria feliz em ser provado errado nisso. :)

Quanto aos comandos de layout, acredito que as alimentações de linha são necessárias, porque o fluxo de controle útil é impossível em uma única linha. No entanto, os espaços não são tecnicamente necessários. Em teoria, pode ser possível criar uma construção que preencha toda a grade com ~{}(ou =()ou =-~), ou faça uso de um layout irregular, em que as linhas não tenham o mesmo comprimento. No entanto, escrever um código como esse é incrivelmente difícil, porque o Labyrinth tratará todas as células como uma junção e você precisará ter muito cuidado para impedir que o código se ramifique quando não desejar. Se alguém puder provar ou refutar se é possível omitir o espaço para a perfeição de Turing, ficaria feliz em oferecer uma recompensa considerável por isso. :)

Haskell, 5 7 caracteres

()\->=;

Como linguagem funcional, Haskell, é claro, possui lambdas, portanto, simular o cálculo lambda é fácil. A sintaxe para lambdas é(\variable->body)argument portanto, precisamos de pelo menos os caracteres ()\->.
Além disso, precisamos de uma quantidade ilimitada de símbolos variáveis ​​para poder construir expressões lambda arbitrárias. Felizmente não precisamos de quaisquer novos personagens para isso, porque (>), (>>), (>>>), ..., são todos nomes de variáveis válidos. De fato, toda combinação de \->parênteses internos é um nome de variável válido, com exceção de apenas\ e ->, que são reservados para expressões lambda e --, que inicia um comentário de linha.

Exemplos:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))tipos para(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))tipos parat -> t1 -> t
• I =(\(>)->(>)) tipos parat -> t

Edit: No entanto, como ais523 apontou nos comentários, essa construção implementa o cálculo lambda digitado , que por si só não é completo para Turing porque não possui a capacidade de inserir loops infinitos. Para corrigir isso, precisamos de alguma função que execute recursão. Até agora, usamos lambdas sem nome, que não podem se chamar, porque, bem, elas não têm nome. Portanto, temos que adicionar os caracteres =e ;implementar uma fixfunção:

(>)=(\(-)->(-)((>)(-)));   -- equivalent to: f =(\ x -> x ( f  x ));

Com esta declaração, nosso cálculo lambda se torna Turing completo, no entanto, adicionamos =e ;não precisamos mais de lambdas, como você pode ver na resposta de nimi, que usa apenas ()=;.

CJam, 3 caracteres

Removido de )acordo com a sugestão de Martin Ender

'(~

Semelhante ao Python, dado como exemplo.

Usando '~você pode obter o ~personagem. Em seguida (, use- o para decrementá-lo para obter o caractere desejado ( ~o último caractere ASCII imprimível). ~avalia qualquer string como código CJam normal. As strings podem ser construídas obtendo o personagem [(através de decrementar ~), avaliando-o, colocando uma sequência de outros caracteres e, em seguida, avaliando o personagem ]. Com isso, você pode criar e executar qualquer programa CJam usando apenas esses três caracteres.

Cálculo 2 + 2 usando apenas '(~

Brain-Flak , 6 caracteres

(){}[]

Brain-Flak é um idioma minimalista, com apenas 8 caracteres disponíveis. No entanto, pode-se provar que existe um subconjunto de Brain-Flak que também é Turing completo, usando apenas 6 caracteres.

A primeira coisa que faremos é implementar uma Minsky Machine com apenas uma pilha de Brain-Flak. Se pudermos provar que uma Minsky Machine é possível com apenas uma pilha, podemos mostrar que Brain-Flak é Turing completo sem as <>e []nilads. Isso não salvará nenhum personagem imediatamente, mas será no futuro quando mostrarmos que<...> não é necessário.

Uma máquina Minsky é um tipo de autômato completo de Turing que possui um número finito de registros ilimitados e duas instruções:

• Incrementar o registro

• Se decréscimo diferente de zero, faça a transição para uma instrução especificada

Para configurar uma estrutura de goto no Brain-Flak, podemos usar o seguinte snippet:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Isso diminuirá o contador e será executado %sse zero. Um monte desses encadeados nos permitirá colocar um número na pilha que indicará qual linha queremos ir. Cada uma delas diminuirá o topo da pilha, mas apenas uma delas executará o código.

Usamos isso como invólucro para todas as instruções da Minsky Machine.

Incrementar um registro específico é muito fácil sem mudar a pilha. Isso pode ser alcançado com esta fórmula de string:

"({}<"*n+"({}())"+">)"*n

Por exemplo, para incrementar o terceiro registro, escreveríamos o seguinte código:

({}<({}<({}<({}())>)>)>)

Agora, apenas precisamos implementar a segunda operação. Verificar se um número é zero é bastante simples no Brain-Flak:

(({})){(<{}%s>)}{}

só executará %s se o TOS for zero. Assim, podemos fazer nossa segunda operação.

Desde Minsky Machines são Turing completo Brain-Flak também é Turing completa sem o uso do <>e[] operações .

No entanto, não ter reduzido o número de caracteres ainda porque <...>e [...]ainda estão em uso. Isso pode ser remediado com uma simples substituição. Uma vez que <...>é realmente equivalente a [(...)]{}em todos os casos. Assim, Brain-Flak é Turing completo sem o uso dos caracteres <e >(mais todos os no-ops).

> <> , 3 caracteres

> <> é factível em 3 com 1p-, que:

1          Push 1
p          Pop y, x, c and put the char c in cell (x, y) of the codebox
-          Subtraction: pop y, x and push x-y

pfornece reflexão, modificando o código-fonte 2D colocando caracteres na caixa de códigos. Com 1-, você pode inserir qualquer número na pilha, pois 1-subtrai um e 111-1--( x-(1-1-1) = x+1) adiciona um.

Depois que todos os 1p-comandos são executados, o ponteiro da instrução gira em torno, permitindo que ele execute o código "real".

Um exemplo de programa que calcula os números de Fibonacci ( desta resposta ) é:

111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1-1--1p

Experimente online! Após a 1p-execução de todos os comandos, o codebox fica assim:

01aa+v1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1- ...
@+&1->:?!;&:nao:

Exceto tudo após a vprimeira linha, este é um programa padrão de Fibonacci> <>.

bash, 9 caracteres

01456\$ '

O Bash possui uma sintaxe $'\nnn'para inserir caracteres com seus valores ascii octais. Podemos inserir o evalcomando neste formato como $'\145\166\141\154'. Primeiro, transformamos o resultado desejado em seus valores octais. Em seguida, convertemos quaisquer valores octais usando dígitos diferentes de 0, 1, 4, 5 e 6 em expressões avaliadas para os referidos valores octais usando $(())e subtração, acrescentando um evalà frente. Em nossa etapa final, adicionamos outra evale convertemos os parênteses e o sinal de menos em seus valores octais. Usando este método, podemos executar qualquer comando bash, para que este subconjunto esteja completo.

Exemplo:

dc torna-se

$'\144\143' que se torna

$'\145\166\141\154' \$\'\\144\\$((144-1))\' que se torna

$'\145\166\141\154' $'\145\166\141\154' $'\$\\\'\\\\144\\\\$\050\050144\0551\051\051\\\''

Incidente , 2 caracteres

Também não importa quais dois caracteres você escolhe; qualquer combinação de dois octetos é concluída em Turing em Incidente.

Na verdade, provar isso é muito mais difícil do que você imagina e, no momento em que escrevo, a página de discussão na Esolang sobre Incidentes é dedicada ao problema. Vou tentar fazer um resumo da prova mais simples conhecida abaixo, no entanto.

Antes da prova, alguns antecedentes. O incidente infere os tokens usados ​​no programa observando a fonte (um token é uma string que aparece exatamente três vezes na fonte, não é uma substring de outro token e não se sobrepõe a outro token em potencial). Como tal, qualquer programa pode ser convertido para usar praticamente qualquer conjunto de caracteres alterando quais são os tokens; o idioma é Turing-complete (e também possui integridade para E / S!), apesar de ser incrivelmente difícil de programar, portanto, "tudo" é necessário um método de codificação de tokens para que funcionem com apenas dois caracteres.

E agora, aqui está um resumo da prova (encontrada por Ørjan, matemático residente de Esolang). A idéia é que codifiquemos um token usando duas cópias de um caractere (digamos 1) em um grande mar do outro caractere (digamos 0). A distância entre 1s difere para cada token, mas é sempre um múltiplo de 4. Então, para o preenchimento entre os tokens, usamos uma lista extra de 0s com a 1no meio, mas o número de 0s em cada lado 1é não um múltiplo de 4, mas um número exclusivo para a incidência específica do programa que não aparece em nenhum outro local do programa. Isso significa que cada1 ...1dentro do preenchimento só pode aparecer duas vezes, portanto, não fará parte de um token; cada token pretendido contém exatamente dois 1s e nenhum token falso pode conter mais de um 1. Em seguida, adicionamos um pouco de preenchimento ao lado para remover todos os tokens possíveis contendo um 1ou zero 1s, adicionando pelo menos quatro cópias deles.

Retina , 3 caracteres

{`

e nova linha.

Primeiro, precisamos de nova linha para poder fazer substituições (necessárias, a menos que desejemos ajustar o programa inteiro em uma regex, que precisaria de mais caracteres); e `e {são a maneira menos caracteres intensivo para fazer loops. Acontece que não precisamos de mais nada.

Nossa linguagem-alvo a implementar é uma variante determinística de Thue (o não determinismo não é necessário para a integridade de Turing; é possível escrever um programa Thue para funcionar corretamente, independentemente da ordem de avaliação usada). A idéia básica é compilar pattern::=replacementem

`pattern
replacement

(que é uma tradução direta de retina do Thue; alternativamente, se você conhece Retina, mas não Thue, pode usá-lo como um método para aprender como o Thue funciona); como uma exceção, o primeiro padrão é precedido por um {`substituto (para colocar o programa inteiro em um loop; os programas continuam em execução até que não haja mais substituições possíveis e isso faz com que a Retina funcione da mesma maneira).

Obviamente, isso significa que precisamos provar que Thue Turing está completo com justos {e `nos padrões e substituição, mas isso é bastante simples; substituímos um caractere pelo código ascii n por `, n +1 {e outro `. É claramente impossível para um padrão corresponder a qualquer lugar, exceto nos limites dos caracteres, então isso acabará fazendo a mesma coisa que o programa original.

Braquilog , 5 caracteres

~×₁↰|

Esse subconjunto de caracteres nos permite implementar uma versão do Fractran na qual os únicos números que podem aparecer são produtos de repunits (ou seja, produtos de números que podem ser escritos em decimal usando apenas o dígito 1). ~×(com um número inteiro como subscrito) divide o valor atual por esse número inteiro, mas apenas se ele divide exatamente (caso contrário, "falha" e procura outro caso a ser executado; |separa os casos). ×vamos multiplicar por um número inteiro. Portanto, usando ~×₁|podemos implementar uma etapa da execução do Fractran. Em seguida, ↰vamos recursar, executando o programa inteiro novamente no novo valor atual. Aqui está um exemplo de um programa Fractran muito simples ( 11111111111111111111111/111) traduzido para o Brachylog.

Então esse Turing está completo? Tudo o que precisamos para completar o Fractran Turing é uma quantidade suficientemente grande de números primos (o suficiente para escrever um intérprete para uma linguagem completa de Turing no próprio Fractran). tem cinco comprovados e quatro suspeitosprimos de reembolso, além de, possivelmente, aqueles que ainda não foram descobertos. Isso é realmente mais do que precisamos neste caso. O programa verifica as possibilidades da esquerda para a direita, para que possamos usar um primo como ponteiro de instrução e mais dois como contadores, demonstrando a integridade de Turing com apenas três primos (uma coisa boa também, porque nos permite usar as repunições com 2, 19 e 23 dígitos, sem ter que recorrer às repunições comprovadas, mas irritantemente grandes, com 317 ou 1031 dígitos, o que tornaria o código-fonte bastante difícil de escrever). Isso possibilita a implementação de uma máquina Minsky com dois contadores (o suficiente para a integridade de Turing).

Veja como a compilação funciona especificamente. Usaremos os dois comandos a seguir para a implementação da máquina Minsky (isso é conhecido como Turing completo), e cada comando terá um número inteiro como rótulo:

• Etiqueta L: Se o contador {A ou B} for zero, vá para X. Caso contrário, diminua-o e vá para Y.
• Etiqueta L: incremente o contador {A ou B} e vá para Z.

Escolhemos qual comando executar, colocando potências de 11 no denominador, potências mais altas primeiro; o expoente de 11 é o rótulo do comando. Dessa forma, a primeira fração correspondente será o comando em execução no momento (porque as anteriores não podem ser divididas por todos os 11s). No caso de um comando de decréscimo, também colocamos um fator 1111111111111111111 ou 11111111111111111111111 no denominador, para o contador A ou B, respectivamente, e seguimos com outro comando sem esse fator; o caso "decremento" será implementado pelo primeiro comando, o caso "zero" pelo segundo. Enquanto isso, o "goto" será tratado por uma potência apropriada de 11 no numerador e "incrementado" por um fator de 1111111111111111111 ou 11111111111111111111111 no numerador.

Befunge-98, 3 caracteres

Até onde eu sei, o Befunge-98 deve estar completo, então precisamos mostrar como qualquer programa do Befunge-98 pode ser gerado usando apenas três caracteres. Minha solução inicial contava com os quatro caracteres a seguir:

01+p

Podemos obter qualquer número inteiro positivo na pilha adicionando vários 1valores junto com o +comando e, para zero, simplesmente usamos 0. Depois que tivermos a capacidade de enviar qualquer número que desejar, podemos usar op comando (put) para gravar qualquer valor ASCII em qualquer local no campo de jogo Befunge.

No entanto, como o Sp3000 apontou, você pode se dar bem com apenas os três caracteres:

1-p

Qualquer número negativo pode ser calculado começando com 1e subtraindo repetidamente 1(por exemplo, -3 seria 11-1-1-1-). Qualquer número positivo pode ser representado subtraindo 1-n de 1, onde 1-n é um número negativo com o qual já sabemos lidar (por exemplo, 4 = 1 - (- 3), o que seria111-1-1-1-- ).

Assim, podemos usar nossos três caracteres para escrever um tipo de carregador de inicialização que gera lentamente o código real que queremos executar. Depois que a execução do carregador terminar, será iniciada a primeira linha do campo de jogo, que nesse momento deve conter o início do nosso código recém-gerado.

Como exemplo, aqui está um gerenciador de inicialização que gera o código Befunge necessário para somar 2 + 2 e gerar o resultado: 22+.@

E para um exemplo um pouco mais complicado, este é "Hello World": "!dlroW olleH"bk,@

Ruby, 8 caracteres

eval"<1+

Inspirado pelas respostas do Python

Como funciona

• eval pode ser usado para executar uma string arbitrária.
• "<1+ é o conjunto mínimo de caracteres necessários para criar qualquer sequência

Uma string em ruby ​​pode ser criada usando a string vazia como ponto de partida e anexando caracteres ascii a ela, por exemplo:

eval ""<<111+1<<11+11+11+1<<111<<11+11+11+1

é realmente equivalente a

eval ""<<112<<34<<111<<34

que avalia a string

p"o"

OCaml, 9 caracteres

fun->()`X

Esses caracteres são suficientes para implementar o SKI Combinator Calculus no OCaml. Notavelmente, somos capazes de evitar o uso do espaço com parênteses suficientes. Infelizmente, as expressões lambda no OCaml requerem ofun palavra chave, portanto, uma solução mais concisa não é possível. As mesmas letras podem ser usadas para criar nomes de variáveis ​​arbitrários, se desejar expressões lambda mais complexas.

Combinador S:

fun(f)(u)(n)->f(n)(u(n)) com tipo ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Combinator:

fun(f)(u)->u com tipo 'a -> 'b -> 'b

Eu Combinador:

fun(f)->f com tipo 'a -> 'a

Conforme observado pelo ais523, é insuficiente codificar simplesmente SKI. Aqui está uma codificação para Z usando variantes polimórficas para manipular o sistema de tipos. Com isso, meu subconjunto deve estar completo.

Combinador Z:

fun(f)->(fun(`X(x))->(x)(`X(x)))(`X(fun(`X(x))y->f(x(`X(x)))y))

com tipo (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Linguagens concatenativas baseadas em pilha, 4 caracteres

Sob carga

():^

GolfScript

{}.~

CJam

{}_~

GS2

• backspace, tab,, @space (eu sabia que o GS2 usava muito os imprimíveis, mas isso é ridículo…)

dc (sugerido por @seshoumara)

[]dx

A subcarga foi comprovada como completa em Turing apenas com o uso de ():^(graças ao matemático residente Ørjan de Esolang). A prova é longa demais para ser explicada aqui, mas se você estiver interessado, pode ler sobre isso aqui .

Os comandos em questão são ()(literal de código de lugar na pilha), :(elemento duplicado da pilha superior) e ^(avaliar o topo da pilha). Esses comandos são bastante comuns em linguagens baseadas em pilha (especialmente linguagens concatenativas), e, portanto, eu dei uma espécie de coleção deles acima; esses idiomas são todos completos em Turing em 4 caracteres pelo mesmo motivo que o Underload.

Espaço em branco, 3 caracteres

STL

Sé espaço, Té tabulação e Lé nova linha.

Raquete (esquema), 4 caracteres

(λ)

Usando apenas λ, parênteses e espaço, podemos programar diretamente no subconjunto Lambda Calculus do Scheme. Reutilizamos o caractere λ para todos os identificadores, concatenando-os juntos para fornecer um número arbitrariamente grande de identificadores exclusivos.

Como exemplo, aqui está o clássico combinador Omega, que faz um loop para sempre.

((λ (λλ) (λλ λλ)) (λ (λλ) (λλ λλ)))

Python 3, 9 caracteres

exc('%1+)

Veja meu resposta do Python 2 para uma explicação básica. Essa resposta se baseia nessa.

Em vez de simplesmente usar os mesmos caracteres que o Python dois com a adição de (), podemos descartar um caractere, já que agora temos o uso de parênteses. Os programas ainda terão a forma básica de

exec('%c'%stuff)

mas reduzimos o comprimento do programa usando em +vez de -e, em seguida, podemos removê-lo ~usando em 1vez de 0. Podemos, então, adicionar 1, 11e 111para obter os valores ASCII necessários.

O programa print()se torna o seguinte, no mínimo:

exec('%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c'%(111+1)%(111+1+1+1)%(11+11+11+11+11+11+11+11+11+1+1+1+1+1+1)%(11+11+11+11+11+11+11+11+11+11)%(111+1+1+1+1+1)%'('%')')

Experimente online

Você pode estar pensando: como criar um byte NUL sem 0? Não tema, jovem gafanhoto! pois também temos a capacidade de usar %matemática, criando zero com 1%1.

PHP 7, 6 caracteres

'().;^

A idéia é que é possível executar código arbitrário usando a seguinte construção:

('create_function')('','<code>')();

eval não funcionaria aqui, porque é uma construção de linguagem e não pode ser chamada usando funções variáveis.

create_function e o código pode ser escrito como uma concatenação de XORs bit a bit de caracteres disponíveis:

(<char1_1>^<char1_2>^...).(<char2_1>^<char2_2>^...)...

Usando ().;^para <charX_Y>, podemos obter

()./:;<=JKLMXY^_bcdepqvw

e alguns caracteres não imprimíveis. Não é suficiente, mas agora podemos ligar 'eXp'()e obter alguns caracteres numéricos também:

''.'eXp'('eXp'('')) -> 1
''.'eXp'('eXp'('eXp'(''))) -> 2.718281828459
''.'eXp'('eXp'('eXp'('eXp'('eXp'(''))))) -> 3814279.1047602

Ele nos fornece 1, 2e 3(outros caracteres serão ignorados pelo XOR, se a outra sequência tiver um caractere). De().;^123 agora podemos gerar todo o conjunto de caracteres ASCII.

Experimente online

Pyke, 5 caracteres

0h.CE

Isso é capaz de produzir um número infinitamente grande, transformá-lo em uma string e, em seguida, avaliá-lo como código Pyke.

Explicação do código:

0- Adicione 0 à pilha. Isso é necessário para iniciar um número

h- Incremente o número antes. Repetindo isso uma quantidade arbitrária de vezes, você pode criar números infinitamente grandes. O Pyke suporta bignums como está escrito em Python, que os usa como padrão.

.C- Transforme um número em uma string usando o seguinte algoritmo: ( link do Github )

def to_string(num):
    string = ""
    while num > 256:
        num, new = divmod(num, 256)
        string = chr(new) + string
    string = chr(num) + string
    return string

Nesse ponto, podemos criar uma quantidade arbitrária de strings e números naturais no Pyke com valores arbitrários. Os números podem ser criados no formato correspondente à regex 0(h)*e as cadeias podem ser criadas com 0(h)*.C. Eles podem ser entrelaçados entre si para criar uma mistura arbitrária de seqüências de caracteres e números inteiros.

E- avalie uma string como código Pyke. Isso usa o mesmo ambiente que o código Pyke já em execução e, portanto, compartilhará coisas como a entrada.

Tentativa de provar que Pyke é Turing Complete.

Uma das maneiras mais simples de mostrar que um idioma está completo é implementando o Brainf * ck nele. Provavelmente, isso é muito mais difícil no Pyke do que em outros idiomas, porque as operações de lista e dicionário são praticamente inexistentes devido à falta de necessidade delas na área em que o Pyke foi projetado para executar: code-golf .

Primeiro, criamos um intérprete para brainf * ck e o codificamos usando nosso algoritmo acima para criar um número e depois expressá-lo com 0e h. Em seguida, criamos a sequência que contém o código a ser executado exatamente da mesma maneira. Se deixássemos assim, teríamos a pilha como

string containing brainf*ck code
string containing brainf*ck interpreter

Isso significa que o código deve estar na forma oposta, pois a pilha Pyke é a primeira a sair pela última vez.

Agora, a parte divertida: o intérprete brainf * ck com impressionantes 216 bytes!

Q~B"><ht.,".:=B;Z]1=L;W~Bo@D=c"ht"{I~c~LZ@EZ]1~LR3:=L)~c\,qIz.oZ]1~LR3:=L)~c\[email protected])~c"<>"{I~c"<>""th".:ZE=ZZ1_qI0=Z~L0"":0]10:=L)Z~LlqI~L~Ll"":1_]10:=L))~c\[qI~LZ@0qI\]~B~o>@~o+h=o))~c\]qI~o\[~B~o<_@-t=o)~o~BlN

Experimente aqui!

Se você quiser experimentar o código em formato semi-preenchido, mas editável, tente aqui!

Para converter de uma sequência em um número, você pode usar o seguinte código Python:

def conv(string, t=0):
    t *= 256
    t += ord(string[0])
    if len(string) != 1:
        return conv(string[1:], t)
    return t

A (quase) solução final pode ser tentada aqui!

Explicação do intérprete Brainf * ck

Primeiro vamos separar o programa em partes:

• A inicialização:

O que outras pessoas estão dizendo

Q~B"><ht.,".:=B;Z]1=L; - The initialisation part
Q~B"><ht.,".:          - input.replace("><+-.,[]", "><ht.,")
                       - replace the characters in brainf*ck with some modified ones. 
                       - this means we can `eval` the add and subtract bits easily.
             =B;       - set `B` to this.
                       - The `B` variable contains the instructions
                Z]1=L; - set `L` to [0]
                       - `L` contains the stack, initialised with 0

• O loop principal:

O que outras pessoas estão dizendo

W~Bo@D=c !code! ~o~BlN - The main loop
W                      - do
 ~Bo@D=c               -  c=B[o++]
                       -  the c variable is used to store the current character.
                ~o~BlN - while
                ~o     -   o 
                     N -  ^ != V 
                  ~Bl  -   len(B)
                       -  this stops the program running once it's finished.

• As instruções
  • Aumentar / diminuir:+-

O que outras pessoas estão dizendo

"ht"{I~c~LZ@EZ]1~LR3:=L) - The bit that does incrementing and decrementing
"ht"{I                 ) - if c in "ht"
        ~LZ@             -  L[Z]
                         -  `Z` contains the current stack pointer
      ~c    E            -  eval current character with ^ as an argument
                         -  returns the contents of `Z` either incremented or decremented
             Z]1~LR3:=L  - L[Z] = ^

• Entrada ,:

O que outras pessoas estão dizendo

~c\,qIz.oZ]1~LR3:=L) - The code for output 
~c\,qI             ) -  if character == ",":
      z.o            -    ord(input)
         Z]1~LR3:=L  -   L[Z] = ^

• Saída .:

O que outras pessoas estão dizendo

~c\[email protected]) - The code for input 
~c\.qI        ) - if c == ".":
      ~LZ@      -    L[Z]
          .C    -   chr(^)
            pK  -  print(^)

• Deslocar Esquerda / Direita <>::

O que outras pessoas estão dizendo

~c"<>"{I~c"<>""th".:ZE=Z - main part 
~c"<>"{I                 - if "<>" in c:
        ~c"<>""th".:     -  c.replace("<>", "th")
                    ZE=Z -  Z = eval(char, Z)

Z1_qI0=Z~L0"":0]10:=L) - lower bound check
Z1_qI                ) - if Z == -1:
     0=Z               -  Z = 0
        ~L0"":         -  L.insert("", 0)
              0]10:=L  -  L[0] = 0

Z~LlqI~L~Ll"":1_]10:=L) - upper bound check
Z~LlqI                ) - if Z == len(L):
        ~Ll"":          -  L.insert("", len(L))
      ~L      1_]10:=L  -  L[-1] = 0

• Os condicionais [::

O que outras pessoas estão dizendo

~c\[qI~LZ@0qI\]~B~o>@~o+h=o)) - Code for `[`
~c\[qI                      ) - if c == "[":
      ~LZ@0qI              )  -  if L[Z] == 0:
               ~B~o>          -     B[o:]
             \]     @         -    ^.find("]")
                     ~o+h=o   -   o = o + ^ + 1

- e ]:

O que outras pessoas estão dizendo

~c\]qI~o\[~B~o<_@-t=o) - Code for `]`
~c\]qI               ) - if c == "]":
          ~B~o<_       -    reversed(B[:o])
        \[      @      -   ^.find("[")
      ~o         -t=o  -  o = o - ^ -1

Empilhados, 5 caracteres

{!n:}

Isso é surpreendentemente curto. Se o Stacked puder implementar cada uma das combinações de SKI, será Turing Complete. Recapitular:

• I combinador - a função de identidade. x -> x
• K combinador - a função constante. x -> y -> x
• S combinador - a função de substituição. (x, y, z) -> x(z)(y(z))

Eu combinador: {!n}

Agora, para os detalhes empilhados. {! ... }é um n-lambda. É uma função unária cujo argumento é implicitamente n. Em seguida, a última expressão é retornada da função. Assim, {!n}é uma função que pega um argumento ne geran .

K combinador: {!{:n}}

Agora, {:...}é uma função que não aceita argumentos e retorna .... Combinando isso com a nossa formação n-lambda, obtemos (adicionando espaço em branco para maior clareza):

{! { : n } }
{!         }   n-lambda. arguments: (n)
   { : n }     lambda.   arguments: ()
       n       yields n.

Combinador S: {n!nn!nnn:nnn{!n}!nn!nnn{!n}!n!!}

Ok, isso parece um pouco mais complicado. Portanto, um lambda recebe argumentos, separados por caracteres não identificadores. Assim, o lambda no cabeçalho é equivalente a:

{n nn nnn:nnn{!n}!nn!nnn{!n}!n!!}

Este é um lambda que leva três argumentos, n, nn, e nnn. Vamos substituí-las por x, ye zpara maior clareza:

{x y z:z{!n}!y!z{!n}!x!!}

Os dois {!n}!são apenas funções de identidade para evitar novamente espaços em branco, onde !significa "executar". Então, novamente, reduzindo:

{x y z:z y!z x!!}

Com uma explicação:

{x y z:z y!z x!!}
{x y z:         }  three arguments
       z y!        apply `y` to `z` -- `y(z)`
           z x!    apply `x` to `z` -- `x(z)`
               !   apply `x(z)` to `y(z)` -- `x(z)(y(z))`

E, portanto, este é o combinador S.