Sommaire:

Quelle que soit la langue donnée, quelle est la plus petite quantité de caractères uniques pour que votre langue soit Turing-Complete ?

Défi:

Pour la langue de votre choix, recherchez le plus petit sous-ensemble de caractères permettant à votre langue d'être Turing-Complete. Vous pouvez réutiliser votre jeu de caractères autant de fois que vous le souhaitez.

Exemples:

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

• Brainfuck: +<>[](suppose une taille de cellule d'emballage)

• Python 2: ()+1cehrx(fabriqué à partir de scripts comme exec(chr(1+1+1)+chr(1)))

Notation:

Ce défi est marqué en caractères , pas en octets . Par exemple, les scores pour les exemples sont 6, 5 et 9.

Remarques:

• Ce défi se différencie des autres en ce sens que votre langue est uniquement Turing-Complete (vous ne pouvez pas nécessairement utiliser toutes les fonctionnalités de la langue.)

• Bien que vous puissiez le faire, veuillez ne pas poster de réponses sans réduire les caractères utilisés. Exemple: Brainfuck avec 8 caractères (car tous les autres caractères sont des commentaires par défaut.)

• Vous DEVEZ au moins expliquer brièvement pourquoi votre sous-ensemble est Turing-Complete.

Haskell, 4 caractères

()=;

Avec ()=nous pouvons définir S, K et I. Les définitions doivent être séparées par un ;ou par un NL.

Nous définissons (==)comme S (la deuxième ligne montre une version plus lisible):

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

(===) demander:

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

et (====)comme je:

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

Heureusement (==), (===), (====), etc. sont fonction valides / noms de paramètres.

Comme @ ais523 le souligne, SKI ne suffit pas dans un langage fortement typé comme Haskell, nous devons donc ajouter un combinateur de points fixes (=====):

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

JavaScript (ES6), 5 caractères

Merci à @ETHproductions et @ATaco pour leur aide dans ce domaine; Il s’agissait d’un projet de groupe et, bien que l’idée de départ soit la mienne, de nombreux détails leur appartiennent. Voir la discussion en ligne où ce sous-ensemble JavaScript a été développé ici .

[]+=`

Il est assez bien établi que tout programme Javascript peut être écrit avec les caractères ( []()+!), mais 5 caractères ne suffisent pas . Cependant, l'écriture de code JavaScript arbitraire n'est pas un défi. C'est un défi d'écrire un langage complet avec Turing et d'utiliser le fait que ces langages n'ont pas besoin d'accéder au DOM, ni même aux E / S interactives, il s'avère que nous pouvons écrire un programme avec toutes les fonctionnalités requises. , même sans aucune capacité à exécuter un evalou un équivalent.

Amorçage de base

JavaScript est très flexible avec les types. Ainsi, par exemple, []est un tableau vide, mais +[]vaut 0 et []+[]représente la chaîne nulle. Notamment, le fait de pouvoir produire 0 avec ce jeu de caractères permet de simuler l’effet des parenthèses pour le regroupement; (a)peut être écrit comme [a][+[]]. Nous pouvons utiliser ce genre d’astuce pour produire différents personnages en utilisant seulement +[]:

• [][+[]]is undefined(étant le premier élément d'un tableau vide); alors
• []+[][+[]]est "undefined"(la stringification de undefined); alors
• [[]+[][+[]]]est ["undefined"](envelopper cela dans un tableau); alors
• [[]+[][+[]]][+[]]is "undefined"(son premier élément); alors
• [[]+[][+[]]][+[]][+[]]est "u"(sa première lettre).

uest l’un des personnages les plus faciles à créer, mais des techniques similaires nous permettent de créer une gamme d’autres personnages. Le même lien que précédemment nous donne la liste suivante de caractères accessibles avec +[](c'est la même liste que pour +[](), à l'exclusion, ,car c'est la seule construction qui utilise des parenthèses à une fin autre que le regroupement / la priorité):

0123456789acdefinotuvyIN (){}.

Nous ne pouvons pas épeler beaucoup de mots utiles dans cet ensemble de caractères (rappelez-vous qu'il s'agit de l'ensemble des caractères que nous pouvons produire sous forme de chaînes ; nous ne pourrons pas les exécuter sans une sorte de eval). En tant que tel, nous avons besoin d'un autre personnage. Nous l'utilisons =, car il sera utile plus tard, mais pour le moment, nous l'utilisons pour épeler l'opérateur de comparaison ==. Cela nous permet de produire falseet true, ce qui peut être structuré et indexé, et nous permet d’ajouter immédiatement lrsaux caractères que nous pouvons inclure dans des chaînes.

De loin, le mot le plus important que cela nous permet d'épeler, que nous ne pouvions pas auparavant, est constructor. Maintenant, JavaScript a une syntaxe d'accès de propriété qui ressemble à ceci:

object.property

mais vous pouvez aussi l'écrire comme ceci:

object["property"]

et rien ne nous empêche d'utiliser une propriété calculée, plutôt qu'un littéral de chaîne. Nous pouvons donc faire quelque chose dans le sens de

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

(avec les lettres générées comme décrit ci-dessus; le code devient rapidement très long!); c'est équivalent à object.constructor, ce qui nous permet d'accéder aux constructeurs d'objets arbitraires.

Nous pouvons faire plusieurs astuces avec cela. Du banal au fantastique:

• Le constructeur d'un objet est une fonction. Notamment, il a un nom et ce nom fait partie de la chaîne de caractères de la fonction. Donc, par exemple, nous pouvons faire [[]+[]][+[]]["constructor"]pour obtenir le constructeur d'une chaîne, dont le nom est String, puis le lustrer pour obtenir le Scaractère majuscule . Cela élargit un peu notre alphabet et nous aurons besoin de certains des nouveaux caractères plus tard.

• Tous les tableaux ont le même constructeur. []["constructor"] == []["constructor"]est true(contrairement à [] == []ce qui est faux). Cela peut sembler mineur, mais c'est très important, car cela nous donne une méthode pour stocker les valeurs de manière persistante; nous pouvons définir une propriété aléatoire sur le constructeur et la relire plus tard. (C’est l’une des raisons pour lesquelles nous l’utilisons =en particulier, plutôt que l’un des autres moyens de générer trueet false.) Par exemple, nous pouvons évaluer [[]["constructor"]["a"]=[]], puis lire []["constructor"]["a"]et récupérer le même tableau que nous y avons stocké.

  Cela répond à l' une des exigences dont nous avons besoin pour la complétude de Turing , à savoir la capacité de stocker et de récupérer des quantités arbitraires de données. Nous pouvons créer une cellule contre en utilisant un tableau à deux éléments, en prenant des valeurs de notre stockage de propriétés de constructeur, puis en le stockant à la place de l'une de ces valeurs, ce qui nous permet de construire des structures de données arbitrairement grandes en mémoire; et nous pouvons accéder à ce stockage en procédant à l’inverse, en le décomposant jusqu’à ce que les données souhaitées deviennent accessibles. La lecture est destructrice, mais cela est acceptable car nous disposons de plusieurs emplacements pour stocker les données. Nous pouvons donc les copier au fur et à mesure que nous les lisons, puis replacer la copie à l'emplacement d'origine.

• Cela nous permet d’obtenir le constructeur d’une fonction (il existe de nombreuses fonctions []["find"]auxquelles nous pouvons accéder avec notre alphabet limité; c’est-à-dire Array.find, c’est la plus accessible, mais il y en a d’autres). Pourquoi est-ce utile? Eh bien, nous pouvons en fait l’utiliser dans le but recherché pour un constructeur et construire des fonctions! Malheureusement, avec notre jeu de caractères, nous ne pouvons pas transmettre au constructeur de fonction une chaîne calculée. Cependant, l’utilisation de lui `laisse un littéral de chaîne (par exemple []["find"]["constructor"]`function body goes here`); cela signifie que nous pouvons définir des valeurs personnalisées de type de fonction avec n'importe quel comportement à l'exécution, tant que nous pouvons exprimer ce comportement entièrement à l'aide de []+=. Par exemple, []["find"]["constructor"]`[]+[]`est une fonction assez ennuyeuse qui calcule la chaîne nulle, la supprime et quitte. cettela fonction n'est pas utile, mais les plus complexes le seront. Notez que, bien que les fonctions ne puissent prendre de paramètres ou renvoyer de valeurs, ce ne sont pas des problèmes pratiques car nous pouvons utiliser le stockage constructeur-propriété pour communiquer d'une fonction à une autre. Une autre restriction est que nous ne pouvons pas utiliser `dans le corps d'une fonction.

  Nous pouvons maintenant définir des fonctions personnalisées, mais ce qui nous retient pour l’instant, c’est la difficulté que nous avons à les appeler . Au niveau supérieur du programme, nous pouvons appeler une fonction avec ``, mais pouvoir appeler des fonctions uniquement à partir du niveau supérieur ne nous permet pas de faire une boucle. Nous avons plutôt besoin de fonctions pour pouvoir s’appeler.

  Nous accomplissons cela avec une astuce plutôt astucieuse. Rappelez-vous le capital que Snous avons généré plus tôt? Cela nous permet d'épeler "toString". Nous n'allons pas l'appeler; nous pouvons convertir des choses en chaînes en y ajoutant []. Nous allons plutôt le remplacer . Nous pouvons utiliser le stockage constructeur pour définir des tableaux persistants qui restent. Nous pouvons ensuite assigner les fonctions que nous avons créées aux toStringméthodes des tableaux , et ces assignations resteront également fidèles. Maintenant, tout ce que nous avons à faire est un simple +[]sur le tableau, et tout à coup, notre fonction personnalisée s’exécutera. Cela signifie que nous pouvons utiliser les caractères+=[]appeler des fonctions, et donc nos fonctions peuvent s’appeler les unes les autres - ou elles-mêmes. Cela nous donne la récursion, ce qui nous donne des boucles, et tout à coup nous avons tout ce dont nous avons besoin pour la complétude de Turing.

Voici un aperçu d'un ensemble de fonctionnalités qui donnent à Turing une complétude et comment elles sont implémentées:

• Stockage non lié : tableaux imbriqués dans le stockage du constructeur
• Flux de contrôle : implémenté en utilisant ifet récursivité:
  • if: convertit un booléen en nombre et indexe dans un tableau à 2 éléments; un élément exécute la fonction pour le thencas où stringified, l'autre élément exécute la fonction pour le elsecas quand stringified
  • Récursion : stringifier un élément approprié du stockage du constructeur
• Séquencement des commandes : [a]+[b]+[c]évalue a, bet de cgauche à droite (au moins sur le navigateur que j'ai coché)

Malheureusement, c'est assez peu pratique; non seulement il est énormément grand étant donné que les chaînes doivent être construites caractère par caractère à partir de principes premiers, il n'a également aucun moyen de faire des E / S (qui n'est pas obligé d'être complet de Turing). Toutefois, si elle se termine, il est au moins possible de rechercher ultérieurement dans le stockage du constructeur, de sorte qu'il n'est pas impossible de déboguer vos programmes, qui ne sont pas complètement non communicants.

Unaire , 1 caractère

0

Le choix du personnage n'a pas vraiment d'importance; la longueur du programme définit le programme de brainfuck où il transpile. Bien que la spécification exige des 0caractères, la plupart des transpileurs ne semblent pas vérifier cela.

vim, 9 8 7 6 caractères

<C-v><esc>1@ad

Nous pouvons construire et exécuter un programme vimscript arbitraire comme suit:

1. Utilisez la séquence aa<C-v><C-v>1<esc>dd@1<esc>ddddpour obtenir un <C-a>registre in 1.

2. Passez en mode insertion avec a, puis insérez-en un a, qui sera utilisé pour revenir au mode insertion ultérieurement dans une macro.

3. Pour chaque caractère du programme vimscript souhaité,

   1. utiliser <C-v><C-v>1<esc>pour insérer la séquence littérale <C-v>1,

   2. use @1(c'est-à-dire <C-a><cr>, dans lequel la finale <cr>est un no-op du fait d'être sur la dernière ligne) autant de fois que nécessaire pour incrémenter 1jusqu'à ce que la valeur ASCII du caractère souhaité soit atteinte,

   3. et revenez en mode insertion avec a.

4. Supprimez la ligne (avec une nouvelle ligne) dans le 1registre avec <esc>dd.

5. Exécutez le résultat sous forme de frappes vim en utilisant @1, puis <esc>ddsupprimez la ligne entrée par la nouvelle ligne de fin de l'étape précédente.

6. Exécutez la séquence arbitraire résultante d'octets avec dd@1. S'il commence par un :, il sera interprété comme du code vimscript et sera exécuté en raison du retour à la ligne de fin dd.

Je ne suis pas convaincu qu'il s'agisse d'un jeu de caractères minimal, mais il est assez facile de prouver que Turing est complet.

Perl, 5 caractères

<>^es

Comme avec d'autres langages de script, l'idée est d' evalutiliser des chaînes arbitraires. Cependant, notre jeu de caractères n'inclut pas de guillemets ni d'opérateurs de concaténation. La construction de chaînes arbitraires sera donc beaucoup plus complexe. Notez que ce eval^"serait beaucoup plus simple à gérer, mais a encore un caractère.

Notre outil principal est s<^><CODE>ee, qui évalue CODE, puis évalue sa sortie. Plus epeut être ajouté, avec l'effet attendu.

Nous obtenons des chaînes en utilisant <>, qui est l'opérateur glob sauf quand ce n'est pas le cas. Le premier caractère ne peut pas être <(sinon il ressemble à l' <<opérateur), les crochets doivent être équilibrés et il doit y avoir au moins un caractère autre que lettre (sinon, il est interprété comme l'opérateur readline).

En xorisant ces chaînes ensemble, nous pouvons obtenir n'importe quelle combinaison de caractères ^B^V^S(*-/9;<>HJMOY[`\^begqstv, à condition que nous acceptions de laisser des débris (les trois premiers sont des caractères de contrôle).

Par exemple, supposons que nous voulons obtenir "v99". Une façon d'obtenir v99est "><<" ^ "e>>" ^ "see" ^ "^^^", mais nous ne pouvons pas représenter ces chaînes en raison des contraintes <>. Au lieu de cela, nous utilisons:

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

Les rendements ci-dessus Y9;v99;, qui, une fois évalués, donnent le même résultat qu’un simple v99(à savoir, le caractère avec le code ASCII 99).

Ainsi, nous pouvons utiliser tout le ^B^V^S(*-/9;<>HJMOY[`\^begqstvjeu de caractères pour générer notre chaîne arbitraire, puis la convertir comme ci-dessus et la coller dans un s<><CODE>eeeepour l'exécuter. Malheureusement, ce jeu de caractères est encore très limité, sans aucun moyen évident d'effectuer la concaténation.

Mais heureusement, il contient l'étoile. Cela nous permet d’écrire *b, ce qui correspond à la chaîne "*main::b". Puis, *b^<^B[MMH^V^SY>(^ B, ^ V et ^ S sont des caractères de contrôle littéral) nous donne (6, $&);, qui, une fois encore eval-ed, renvoie la valeur de la variable de correspondance de Perl, $&. Cela nous permet d'utiliser une forme limitée de concaténation: nous pouvons à plusieurs reprises ajouter des éléments à $_utiliser s<^><THINGS>e, puis utiliser s<\H*><*b^<^B[MMH^V^SY>>eeepour évaluer $_( \Hcorrespond à tout sauf aux espaces horizontaux; nous l'utilisons à la place du point, qui n'est pas dans notre jeu de caractères).

En utilisant 9-/, nous pouvons facilement générer tous les chiffres. En utilisant les chiffres, vet la concaténation, nous pouvons générer des caractères arbitraires (vXXX donne le caractère avec le code ASCII XXX). Et nous pouvons concaténer ces éléments afin de générer des chaînes arbitraires. On dirait que nous pouvons faire n'importe quoi.

Écrivons un exemple complet. Supposons que nous voulions un programme qui imprime son propre PID. Nous commençons avec le programme naturel:

say$$

Nous le convertissons en notation V:

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

Nous réécrivons ceci en utilisant uniquement ^B^V^S(*-/9;<>HJMOY[`\^begqstv(les espaces sont uniquement pour la lisibilité et n’affectent pas la sortie):

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;

Enfin, nous convertissons le programme ci-dessus en only <>^es: pastebin . Malheureusement, cela bloque Perl Excessively long <> operator, mais ce n’est qu’une limitation technique et ne doit pas être pris en compte.

Ouf, c'était tout le voyage. Ce serait vraiment intéressant de voir quelqu'un proposer un jeu de 5 caractères qui simplifie les choses.

EDIT: en utilisant une approche légèrement différente, nous pouvons éviter de frapper la limite de longueur <>. Interprète brainfuck entièrement fonctionnel utilisant seulement <>^es: Essayez-le en ligne! . Perl automatisé vers <>^estranspiler: pastebin .

Python 2, 7 caractères

exc="%\n

Tout programme Python 2 peut être encodé en utilisant ces 7 caractères ( \nest une nouvelle ligne).

Construire des chaînes arbitraires

Nous pouvons effectuer la concaténation en appliquant de manière répétée l'opérateur de substitution %sur une seule chaîne. Par exemple, si a=1, b=2, c=3, "%d%%d%%%%d" % a % b % cnous donnera la chaîne "123". Heureusement, les lettres execnous donnent accès à %xet %cqui sont fondamentalement hex()et chr(). Avec %c, nous pouvons construire n'importe quelle chaîne tant que nous avons les nombres nécessaires pour représenter les caractères. Nous pouvons ensuite exécuter cette chaîne en tant que code python en utilisant le execmot - clé.

Faire des nombres

Nous pouvons avoir accès à 0et 1dès le départ avec des comparaisons ( ==). En combinant les chiffres concaténés et modulo, il est possible de construire le nombre 43qui représente +en ASCII. Cela nous permet de construire les nombres dont nous avons besoin pour notre code.

Mettre ensemble

J'ai omis plusieurs détails dans cette explication car ils ne sont pas essentiels pour comprendre comment les programmes soumis à ces contraintes peuvent être écrits. Voici un programme Python 2 que j’ai écrit et qui convertit n’importe quel programme python en une version fonctionnellement équivalente qui n’utilise que ces 7 caractères. Les techniques utilisées s'inspirent de cette soumission sur l'anarchie golf par k. Quelques astuces simples sont également utilisées pour maintenir la taille des programmes générés dans des limites raisonnables.

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

Essayez-le en ligne

Mathematica, 5 à 4 caractères

I[]

est un caractère Unicode à usage privé , qui agit en tant qu'opérateur pour vous Functionpermettre d'écrire des littéraux pour des fonctions non nommées avec des arguments nommés. Le caractère ressemble beaucoup ↦à Mathematica, je vais donc l'utiliser pour le reste de la réponse pour plus de clarté.

L' utilisation de ces, nous pouvons mettre en œuvre le S, Ket Icombinateurs de la logique combinatoire:

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

Un problème syntaxique avec ceux-ci est que la ↦priorité est très faible, ce qui posera un problème si nous essayons de passer des arguments à ces combinateurs. Vous devriez normalement résoudre ce problème en plaçant un combinateur Centre parenthèses (C), mais nous n'avons pas de parenthèses. Cependant, nous pouvons utiliser Iet []encapsuler Cune autre magie qui a suffisamment de préséance pour pouvoir l'utiliser ultérieurement:

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

Enfin, pour écrire une application A x y z(où Aest un combinateur « parenthesised » comme indiqué ci - dessus, et x, y, zpeuvent ou non être parenthesised, ou peut - être plus grandes expressions), nous pouvons écrire:

A[x][y][z]

Cela laisse la question de savoir comment l’équivalent parenthèse fonctionne réellement. Je vais essayer de l'expliquer en gros dans l'ordre dans lequel je l'ai trouvé.

Donc, ce que nous avons syntaxiquement pour grouper quelque chose, ce sont les crochets []. Les crochets apparaissent de deux manières dans Mathematica. Soit en tant qu'invocations de fonction f[x], soit en tant qu'opérateur d'indexation f[[i]](ce qui est vraiment juste un raccourci pour Part[f, i]). En particulier, cela signifie que ni la syntaxe [C]ni [[C]]valide sont. Nous avons besoin de quelque chose devant. Cela peut théoriquement être n'importe quoi. Si nous utilisons le que Inous avons déjà, nous pouvons obtenir I[C]par exemple. Cela reste non évalué, car ce In'est pas une fonction unaire (ce n'est pas une fonction du tout).

Mais maintenant, nous avons besoin d’un moyen d’extraire à Cnouveau, car sinon, cela ne sera pas réellement évalué lorsque nous essaierons de lui passer un argument x.

C’est là qu’il est pratique de f[[i]]pouvoir utiliser des expressions arbitraires f, pas seulement des listes. En supposant que flui - même est de la forme head[val1,...,valn], puis f[[0]]donne head, f[[1]]donne val1, f[[-1]]donne valnet ainsi de suite. Nous avons donc besoin d’obtenir l’un 1ou -1de les extraire à Cnouveau, car l’un I[C][[1]]ou l’ I[C][[-1]]évalue C.

Nous pouvons obtenir 1un symbole arbitraire non défini comme x, mais pour ce faire, nous aurions besoin d'un autre caractère pour la division ( x/xdonne 1pour non défini x). La multiplication est la seule opération arithmétique que nous puissions effectuer sans aucun caractère supplémentaire (en principe). Nous avons donc besoin d’une valeur pouvant être multipliée pour donner -1ou 1. Cela finit par être la raison pour laquelle j'ai spécifiquement choisi Inos identifiants. Parce que Ipar lui-même est le symbole intégré de Mathematica pour l'unité imaginaire.

Mais cela laisse un dernier problème: comment pouvons-nous réellement multiplier Ipar lui - même? Nous ne pouvons pas simplement écrire IIparce que cela est analysé comme un symbole unique. Nous devons séparer ces jetons sans a) changer leur valeur et b) en utilisant de nouveaux caractères.

Le dernier élément magique est un élément de comportement non documenté: f[[]](ou de manière équivalente Part[f]) est une syntaxe valide et se retourne f. Donc, au lieu de multiplier Ipar I, nous multiplions I[[]]par I. Lorsque vous insérez des crochets, Mathematica recherche ensuite un nouveau jeton et I[[]]Iévalue -1si nécessaire. Et c'est comme ça qu'on se retrouve I[C][[I[[]]I]].

Notez que nous ne pouvions pas utiliser I[]. Il s'agit d'une invocation sans argument de la fonction I, mais comme je l'ai dit précédemment In'est pas une fonction, elle ne sera donc pas évaluée.

Python 2, 8 caractères

exc'%~-0

Ces caractères permettent la traduction / exécution de n’importe quel programme Python en utilisant des chaînes de format et exec. Bien que la capacité de traduire un programme ne soit pas nécessaire à la complétude de Turing, c'est le moins de personnages que je connaisse qui en font de toute façon TC. Que ce soit si puissant n'est qu'un bonus.

Un guillemet double ainsi que tout chiffre autre que zéro pourraient également être utilisés. (Maintenant que je pense, 1serait certainement mieux, ce qui dans les programmes plus courts, puisque vous pouvez utiliser 1, 11et 111, aussi bien.)

Voici le programme print:

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

Essayez-le en ligne

Le programme de base nécessite

exec''

Chaque caractère xajouté au programme nécessite (nombre de caractères):

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

L'exception à cette règle est que certaines optimisations / raccourcis peuvent être utilisés %'0'pour raccourcir le programme codé, par exemple utiliser le caractère 0au lieu de 48 -~, etc.

Utilisations pratiques (AKA golfing): J'ai utilisé cette tactique pour résoudre ce défi sans utiliser de handicap supplémentaire.

Crédit pour la liste de caractères et un programme de codeur: ici

Pour plus d'informations sur la recherche d'une limite inférieure sur la taille du programme résultant (sans optimisations), consultez ce commentaire .

Le nombre d'octets requis augmente O(2**n), cette méthode n'est donc pas recommandée pour le golf. Un quine utilisant cette restriction de source serait incroyablement long.

C (unportable), 24 18 13 caractères

aimn[]={};,1+

Cela couvre tous les programmes de la forme

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

... où la séquence de constantes (de la forme 1 + 1 + 1 ...) contient la représentation du code machine de votre programme. Cela suppose que votre environnement autorise l'exécution de tous les segments de mémoire (apparemment vrai pour tcc [merci @Dennis!] Et pour certaines machines sans bit NX). Sinon, pour Linux et OSX, vous devrez peut-être ajouter le mot clé à la fin constet pour Windows, vous devrez peut-être ajouter #pragmaexplicitement le segment comme exécutable.

À titre d'exemple, le programme suivant écrit dans le style ci-dessus s'imprime Hello, World!sous Linux et OSX sous x86 et 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};

Essayez-le en ligne!

Retina , 6 personnages

$%`{¶

Ainsi que des sauts de ligne (0x0A).

D'un côté, je suis surpris de pouvoir l'avoir aussi bas. D'autre part, je suis très mécontent de l'inclusion de %¶. Chacune des $`{est réutilisée pour deux voire trois buts, mais %¶ ensemble ne servent qu’un seul but. Cela les rend plutôt inutiles et détruit légèrement l’élégance de la démarche. J'espère qu'il y a un moyen de battre cette construction.

Sur la preuve. Je vais décrire un moyen simple de traduire les systèmes de balises cycliques en rétine à l'aide des caractères ci-dessus.

Tout d'abord, nous utiliserons `et {pour l'alphabet binaire au lieu de 0et 1. Celles-ci sont pratiques, car elles n'ont pas besoin d'être échappées dans une expression rationnelle, mais elles ont une signification pour Retina ou dans la syntaxe de substitution. J'utilise `pour 0et {pour 1, mais ce choix est arbitraire. De plus, nous allons inverser la chaîne (et les productions) en mémoire, parce que travailler avec le dernier caractère nous permet d' utiliser $et au $`lieu de ^et $', en maximisant la réutilisation des caractères.

Si le mot initial est noté Set que la production ith (inversée) est appelée , le programme résultant ressemblera à ceci:pi

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Cette construction grandit inévitablement en mémoire chaque fois qu'une production est appliquée, et il est peu probable qu'elle se termine - en fait, au moment où le système de balises cycliques prendrait fin (lorsque la chaîne de travail devient vide), le comportement du programme Retina résultant devient fondamentalement indéfini.

Regardons ce que le programme fait:

S

Nous commençons par initialiser la chaîne de travail au mot initial.

{`

Cela enveloppe le reste du programme dans un programme qui s'exécute jusqu'à ce qu'il ne parvienne pas à changer la chaîne résultante (hé, détection naïve de la boucle infinie intégrée gratuite ...). Les deux sauts de ligne ne sont pas vraiment nécessaires, mais ils séparent plus clairement la boucle des productions individuelles. Le reste du programme passe en revue chacune des productions et, en raison de la boucle, nous les traitons effectivement de manière cyclique, encore et encore.

Chaque production est traitée en deux étapes. Nous traitons d’abord le cas où le symbole principal (ou, dans notre cas, le dernier symbole) est {, auquel cas nous utilisons la production:

{$
¶pi$%``

La regex ne correspond que si la chaîne se termine par {. Si tel est le cas, nous le remplaçons par:

• Un saut de ligne ( ¶). Nous ne travaillerons jamais qu'avec la dernière ligne de la chaîne de travail, de sorte que la chaîne de travail est jusqu'à présent ignorée (c'est pourquoi l'utilisation de la mémoire du programme augmentera de plus en plus).
• La production actuelle ( ), que nous ajoutons ici à la chaîne de travail (à laquelle le système de balises cycliques l'ajoute).pi
• La dernière chaîne de travail restante ( $%`). C'est pourquoi nous devons insérer le ¶: $%`ramasse tout ce qui reste du match, mais uniquement sur la même ligne. Par conséquent, cela ne voit pas tous les déchets que nous avons laissés par les productions précédentes. Cette astuce nous permet de faire correspondre quelque chose à la fin de la chaîne de travail pour insérer quelque chose au début de la chaîne de travail, sans avoir à utiliser quelque chose du genre (.+)et $1qui aurait pour effet d'augmenter considérablement le nombre de caractères dont nous avons besoin.
• Un simple coup de gueule ( `). Cela remplace efficacement le {( 1-symbol) que nous avons associé à un `( 0-symbol), de sorte que l'étape suivante n'a pas besoin de savoir si nous avons déjà traité la production en cours ou non.

La deuxième partie de chaque production est alors le cas trivial où la production est ignorée:

``$

Nous supprimons simplement une fin `. La raison pour laquelle nous avons besoin de deux `sur la première ligne est que Retina considère que le premier backtick est le séparateur entre configuration et regex. Cela lui donne simplement une configuration vide afin que nous puissions utiliser des backticks dans la regex elle-même.

Java 7, 18 17 caractères

\bcdefu0123456789

Tout le code source Java peut être réduit à des points de code Unicode. "a" n'est pas nécessaire car il n'est utilisé que pour *:jJzZ. L'astérisque est utilisé pour la multiplication ou le blocage de commentaires. La multiplication est simplement une addition répétée et vous pouvez utiliser des commentaires sur une seule ligne (ou simplement les omettre). Les deux points sont utilisés pour les opérateurs ternaires, pour lesquels vous pouvez utiliser une instruction if, et pour les boucles foreach, qui peuvent être remplacés par des boucles normales pour. j et z ne font partie d'aucun mot clé en java.

Pour supprimer tout autre caractère, nous devons ajouter au moins un des caractères requis dans la plaque de la chaudière Java class a{public static void main(String[]a){}}. Voir ci-dessous:

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

Voici un exemple avec un programme Hello World Essayez-le en ligne!

Java 8, 16 caractères

\bdefu0123456789

Merci à ais523 de l'avoir signalé. Java 8 permet aux interfaces d'avoir des méthodes statiques, ce qui signifie que nous pouvons supprimer "c" car nous n'en avons pas besoin pour le "l" dans "class". "c" étant utilisé ,<lL\|, nous finissons par perdre un peu plus de fonctionnalités java que lorsque nous avons supprimé "a", mais nous en avons encore suffisamment pour être complets. Essayez-le en ligne!

Labyrinthe , 5 personnages

~{}

Plus sauts de ligne (0x0A) et espaces (0x20).

Je vais esquisser une preuve sous la forme d'une réduction de Smallfuck (une variante de Brainfuck réduite utilisant des cellules à 1 bit). Notez que Smallfuck lui-même n’est pas Turing-complete car le langage spécifie que sa bande doit être finie, mais nous allons supposer une variante de Smallfuck avec une bande infinie, qui serait alors Turing-complete (Labyrinth n’a pas de mémoire). restrictions par conception).

Un invariant important tout au long de cette réduction sera que chaque programme (ou sous-programme) donnera un programme (ou sous-programme) Labyrinth qui commence et se termine sur la même ligne et couvre un nombre pair de colonnes.

Labyrinth a deux piles qui sont initialement remplies d'une quantité infinie (implicite) de 0s. {et }décaler la valeur supérieure entre ces piles. Si nous considérons que le haut de la pile principale est la "cellule" actuelle, ces deux piles peuvent alors être considérées comme les deux moitiés semi-infinies de la bande infinie utilisée par Smallfuck. Cependant, il sera plus pratique d’avoir deux copies de chaque valeur de bande sur les piles, pour garantir l’invariant mentionné ci-dessus. Par conséquent <, >ils seront traduits en {{et }}, respectivement (vous pouvez les échanger si vous le souhaitez).

Au lieu de permettre les valeurs de cellule 0et 1, nous utilisons 0et -1, avec lesquels nous pouvons basculer entre ~(négation au niveau du bit). Les valeurs exactes n’ont aucune importance pour la complétude de Turing. Nous devons changer les deux copies de la valeur sur la pile, ce qui nous donne à nouveau une traduction de longueur égale: *devient ~}~{.

Cela laisse les commandes de flux de contrôle []. Labyrinth n'a pas de flux de contrôle explicite, mais le flux de contrôle est déterminé par la structure du code. Nous avons besoin des espaces et des sauts de ligne pour faire cette mise en page.

Tout d’abord, notez que ~~c’est un non-op, car les deux ~annulent effectivement. Nous pouvons utiliser cela pour avoir des chemins arbitrairement longs dans le code, tant que leur longueur est paire. Nous pouvons maintenant utiliser la construction suivante pour traduire AA[BB]CCLabyrinth (j'utilise des lettres doubles pour que la taille de chaque extrait de Labyrinth soit égale, comme le garantit l'invariant):

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

Ici, ..est un nombre approprié ~qui correspond à la largeur de BB.

Encore une fois, notez que la largeur de la construction reste égale.

Nous pouvons maintenant passer en revue le fonctionnement de cette boucle. Le code est entré via le AA. Le premier ~~ne fait rien et nous permet d'atteindre la jonction. Cela correspond à peu près au [:

• Si la valeur de la cellule actuelle est zéro, l'IP continue tout droit, ce qui finira par sauter BB. La ..partie est toujours un no-op. Ensuite, nous en atteignons un ~à un autre croisement. Nous savons maintenant que la valeur actuelle est non nulle et que l'IP prend alors le virage nord. Il fait le tour en haut, jusqu’à atteindre un autre croisement après six heures ~. Donc, à ce stade, la valeur actuelle est toujours non nulle et l’IP reprend son virage pour aller vers l’est en direction de la CC. Notez que les trois ~précédant le CCretour à la valeur actuelle 0, comme il se doit lorsque la boucle a été ignorée.
• Si la valeur actuelle de la cellule au début de la boucle est non nulle, l’IP prend la direction sud. Il en exécute six autres ~avant d’atteindre BB(ce qui ne fait rien), puis six autres ~avant d’atteindre la prochaine intersection. Cela correspond à peu près au ].
  • Si la cellule en cours est zéro, l'IP continue de se déplacer vers le nord. La ~valeur suivante rend la valeur non nulle, de sorte que l'adresse IP utilise cette deuxième jonction, qui fusionne le chemin avec le cas où la boucle a été ignorée complètement. De nouveau, les trois ~renvoient la valeur à zéro avant d’atteindre CC.
  • Si la cellule en cours est non nulle, l’IP prend le virage ouest. Il y en a ~avant la prochaine jonction, ce qui signifie qu'à ce stade, la valeur actuelle est égale à zéro, de sorte que l'adresse IP continue à aller vers l'ouest. Ensuite, il y aura un nombre impair ~avant que l'IP n'atteigne à nouveau la jonction initiale, de sorte que la valeur soit renvoyée -1et que l'IP se déplace vers le sud à la prochaine itération.

Si le programme contient des boucles, la toute première AAdoit être étendue en haut du programme pour que l'IP trouve la bonne cellule sur laquelle démarrer:

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

C'est ça. Notez que les programmes résultant de cette réduction ne se termineront jamais, mais cela ne fait pas partie des exigences de la complétude de Turing (considérez la règle 101 ou Fractran).

Enfin, il reste la question de savoir si cela est optimal. En termes de charge de travail, je doute qu'il soit possible de faire mieux que trois commandes. Je pouvais voir une construction alternative basée sur des machines Minsky avec deux registres, mais cela nécessiterait =()ou =-~, ne disposant que d’une commande de manipulation de pile mais de deux commandes arithmétiques. Je serais heureux de me tromper à ce sujet. :)

En ce qui concerne les commandes de présentation, je pense que les sauts de ligne sont nécessaires, car un contrôle utile est impossible sur une seule ligne. Cependant, les espaces ne sont pas techniquement nécessaires. En théorie, il pourrait être possible de concevoir une construction qui remplisse toute la grille avec ~{}(ou =()ou =-~), ou utilise une disposition irrégulière où les lignes ne sont pas toutes de la même longueur. Cependant, écrire un code comme celui-là est incroyablement difficile, car Labyrinth traitera alors chaque cellule comme une jonction et vous devez faire très attention à ce que le code ne se ramifie pas lorsque vous ne le souhaitez pas. Si quelqu'un peut prouver ou réfuter s'il est possible d'omettre l'espace pour que Turing soit complet, je serais heureux de donner une prime substantielle pour cela. :)

Haskell, 5 7 caractères

()\->=;

En tant que langage fonctionnel, Haskell a bien sûr des lambdas, il est donc facile de simuler le calcul lambda. La syntaxe pour lambdas est la suivante: nous avons au moins besoin des caractères . De plus, nous avons besoin d'un nombre illimité de symboles variables pour pouvoir construire des expressions lambda arbitraires. Heureusement , on n'a pas besoin de nouveaux personnages pour cela, parce que , , , ..., sont tous les noms de variables valides. En fait, chaque combinaison de parenthèses à l'intérieur est un nom de variable valide, à l'exception de just et , qui sont réservés aux expressions lambda, et qui commencent un commentaire de ligne.(\variable->body)argument()\->
(>)(>>)(>>>)\->\->--

Exemples:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))types à(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))types àt -> t1 -> t
• I = (\(>)->(>))types àt -> t

Edit: Cependant, comme l' a fait remarquer ais523 dans les commentaires, cette construction implémente le calcul lambda typé , qui en soi n'est pas complet, car il manque la capacité d'entrer dans des boucles infinies. Pour résoudre ce problème, nous avons besoin d’une fonction qui effectue la récursivité. Jusqu'ici, nous avons utilisé des lambdas anonymes, qui ne peuvent pas s'appeler eux-mêmes, car ils n'ont pas de nom. Il faut donc ajouter les personnages =et ;implémenter une fixfonction:

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

Avec cette déclaration, notre calcul lambda devient complet, bien que nous ayons ajouté =et ;, nous n’avons plus besoin de lambdas, comme vous pouvez le constater dans la réponse de nimi qui utilise justement ()=;.

CJam, 3 personnages

Supprimé )selon la suggestion de Martin Ender

'(~

Semblable à celui de Python donné à titre d'exemple.

En utilisant '~vous pouvez obtenir le ~personnage. Ensuite, en utilisant (, vous pouvez le décrémenter pour obtenir le caractère de votre choix ( ~le dernier caractère ASCII imprimable). ~évalue n'importe quelle chaîne en tant que code CJam normal. Les chaînes peuvent être construites en obtenant le caractère [(par décrémentation ~), en l’évaluant, en insérant une séquence d’autres caractères, puis en évaluant le caractère ]. Grâce à cela, vous pouvez créer et exécuter n’importe quel programme CJam en utilisant uniquement ces trois caractères.

Calculer 2 + 2 en utilisant seulement '(~

Brain-Flak , 6 personnages

(){}[]

Brain-Flak est un langage minimaliste avec seulement 8 caractères disponibles. Cependant, il peut être prouvé qu’il existe un sous-ensemble de Brain-Flak qui est également complet en utilisant seulement 6 caractères.

La première chose à faire est de mettre en œuvre une machine Minsky avec une seule pile de Brain-Flak. Si nous pouvons prouver qu'une machine Minsky est possible avec une seule pile, nous pouvons montrer que Brain-Flak est complète sans les <>ni plus []ni moins. Cela ne sauvegardera aucun personnage immédiatement, mais le sera ultérieurement lorsque nous montrerons que ce <...>n'est pas nécessaire.

Une machine de Minsky est un type d'automate complet de Turing qui a un nombre fini de registres non bornés et deux instructions:

• Incrémenter le registre

• Si la valeur est différente de zéro, sinon, transition vers une instruction spécifiée

Pour configurer une structure de goto dans Brain-Flak, nous pouvons utiliser l'extrait suivant:

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

Cela va décrémenter le compteur et courir %ssi zéro. Un tas de ces chaînes nous permettra de mettre un numéro sur la pile qui indiquera quelle ligne nous voulons aller. Chacune d'elles décrémentera le haut de la pile, mais un seul exécutera le code.

Nous l'utilisons comme enveloppe pour toutes nos instructions Minsky Machine.

Incrémenter un registre particulier est assez facile sans changer de pile. Cela peut être réalisé avec cette formule de chaîne:

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

Par exemple, pour incrémenter le 3ème registre, nous écririons le code suivant:

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

Il ne nous reste plus qu'à mettre en œuvre la deuxième opération. Vérifier si un nombre est égal à zéro est assez simple dans Brain-Flak:

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

ne s’exécutera que %ssi le TOS est nul. Ainsi, nous pouvons faire notre deuxième opération.

Puisque les machines Minsky sont complètes de Turing, Brain-Flak est également complet de Turing sans utiliser les opérations <>and [].

Cependant , nous n'avons pas réduit encore le nombre de caractères car <...>et [...]sont encore en cours d' utilisation. On peut remédier à cela avec une simple substitution. Depuis <...>est réellement équivalent à [(...)]{}dans tous les cas. Ainsi, Brain-Flak est complet sans l'utilisation des caractères <et >(plus tous les no-ops).

> <> , 3 caractères

> <> est faisable en 3 avec 1p-, qui:

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

pfournit une réflexion en modifiant le code source 2D en plaçant des caractères dans la boîte à code. Avec 1-, vous pouvez placer n'importe quel nombre dans la pile puisque 1-soustrait un et 111-1--( x-(1-1-1) = x+1) en ajoute un.

Une fois que toutes les 1p-commandes ont été exécutées, le pointeur d’instruction s’enroule, lui permettant d’exécuter le code "réel".

Un exemple de programme qui calcule les nombres de Fibonacci (à partir de cette réponse ) est:

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

Essayez-le en ligne! Une fois que toutes les 1p-commandes ont été exécutées, la boîte à code se présente comme suit:

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

Sauf tout après la vpremière ligne, il s'agit d'un programme Fibonacci> <> standard.

bash, 9 caractères

01456\$ '

Bash a une syntaxe $'\nnn'pour la saisie de caractères avec leurs valeurs ascii octales. Nous pouvons entrer la evalcommande dans ce format en tant que $'\145\166\141\154'. Nous transformons d'abord le résultat souhaité en ses valeurs octales. Nous convertissons ensuite les valeurs octales en utilisant des chiffres autres que 0, 1, 4, 5 et 6 en expressions évaluant lesdites valeurs octales en utilisant une $(())soustraction, en ajoutant un evalavant. Dans notre dernière étape, nous en ajoutons un autre evalet convertissons les parenthèses et le signe moins en leurs valeurs octales. En utilisant cette méthode, nous pouvons exécuter n’importe quelle commande bash, ce sous-ensemble est donc complet.

Exemple:

dc devient

$'\144\143' qui devient

$'\145\166\141\154' \$\'\\144\\$((144-1))\' qui devient

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

Incident , 2 personnages

Peu importe les deux personnages que vous choisissez. toute combinaison de deux octets est Turing-complete dans Incident.

En fait , prouver ce qui est beaucoup plus difficile que vous pourriez vous attendre, et au moment de l' écriture, la page de discussion sur Esolang à propos de l' incident est consacré au problème. Je vais cependant essayer de résumer la preuve connue la plus simple ci-dessous.

Avant la preuve, un peu de fond. L'incident déduit les jetons utilisés dans le programme en examinant le source (un jeton est une chaîne qui apparaît exactement trois fois dans le source, n'est pas la sous-chaîne d'un autre jeton et ne chevauche pas un autre jeton potentiel). En tant que tel, n'importe quel programme peut être converti pour utiliser à peu près n'importe quel jeu de caractères en modifiant ce que sont les jetons; le langage est complet (et complet aussi pour les E / S!), bien qu’il soit incroyablement difficile à programmer, alors "tout" dont vous avez besoin est une méthode d’encodage des jetons pour qu’ils ne fonctionnent qu'avec deux caractères.

Et maintenant, voici un résumé de la preuve (qui a été trouvée par Ørjan, le mathématicien résident d'Esolang). L'idée est de coder un jeton en utilisant deux copies d'un caractère (par exemple 1) dans une grande mer d'un autre caractère (par exemple 0). La distance entre le 1s est différent pour chaque jeton, mais est toujours un multiple de 4. Ensuite , pour le rembourrage entre les jetons, nous utilisons une liste supplémentaire de 0s avec 1au milieu, mais le nombre de 0s de chaque côté du 1est pas un multiple de 4, mais plutôt un nombre unique à cette incidence particulière du programme qui ne figure pas ailleurs dans le programme. Cela signifie que chacun 1…1dans le remplissage ne peut apparaître que deux fois, alors ne fera pas partie d'un jeton; chaque jeton destiné contient exactement deux 1 et aucun jeton factice ne peut en contenir plus d'un 1. Ensuite, nous ajoutons simplement du rembourrage sur le côté pour supprimer tous les jetons possibles contenant un 1ou zéro 1s en en ajoutant au moins quatre copies.

Retina , 3 personnages

{`

et newline.

Tout d’abord, nous avons besoin de newline pour pouvoir effectuer des substitutions (nécessaire à moins que nous ne voulions inclure tout le programme dans une regex, ce qui nécessiterait plus de caractères); et `et {sont le moyen le moins intensif en caractères de faire des boucles. Il s'avère que nous n'avons besoin de rien d'autre.

Notre langue cible à implémenter est une variante déterministe de Thue (le non déterminisme n'est pas nécessaire pour la complétude de Turing; il est possible d'écrire un programme Thue pour qu'il fonctionne correctement quel que soit l'ordre d'évaluation utilisé). L’idée de base est de compiler pattern::=replacementen

`pattern
replacement

(qui est une traduction directe du Thue par la rétine; alternativement, si vous connaissez la rétine mais pas le Thue, vous pouvez l’utiliser comme méthode d’apprentissage du fonctionnement de Thue); exceptionnellement, le tout premier motif est précédé de {`(afin de placer le programme entier dans une boucle; les programmes Thue continuent de s'exécuter jusqu'à ce qu'il n'y ait plus de substitutions possibles, ce qui entraîne le fonctionnement identique de la rétine).

Bien sûr, cela signifie que nous devons prouver que Thue Turing est complet avec juste {et `dans les modèles et le remplacement, mais c'est assez simple; nous remplaçons un caractère par le code ascii n avec `, n +1 {, et un autre `. Il est clairement impossible pour un motif de correspondre n'importe où, sauf aux limites du personnage. Cela finira donc par faire la même chose que le programme d'origine.

Brachylog , 5 personnages

~×₁↰|

Ce sous-ensemble de caractères nous permet d'implémenter une version de Fractran dans laquelle les seuls nombres pouvant apparaître sont les produits de repunits (c'est-à-dire les produits de nombres pouvant être écrits en décimal à l'aide du chiffre 1 uniquement). ~×(avec un entier en indice) divise la valeur actuelle par cet entier, mais uniquement si elle est divisée exactement (sinon, elle "échoue" et recherche un autre cas à exécuter; |sépare les cas). ×nous permet de multiplier par un entier. Donc, en utilisant ~×₁|nous pouvons implémenter une étape d’une exécution Fractran. Ensuite , ↰nous permet RECURSE, l' exécution du programme tout à nouveau sur la nouvelle valeur actuelle. Voici un exemple de programme Fractran très simple ( 11111111111111111111111/111) traduit en Brachylog.

Alors, est-ce que Turing est complet? Tout ce dont nous avons besoin pour que Fractran Turing soit complet est une quantité suffisamment grande de nombres premiers (assez pour écrire un interprète pour une langue complète de Turing dans Fractran même). Il y a cinq preuves et quatre soupçonnésrepunit prime, en plus, peut-être, de ceux qui n’ont pas encore été découverts. C'est en fait plus que ce dont nous avons besoin dans ce cas. Le programme vérifie les possibilités de gauche à droite, nous pouvons donc utiliser un nombre premier comme pointeur d’instruction et deux autres comme compteurs, démontrant ainsi la complétude de Turing avec seulement trois nombres premiers (une bonne chose aussi, car cela nous permet d’utiliser les repunits avec 2, 19 , et 23 chiffres, sans avoir à recourir aux répétitions éprouvées mais ennuyeuses de 317 ou 1031 chiffres, ce qui rendrait le code source assez difficile à écrire). Cela permet d'implémenter une machine Minsky avec deux compteurs (assez pour la complétude de Turing).

Voici comment la compilation fonctionne spécifiquement. Nous utiliserons les deux commandes suivantes pour notre implémentation de machine Minsky (connue sous le nom de Turing complete), et chaque commande aura un entier comme étiquette:

• Label L: Si le compteur {A ou B} vaut zéro, passez à X. Sinon, décrémentez-le et passez à Y.
• Libellé L: Compteur d'incrémentation {A ou B}, puis passez à Z.

Nous choisissons la commande à exécuter en plaçant des puissances de 11 au dénominateur, les plus hautes puissances en premier; l'exposant de 11 est l'étiquette de la commande. De cette façon, la première fraction qui correspond sera la commande en cours d’exécution (car les précédentes ne peuvent pas se diviser par tous ces 11). Dans le cas d'une commande de décrémentation, nous plaçons également un facteur de 1111111111111111111 ou 1111111111111111111111111 dans le dénominateur, pour le compteur A ou B respectivement, et nous le suivons avec une autre commande sans ce facteur; le cas "décrément" sera implémenté par la première commande, le cas "zéro" par la seconde. Pendant ce temps, le "goto" sera traité avec une puissance appropriée de 11 au numérateur et un "incrément" via un facteur de 1111111111111111111 ou 11111111111111111111111 au numérateur.

Befunge-98, 3 caractères

Pour autant que je sache, Befunge-98 est supposé être complet, nous devons donc montrer comment tout programme Befunge-98 peut être généré en utilisant seulement trois caractères. Ma solution initiale reposait sur les quatre caractères suivants:

01+p

Nous pouvons obtenir n'importe quel entier positif sur la pile en ajoutant plusieurs 1valeurs avec la +commande, et pour zéro, nous utilisons simplement 0. Une fois que nous avons la capacité de composer le nombre que nous voulons, nous pouvons utiliser lep commande (put) pour écrire toute valeur ASCII à n’importe quel emplacement du champ de jeu Befunge.

Cependant, comme l' a souligné Sp3000 , vous ne pouvez vous débrouiller qu'avec ces trois caractères:

1-p

Tout nombre négatif peut être calculé en commençant par 1puis en soustrayant plusieurs fois 1(par exemple, -3 serait 11-1-1-1-). Ensuite, tout nombre positif peut être représenté en soustrayant 1-n de 1, où 1-n est un nombre négatif que nous savons déjà manipuler (par exemple, 4 = 1 - (- 3), ce qui serait111-1-1-1-- ).

Nous pouvons donc utiliser nos trois caractères pour écrire un type de chargeur de démarrage qui génère lentement le code que nous voulons exécuter. Une fois que ce chargeur est terminé, il se termine au début de la première ligne du champ de jeu, qui devrait alors contenir le début de notre code nouvellement généré.

À titre d'exemple, voici un chargeur de démarrage qui génère le code Befunge nécessaire pour additionner 2 + 2 et générer le résultat: 22+.@

Et pour un exemple un peu plus compliqué, voici "Hello World": "!dlroW olleH"bk,@

Ruby, 8 caractères

eval"<1+

Inspiré par les réponses Python

Comment ça fonctionne

• eval peut être utilisé pour exécuter une chaîne arbitraire.
• "<1+ est l'ensemble minimal de caractères requis pour construire une chaîne

Une chaîne en ruby ​​peut être construite en utilisant la chaîne vide comme point de départ et en y ajoutant des caractères ascii, par exemple:

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

est en fait équivalent à

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

qui évalue la chaîne

p"o"

OCaml, 9 caractères

fun->()`X

Ces caractères suffisent pour implémenter le calcul SKI Combinator dans OCaml. Nous pouvons notamment éviter l’utilisation d’espace avec des parenthèses suffisantes. Malheureusement, les expressions lambda dans OCaml nécessitent lafun mot clé. Une solution plus concise n’est donc pas possible. Les mêmes lettres peuvent être utilisées pour créer des noms de variables arbitraires si des expressions lambda plus complexes sont souhaitées.

S combinateur:

fun(f)(u)(n)->f(n)(u(n)) avec le type ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Combinator:

fun(f)(u)->u avec le type 'a -> 'b -> 'b

Je Combinator:

fun(f)->f avec le type 'a -> 'a

Comme indiqué par ais523, il ne suffit pas de coder simplement SKI. Voici un codage pour Z utilisant des variantes polymorphes pour manipuler le système de types. Avec cela, mon sous-ensemble devrait être complet.

Z Combinator:

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

avec le type (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Langages concaténatifs basés sur la pile, 4 caractères

Sous-charge

():^

GolfScript

{}.~

CJam

{}_~

GS2

• backspace, tab, @space (je savais que GS2 utilisait beaucoup d'imprimables, mais c'est ridicule…)

dc (suggéré par @seshoumara)

[]dx

La sous-charge a été prouvée Turing-complete avec seulement l'utilisation de ():^(grâce au mathématicien résident d'Esolang Ørjan). La preuve est beaucoup trop longue à expliquer ici, mais si cela vous intéresse, vous pouvez lire à ce sujet ici .

Les commandes en question sont ()(placez le littéral de code sur la pile), :(élément dupliqué de la pile supérieure) et ^(évaluez le sommet de la pile). Ces commandes sont assez courantes dans les langages basés sur des piles (en particulier les langages concaténatifs), aussi en ai-je donné ci-dessus une collection; ces langues sont toutes Turing-complete en 4 caractères pour la même raison que Underload.

Espaces blancs, 3 caractères

STL

Sis space, Tis tab et Lnewline.

Raquette (Scheme), 4 personnages

(λ)

En utilisant uniquement λ, parenthèse et espace, nous pouvons directement programmer dans le sous-ensemble Lambda Calculus de Scheme. Nous réutilisons le caractère λ pour tous les identificateurs en les concaténant ensemble pour fournir un nombre arbitrairement grand d'identificateurs uniques.

À titre d'exemple, voici le combinateur classique Omega, qui boucle en boucle pour toujours.

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

Python 3, 9 caractères

exc('%1+)

Voir ma réponse à Python 2 pour une explication de base. Cette réponse s'appuie sur celle-là.

Au lieu d'utiliser simplement les mêmes caractères que Python deux avec l'ajout de (), nous pouvons supprimer un caractère puisque nous utilisons maintenant des parenthèses. Les programmes auront toujours la forme de base de

exec('%c'%stuff)

mais nous raccourcissons la durée du programme en utilisant à la +place de -, puis nous pouvons supprimer ~en utilisant à la 1place de 0. Nous pouvons ajouter 1, 11et 111pour obtenir les valeurs ASCII nécessaires.

Le programme print()devient le suivant le plus court possible:

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)%'('%')')

Essayez-le en ligne

Vous pensez peut-être à vous-même, comment créer un octet NUL sans 0? Ne crains rien, jeune sauterelle! car nous avons la capacité d’utiliser les %mathématiques aussi, en créant zéro avec 1%1.

PHP 7, 6 caractères

'().;^

L'idée est qu'il est possible d'exécuter du code arbitraire en utilisant la construction suivante:

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

eval ne fonctionnerait pas ici, car il s'agit d'une construction de langage et ne peut pas être appelé à l'aide de fonctions variables.

create_function et le code pourrait être écrit comme une concaténation de XOR au niveau du bit de caractères disponibles:

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

En utilisant ().;^pour <charX_Y>, nous pouvons obtenir

()./:;<=JKLMXY^_bcdepqvw

et quelques caractères non imprimables. Ce n'est pas suffisant, mais nous pouvons maintenant appeler 'eXp'()et obtenir des caractères numériques également:

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

Cela nous donne 1, 2et 3(les autres caractères seront ignorés par XOR, si l'autre chaîne est longue d'un caractère). De ().;^123nous pouvons maintenant générer tout le charset ASCII.

Essayez-le en ligne

Pyke, 5 personnages

0h.CE

Ceci est capable de produire un nombre infiniment grand, de le transformer en chaîne et de l'évaluer ensuite en tant que code Pyke.

Explication du code:

0- Ajouter 0 à la pile. Ceci est nécessaire pour commencer un numéro

h- Incrémenter le nombre précédent. En répétant cette opération un nombre de fois arbitraire, vous pouvez créer des nombres infiniment grands. Pyke supporte les bignums tels qu’ils sont écrits en Python, qui les utilise par défaut.

.C- Transformez un nombre en chaîne en utilisant l'algorithme suivant: ( lien Github )

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

À ce stade, nous pouvons créer une quantité arbitraire de chaînes et de nombres naturels dans Pyke avec des valeurs arbitraires. Les nombres peuvent être créés sous la forme correspondant à l'expression régulière 0(h)*et les chaînes peuvent être créées avec 0(h)*.C. Ils peuvent être imbriqués les uns dans les autres pour créer un mélange arbitraire de chaînes et de nombres entiers.

E- évalue une chaîne en tant que code Pyke. Cela utilise le même environnement que le code Pyke en cours d’exécution, ce qui permet de partager des éléments tels que l’entrée.

Tentative de preuve que Pyke est Turing Complete.

Une des manières les plus simples de montrer qu'une langue est complète est d'y implémenter Brainf * ck. C’est probablement beaucoup plus difficile dans Pyke que dans beaucoup d’autres langues, car ses opérations de liste et de dictionnaire sont pratiquement inexistantes en raison du manque de ressources dans la région où Pyke est conçu pour fonctionner: code-golf .

Tout d'abord, nous créons un interpréteur pour brainf * ck et l'encodons à l'aide de notre algorithme ci-dessus pour créer un nombre, puis exprimons ce nombre avec 0et h. Nous créons ensuite la chaîne contenant le code à exécuter de la même manière. Si nous devions en rester là, nous aurions la pile comme

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

Cela signifie que le code doit être dans la forme opposée car la pile Pyke est du premier entré dernier sorti.

Passons maintenant à la partie amusante: l'interpréteur brainf * ck avec 216 octets!

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

Essayez-le ici!

Si vous voulez essayer le code sous une forme semi-complète mais modifiable, essayez-le ici!

Pour convertir une chaîne en un nombre, vous pouvez utiliser le code Python suivant:

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

La solution (presque) finale peut être essayée ici!

Explication de l'interprète Brainf * ck

Tout d’abord, séparons le programme en plusieurs parties:

• L'initialisation:

Un séjour sans faille

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

• La boucle principale:

Un séjour sans faille

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.

• Les instructions
  • Incrémenter / décrémenter:+-

Un séjour sans faille

"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] = ^

• Entrée ,:

Un séjour sans faille

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

• Sortie .:

Un séjour sans faille

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

• Décalage Gauche / Droite <>:

Un séjour sans faille

~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

• Les conditionnels [:

Un séjour sans faille

~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

- Et ] :

Un séjour sans faille

~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

Empilé, 5 caractères

{!n:}

C'est étonnamment court. Si Stacked peut implémenter chacune des combinaisons SKI, c'est Turing Complete. Résumer:

• I combinator - la fonction d'identité. x -> x
• K combinator - la fonction constante. x -> y -> x
• S combinator - la fonction de substitution. (x, y, z) -> x(z)(y(z))

Je combine: {!n}

Maintenant, pour les détails empilés. {! ... }est un n-lambda. C'est une fonction unaire dont l'argument est implicitement n. Ensuite, la dernière expression est renvoyée par la fonction. Ainsi, {!n}est une fonction qui prend un argument net donne n.

K combinateur: {!{:n}}

Maintenant, {:...}est une fonction qui ne prend aucun argument, et retourne .... En combinant cela avec notre formation n-lambda, nous obtenons (en ajoutant des espaces pour plus de clarté):

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

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

Ok, ça a l'air un peu plus compliqué. Ainsi, un lambda prend des arguments, séparés par des caractères non identifiants. Ainsi, le lambda dans l'en-tête est équivalent à:

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

Ceci est un lambda qui prend trois arguments, n, nnet nnn. Remplaçons ces avec x, yet zpour plus de clarté:

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

Les deux ne {!n}!sont que des fonctions d'identité pour éviter à nouveau les espaces, où !signifie "exécuter". Donc, encore une fois, en réduisant:

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

Avec une explication:

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

Et par conséquent, c'est le combinateur S.