Zusammenfassung:

Was ist für jede Sprache die kleinste Anzahl von eindeutigen Zeichen, die für Ihre Sprache als vollständig zu bezeichnen sind ?

Herausforderung:

Finden Sie für jede Sprache Ihrer Wahl die kleinste Teilmenge von Zeichen, die es Ihrer Sprache ermöglicht, Turing-Complete zu sein. Sie können Ihren Zeichensatz beliebig oft wiederverwenden.

Beispiele:

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

• Brainfuck: +<>[](nimmt eine Größe der Umhüllungszelle an)

• Python 2: ()+1cehrx(aus Skripten wie exec(chr(1+1+1)+chr(1)))

Wertung:

Diese Herausforderung wird in Zeichen und nicht in Bytes gewertet . Beispiel: Die Punktzahlen für die Beispiele sind 6, 5 und 9.

Anmerkungen:

• Diese Herausforderung unterscheidet sich von anderen in dem Sinne, dass Sie nur Ihre Sprache Turing-Complete sein (nicht unbedingt in der Lage, jedes Merkmal der Sprache zu verwenden).

• Obwohl Sie dies können, posten Sie bitte keine Antworten, ohne die verwendeten Zeichen zu reduzieren. Beispiel: Brainfuck mit 8 Zeichen (da jedes andere Zeichen standardmäßig ein Kommentar ist.)

• Sie MÜSSEN mindestens eine kurze Erklärung geben, warum Ihre Teilmenge Turing-Complete ist.

Haskell, 4 Zeichen

()=;

Mit können ()=wir S, K und I definieren. Die Definitionen müssen entweder durch ;NL oder durch eine NL getrennt werden.

Wir definieren (==)als S (die zweite Zeile zeigt eine besser lesbare Version):

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

(===) Fragen:

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

und (====)wie ich:

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

Zum Glück (==)sind (===), (====)usw. gültige Funktions- / Parameternamen.

Wie @ ais523 betont, reicht SKI in einer stark typisierten Sprache wie Haskell nicht aus, daher müssen wir einen Fixpunkt-Kombinator hinzufügen (=====):

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

JavaScript (ES6), 5 Zeichen

Vielen Dank an @ETHproductions und @ATaco, die uns dabei geholfen haben. Dies war ein Gruppenprojekt, und obwohl die ursprüngliche Idee meine war, sind viele der Details ihre. Sehen Sie sich hier die Chat-Diskussion an, in der diese JavaScript-Teilmenge entwickelt wurde .

[]+=`

Es ist ziemlich sicher,[]()+! dass jedes Javascript-Programm mit den Zeichen ( ) geschrieben werden kann, aber 5 Zeichen reichen nicht aus . Dies ist jedoch keine Herausforderung beim Schreiben von beliebigem JavaScript. Es ist eine Herausforderung, eine Turing-vollständige Sprache zu schreiben, und die Tatsache, dass Turing-vollständige Sprachen keinen Zugriff auf das DOM oder sogar interaktive E / A benötigen, zeigt, dass wir ein Programm mit allen erforderlichen Funktionen schreiben können , auch ohne die Fähigkeit, ein evaloder ein Äquivalent auszuführen .

Grundlegendes Bootstrapping

JavaScript ist sehr flexibel mit Typen. Ist also zum Beispiel []ein leeres Array, hat aber den Wert +[]0 und []+[]ist die Null-Zeichenfolge. Insbesondere die Tatsache, dass wir mit diesem Zeichensatz 0 erzeugen können, ermöglicht es, den Effekt von Klammern für die Gruppierung zu simulieren. (a)kann geschrieben werden als [a][+[]]. Wir können diese Art von Trick verwenden, um verschiedene Charaktere zu erzeugen, indem wir nur verwenden +[]:

• [][+[]]ist undefined(als erstes Element eines leeren Arrays); damit
• []+[][+[]]ist "undefined"(die Stringifizierung von undefined); damit
• [[]+[][+[]]]is ["undefined"](umhüllt das in ein Array); damit
• [[]+[][+[]]][+[]]ist "undefined"(sein erstes Element); damit
• [[]+[][+[]]][+[]][+[]]ist "u"(sein erster Buchstabe).

uist eine der am einfachsten zu erstellenden Figuren, aber mit ähnlichen Techniken können wir eine Reihe anderer Figuren erstellen. Über den gleichen Link wie zuvor erhalten wir die folgende Liste der Zeichen, auf die mit zugegriffen werden kann +[](dies ist die gleiche Liste wie für +[](), außer ,dass dies die einzige Konstruktion ist, die Klammern für einen anderen Zweck als Gruppierung / Vorrang verwendet):

0123456789acdefinotuvyIN (){}.

Wir können nicht sehr viele nützliche Wörter aus dieser Menge von Zeichen buchstabieren (denken Sie daran, dass dies die Menge von Zeichen ist, die wir als Zeichenketten produzieren können ; wir können sie nicht ohne irgendeine Art von ausführen eval). Als solches brauchen wir einen anderen Charakter. Wir werden es verwenden =, da es später nützlich sein wird, aber vorerst werden wir es verwenden, um den Vergleichsoperator zu buchstabieren ==. Dies ermöglicht es uns, falseund zu produzieren true, die stringiert und indexiert werden können, und lrsdie Zeichen, die wir in Strings einfügen können, sofort zu ergänzen .

Das mit Abstand wichtigste Wort, mit dem wir buchstabieren können, was wir vorher nicht konnten, ist constructor. JavaScript hat jetzt eine Eigenschaftenzugriffssyntax, die folgendermaßen aussieht:

object.property

Sie können es aber auch so schreiben:

object["property"]

und nichts hindert uns daran, eine berechnete Eigenschaft anstelle eines String-Literal zu verwenden. Wir können also etwas in der Art von tun

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

(mit den wie oben beschrieben erzeugten Buchstaben; der Code wird schnell sehr lang!); Das ist äquivalent zu object.constructor, mit dem wir auf die Konstruktoren beliebiger Objekte zugreifen können.

Es gibt mehrere Tricks, die wir damit machen können. Vom Alltäglichen zum Fantastischen:

• Der Konstruktor eines Objekts ist eine Funktion. Insbesondere hat es einen Namen, und dieser Name ist Teil der Stringifizierung der Funktion. So können wir beispielsweise [[]+[]][+[]]["constructor"]den Konstruktor für einen String abrufen, dessen Name "String" ist, und ihn dann mit einem String versehen, um das Großbuchstabenzeichen zu erhalten S. Dies erweitert unser Alphabet ein wenig und wir werden später einige der neuen Zeichen brauchen.

• Alle Arrays haben den gleichen Konstruktor. []["constructor"] == []["constructor"]ist true(im Gegensatz [] == [], was falsch ist). Dies mag unbedeutend erscheinen, ist aber sehr wichtig, da es uns eine Methode zum dauerhaften Speichern von Werten bietet. Wir können eine zufällige Eigenschaft für den Konstruktor festlegen und später zurücklesen. (Dies ist einer der Gründe, die wir =insbesondere verwenden, anstatt eine der anderen Möglichkeiten zum Generieren trueund Abrufen false.) Beispielsweise können wir das dort gespeicherte Array auswerten [[]["constructor"]["a"]=[]]und später lesen []["constructor"]["a"]und zurückholen.

  Dies erfüllt eine der Anforderungen, die wir an die Vollständigkeit von Turing stellen und an die Fähigkeit, beliebige Datenmengen zu speichern und abzurufen. Wir können eine Cons-Zelle mit einem Array aus zwei Elementen erstellen, Werte aus unserem Konstruktoreigenschaftenspeicher entnehmen und sie dann anstelle eines dieser Werte zurückspeichern, sodass wir beliebig große Datenstrukturen im Speicher aufbauen können. und wir können auf diesen Speicher zugreifen, indem wir umgekehrt vorgehen und ihn Stück für Stück herunterreißen, bis die gewünschten Daten verfügbar sind. Das Lesen ist destruktiv, aber das ist akzeptabel, da wir mehr als einen Ort zum Speichern von Daten haben, sodass wir sie beim Lesen kopieren und dann die Kopie wieder an den ursprünglichen Ort zurücklegen können.

• Es ermöglicht uns, den Konstruktor für eine Funktion []["find"]aufzusuchen (es gibt viele Funktionen, auf die wir mit unserem eingeschränkten Alphabet zugreifen können , dh Array.find ist am einfachsten zugänglich, aber es gibt andere). Warum ist das sinnvoll? Nun, wir können es tatsächlich für den beabsichtigten Zweck eines Konstruktors verwenden und Funktionen konstruieren! Leider können wir mit unserem Zeichensatz dem Function-Konstruktor keine berechnete Zeichenfolge übergeben. Bei Verwendung von wird `jedoch ein String- Literal übergeben (z. B. []["find"]["constructor"]`function body goes here`). Dies bedeutet, dass wir benutzerdefinierte Werte des Funktionstyps mit jedem Verhalten bei der Ausführung definieren können, sofern wir dieses Verhalten vollständig mit ausdrücken können []+=. Ist beispielsweise []["find"]["constructor"]`[]+[]`eine ziemlich langweilige Funktion, die die Nullzeichenfolge berechnet, sie verwirft und beendet. DasFunktion ist nicht nützlich, aber komplexer. Beachten Sie, dass die Funktionen zwar keine Parameter oder Rückgabewerte annehmen können, dies in der Praxis jedoch keine Probleme darstellt, da wir den Konstruktoreigenschaftenspeicher verwenden können, um von einer Funktion zu einer anderen zu kommunizieren. Eine weitere Einschränkung besteht darin, dass wir `im Hauptteil einer Funktion nicht verwenden können.

  Jetzt können wir benutzerdefinierte Funktionen definieren, aber was uns an dieser Stelle zurückhält, ist die Schwierigkeit , sie aufzurufen . Auf der obersten Ebene des Programms können wir eine Funktion mit aufrufen ``, aber in der Lage zu sein, Funktionen nur von der obersten Ebene aufzurufen, lässt uns keine Art von Schleife ausführen. Vielmehr brauchen wir Funktionen, um uns gegenseitig aufrufen zu können.

  Dies erreichen wir mit einem ziemlich raffinierten Trick. Erinnern Sie sich an das Kapital, das Swir früher generiert haben? Das lässt uns buchstabieren "toString". Wir werden es nicht nennen; Wir können Dinge in Strings umwandeln, indem wir []sie hinzufügen . Vielmehr werden wir es ersetzen . Wir können Konstruktorspeicher verwenden, um persistente Arrays zu definieren, die in der Nähe bleiben. Wir können dann unsere erstellten Funktionen den toStringMethoden der Arrays zuweisen , und diese Zuweisungen bleiben auch erhalten. Alles, was wir jetzt tun müssen, ist ein einfaches +[]Array, und plötzlich wird unsere benutzerdefinierte Funktion ausgeführt. Dies bedeutet, dass wir die Zeichen verwenden können+=[]Funktionen aufrufen, und daher können sich unsere Funktionen gegenseitig aufrufen - oder sich selbst. Dies gibt uns eine Rekursion, die uns Schleifen gibt, und plötzlich haben wir alles, was wir für die Turing-Vollständigkeit brauchen.

Hier ein Überblick über eine Reihe von Funktionen, die Turing-Vollständigkeit verleihen, und wie sie implementiert werden:

• Ungebundener Speicher : Verschachtelte Arrays im Konstruktorspeicher
• Kontrollfluss : implementiert mit ifund Rekursion:
  • if: Konvertieren eines Booleschen Werts in eine Zahl und Indizieren in ein Array mit zwei Elementen. Ein Element führt die Funktion für den thenFall aus, wenn es stringiert ist, das andere Element führt die Funktion für den elseFall aus, wenn es stringiert ist
  • Rekursion : Geben Sie ein geeignetes Element des Konstruktorspeichers an
• Befehlssequenzierung : [a]+[b]+[c]wertet aus a, bund von clinks nach rechts (zumindest in dem von mir überprüften Browser)

Leider ist dies ziemlich unpraktisch; Es ist nicht nur enorm groß, da Zeichenfolgen nach den ersten Prinzipien zeichenweise aufgebaut werden müssen, sondern es gibt auch keine Möglichkeit für die E / A (die nicht vollständig sein muss). Wenn es jedoch beendet wird, ist es zumindest möglich, den Konstruktorspeicher manuell nachzuschlagen, so dass es nicht unmöglich ist, Ihre Programme zu debuggen, und sie sind nicht vollständig nicht kommunikationsfähig.

Unär , 1 Zeichen

0

Die Wahl des Charakters spielt eigentlich keine Rolle; Die Länge des Programms definiert das Brainfuck-Programm, in das es übersetzt wird. Während die Spezifikation 0Zeichen verlangt, scheinen die meisten Transpiler dies nicht zu prüfen.

vim, 9 8 7 6 Zeichen

<C-v><esc>1@ad

Wir können ein beliebiges Vimscript-Programm wie folgt erstellen und ausführen:

1. Verwenden Sie die Sequenz aa<C-v><C-v>1<esc>dd@1<esc>dddd, um ein <C-a>In-Register zu erhalten 1.

2. Aktivieren Sie den Einfügemodus mit aund fügen Sie anschließend ein ein a, um den Einfügemodus in einem Makro später erneut zu aktivieren.

3. Für jedes Zeichen im gewünschten Vimscript-Programm

   1. Verwenden Sie <C-v><C-v>1<esc>, um die Literalsequenz einzufügen <C-v>1.

   2. verwenden @1(das ist <C-a><cr>, in dem die letzten <cr>ist ein No-op am letzten Zeile ist) so oft wie erforderlich , die zu inkrementieren , 1bis der ASCII - Wert des gewünschten Zeichens erreicht ist ,

   3. und mit erneut in den Einfügemodus wechseln a.

4. Löschen Sie die Zeile (zusammen mit einem nachfolgenden Zeilenumbruch) im 1Register mit <esc>dd.

5. Führen Sie das Ergebnis mit vim als Tastendruck aus @1, und <esc>ddlöschen Sie dann die Zeile, die von der nachfolgenden neuen Zeile aus dem vorherigen Schritt eingegeben wurde.

6. Führen Sie die resultierende beliebige Folge von Bytes mit aus dd@1. Wenn es mit einem beginnt :, wird es als Vimscript-Code interpretiert und aufgrund des abschließenden Zeilenumbruchs von ausgeführt dd.

Ich bin nicht davon überzeugt, dass dies ein minimaler Zeichensatz ist, aber es ist ziemlich einfach, sich als Turing-vollständig zu erweisen.

Perl, 5 Zeichen

<>^es

Wie bei anderen Skriptsprachen geht es um evalbeliebige Zeichenfolgen. Da unser Zeichensatz jedoch keine Anführungszeichen oder Verkettungsoperatoren enthält, wird die Erstellung beliebiger Zeichenfolgen wesentlich komplexer. Beachten Sie, dass eval^"dies viel einfacher zu handhaben wäre, aber einen weiteren Charakter hat.

Unser Hauptwerkzeug ist s<^><CODE>ee, welches CODEseine Ausgabe auswertet und dann auswertet. Weitere ekönnen mit dem erwarteten Effekt hinzugefügt werden.

Wir verwenden Strings <>, die der Glob-Operator sind, außer wenn dies nicht der Fall ist. Das erste Zeichen kann nicht sein <(ansonsten sieht es aus wie der <<Operator), die spitzen Klammern müssen ausgeglichen sein und es muss mindestens ein Nicht-Buchstaben-Zeichen vorhanden sein (ansonsten wird es als Readline-Operator interpretiert).

Indem wir diese Zeichenketten zusammenfügen, können wir eine beliebige Kombination von Zeichen erhalten ^B^V^S(*-/9;<>HJMOY[`\^begqstv, solange wir akzeptieren, dass etwas Müll herumsteht (die ersten drei davon sind Steuerzeichen).

Nehmen wir zum Beispiel an, wir wollen bekommen "v99". Eine Möglichkeit v99ist "><<" ^ "e>>" ^ "see" ^ "^^^", aber wir können diese Zeichenfolgen aufgrund der Einschränkungen von nicht darstellen <>. Also verwenden wir stattdessen:

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

Das obige Y9;v99;Ergebnis ergibt , wenn es ausgewertet wird, dasselbe Ergebnis wie ein einfaches Ergebnis v99(nämlich das Zeichen mit dem ASCII-Code 99).

So können wir den gesamten ^B^V^S(*-/9;<>HJMOY[`\^begqstvZeichensatz verwenden, um unsere beliebige Zeichenfolge zu generieren, sie dann wie oben konvertieren und in eine kleben s<><CODE>eeee, um sie auszuführen. Leider ist dieser Zeichensatz immer noch sehr begrenzt, ohne dass eine Verkettung offensichtlich ist.

Aber zum Glück enthält es den Stern. So können wir schreiben *b, was zu der Zeichenfolge ausgewertet wird "*main::b". Dann *b^<^B[MMH^V^SY>(^ B, ^ V und ^ S sind wörtliche Steuerzeichen) erhalten wir (6, $&);, die, wenn sie erneut ausgewertet werden, den Wert der Übereinstimmungsvariablen von Perl zurückgeben $&. Auf diese Weise können wir eine begrenzte Form der Verkettung verwenden: wir können die Dinge immer wieder voranstellen zu $_verwenden s<^><THINGS>e, und verwenden Sie dann s<\H*><*b^<^B[MMH^V^SY>>eeeeval $_( \Hentspricht alles andere als horizontale Leerzeichen, wir es anstelle des Punktes verwendet werden , die nicht in unserem charset ist).

Mit 9-/können wir einfach alle Ziffern erzeugen. Mit Ziffern vund Verkettung können wir beliebige Zeichen erzeugen (vXXX liefert das Zeichen mit dem ASCII-Code XXX). Und wir können diese verketten, um beliebige Zeichenfolgen zu generieren. Es sieht also so aus, als könnten wir alles tun.

Lassen Sie uns ein vollständiges Beispiel schreiben. Angenommen, wir möchten ein Programm, das seine eigene PID ausgibt. Wir beginnen mit dem natürlichen Programm:

say$$

Wir konvertieren es in V-Notation:

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

Wir schreiben dies nur mit ^B^V^S(*-/9;<>HJMOY[`\^begqstv(Leerzeichen dienen nur der Lesbarkeit und haben keinen Einfluss auf die Ausgabe):

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;

Schließlich konvertieren wir das obige Programm in nur <>^es: Pastebin . Leider stürzt dies mit Perl ab Excessively long <> operator, aber das ist nur eine technische Einschränkung und sollte nicht berücksichtigt werden.

Puh, das war schon die Reise. Es wäre wirklich interessant, jemanden mit einem Satz von 5 Zeichen zu sehen, der die Dinge einfacher macht.

BEARBEITEN: Durch einen etwas anderen Ansatz können wir vermeiden, dass das Längenlimit von überschritten wird <>. Voll funktionsfähiger Brainfuck-Interpreter nur mit <>^es: Online ausprobieren! . Automatisiertes Perl zu <>^esTranspiler: Pastebin .

Python 2, 7 Zeichen

exc="%\n

Jedes Python 2-Programm kann mit diesen 7 Zeichen codiert werden ( \nist Newline).

Konstruktion beliebiger Zeichenketten

Wir können eine Verkettung durchführen, indem wir den Ersetzungsoperator wiederholt %auf eine einzelne Zeichenfolge anwenden . Wenn zum Beispiel a=1, b=2, c=3, "%d%%d%%%%d" % a % b % cwird es uns geben Sie die Zeichenfolge "123". Glücklicherweise execgeben uns die Buchstaben Zugang zu %xund %cdie sind im Grunde hex()und chr(). Mit %ckönnen wir eine beliebige Zeichenfolge konstruieren, solange wir die erforderlichen Zahlen haben, die die Zeichen darstellen. Wir können diesen String dann mit dem execSchlüsselwort als Python-Code ausführen .

Zahlen machen

Wir können den Zugang zu bekommen 0und 1rechts von der Fledermaus mit Vergleichen ( ==). Durch eine Kombination von verketteten Ziffern und Modulo ist es möglich, die Zahl zu konstruieren, die in ASCII 43repräsentiert +. Auf diese Weise können wir die Zahlen konstruieren, die wir für unseren Code benötigen.

Etwas zusammensetzen

Ich habe einige Details in dieser Erklärung weggelassen, da sie für das Verständnis, wie Programme unter diesen Bedingungen geschrieben werden können, nicht wesentlich sind. Unten ist ein Python 2-Programm, das ich geschrieben habe und das jedes Python-Programm in eine funktional äquivalente Version konvertiert, die nur diese 7 Zeichen verwendet. Die verwendeten Techniken sind inspiriert von diesem Beitrag über Anarchy Golf von k. Einige einfache Tricks werden auch verwendet, um die Größe der generierten Programme in einem vernünftigen Rahmen zu halten.

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

Probieren Sie es online aus

Mathematica, 5 4 Zeichen

I[]

ist ein privat genutztes Unicode-Zeichen , mit dem Sie als Operator FunctionLiterale für unbenannte Funktionen mit benannten Argumenten schreiben können. Das Zeichen sieht ↦in etwa so aus wie in Mathematica, daher werde ich dieses Zeichen für den Rest dieser Antwort verwenden, um die Übersichtlichkeit zu gewährleisten.

Mit diesen können wir das umsetzen S, Kund IKombinatoren der kombinatorischen Logik:

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

Ein syntaktisches Problem bei diesen ist, dass sie ↦eine sehr niedrige Priorität haben, was ein Problem sein wird, wenn wir versuchen, Argumente an diese Kombinatoren zu übergeben. Normalerweise können Sie das beheben, indem Sie einen Combinator Cin Klammern setzen (C), aber wir haben keine Klammern. Wir können jedoch eine andere Magie verwenden Iund []einwickeln C, die eine ausreichend hohe Priorität hat, damit wir sie später verwenden können:

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

Schließlich , eine Anwendung zu schreiben A x y z(wo Aein combinator ist „parenthesised“ , wie oben gezeigt, und x, y, zoder nicht parenthesised werden kann oder größere Ausdrücke sein), können wir schreiben:

A[x][y][z]

Damit bleibt die Frage offen, wie das Klammeräquivalent tatsächlich funktioniert. Ich werde versuchen, es grob in der Reihenfolge zu erklären, in der ich es mir ausgedacht habe.

Das, was wir syntaktisch haben, um etwas zu gruppieren, sind die Klammern []. In Mathematica werden Klammern auf zwei Arten angezeigt. Entweder als Funktionsaufruf f[x]oder als Indizierungsoperator f[[i]](was eigentlich nur eine Abkürzung ist Part[f, i]). Insbesondere bedeutet dies, dass weder [C]noch [[C]]Syntax gültig ist. Wir brauchen etwas davor. Das kann theoretisch alles sein. Wenn wir das benutzen, was Iwir bereits haben, können wir I[C]zum Beispiel bekommen. Dies bleibt unbewertet, da Ies sich nicht um eine unäre Funktion handelt (es ist überhaupt keine Funktion).

Aber jetzt müssen wir einen Weg finden, um es Cerneut zu extrahieren , da es sonst nicht ausgewertet wird, wenn wir versuchen, ihm ein Argument xzu übergeben.

Hier bietet es sich an, dass nicht nur Listen, sondern f[[i]]beliebige Ausdrücke verwendet werden fkönnen. Angenommen, dass fselbst von der Form ist head[val1,...,valn], dann f[[0]]gibt head, f[[1]]gibt val1, f[[-1]]gibt valnund so weiter. Also müssen wir entweder das holen 1oder -1das Cnochmal extrahieren , weil entweder das I[C][[1]]oder das I[C][[-1]]auswertet C.

Wir können erhalten 1von einem beliebigen undefinierten Symbol wie x, aber das zu tun, würden wir ein weiteres Zeichen für die Teilung benötigen ( x/xgibt 1für nicht definiert x). Die Multiplikation ist die einzige arithmetische Operation, die wir (im Prinzip) ohne zusätzliche Zeichen ausführen können. Daher benötigen wir einen Wert, der multipliziert werden kann, um -1oder zu ergeben 1. Dies ist letztendlich der Grund, warum ich mich speziell Ifür unsere Identifikatoren entschieden habe. Denn Ifür sich ist Mathematica das eingebaute Symbol für die imaginäre Einheit.

Damit bleibt aber noch ein letztes Problem: Wie multiplizieren wir uns eigentlichI von alleine? Wir können nicht einfach schreiben, IIda dies als einzelnes Symbol analysiert wird. Wir müssen diese Token trennen, ohne a) ihren Wert zu ändern und b) neue Zeichen zu verwenden.

Das letzte bisschen Magie ist ein Stück undokumentiertes Verhalten: f[[]](oder gleichwertig Part[f]) ist eine gültige Syntax und gibt sich fselbst zurück. Anstatt also die Multiplikation Ivon Imultiplizieren wir I[[]]durch I. Durch das Einfügen der Klammern sucht Mathematica anschließend nach einem neuen Token und I[[]]Iwertet es nach -1Bedarf aus. Und so enden wir I[C][[I[[]]I]].

Beachten Sie, dass wir nicht verwenden konnten I[]. Dies ist ein argumentloser Aufruf der Funktion I, aber wie ich bereits sagte, Iist dies keine Funktion, so dass dies nicht bewertet wird.

Python 2, 8 Zeichen

exc'%~-0

Diese Zeichen ermöglichen die Übersetzung / Ausführung eines Python-Programms unter Verwendung von Formatstrings und exec. Obwohl es für die Turing-Vollständigkeit nicht erforderlich ist, ein Programm übersetzen zu können, sind dies die wenigsten mir bekannten Zeichen, die es zu TC machen. Dass es so mächtig ist, ist nur ein Bonus.

Ein doppeltes Anführungszeichen sowie eine einzelne Ziffer neben Null können ebenfalls verwendet werden. (Jetzt, wo ich darüber nachdenke, 1wäre auf jeden Fall besser, in kürzeren Programmen führt, da Sie nutzen könnten 1, 11und 111, wie auch.)

Hier ist das Programm print:

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

Probieren Sie es online aus

Das Basisprogramm erfordert

exec''

Jedes xzum Programm hinzugefügte Zeichen benötigt ( Zeichenanzahl ):

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

Die Ausnahme hiervon ist, dass bestimmte Optimierungen / Verknüpfungen vorgenommen werden könnten, um das codierte Programm zu verkürzen, z. B. die Verwendung %'0'für das Zeichen 0anstelle von 48 -~usw.

Praktische Anwendungen (AKA-Golf): Ich habe diese Taktik verwendet, um diese Herausforderung zu lösen , ohne einen zusätzlichen Handicap-Charakter zu verwenden.

Gutschrift für die Zeichenliste und ein Encoderprogramm: hier

Informationen zum Ermitteln einer Untergrenze für die resultierende Programmgröße (ohne Optimierungen) finden Sie in diesem Kommentar .

Die Anzahl der benötigten Bytes steigt O(2**n), daher wird diese Methode zum Golfen nicht empfohlen. Ein Quine, der diese Quellenbeschränkung verwendet, wäre wahnsinnig lang.

C (nicht portierbar), 24 18 13 Zeichen

aimn[]={};,1+

Dies umfasst alle Programme des Formulars

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

... wobei die Konstantenfolge (Form 1 + 1 + 1 ...) die Maschinencodedarstellung Ihres Programms enthält. Dies setzt voraus, dass Ihre Umgebung die Ausführung aller Speichersegmente zulässt (anscheinend gilt dies für tcc [danke @ Tennis!] Und einige Computer ohne NX-Bit). Andernfalls müssen Sie unter Linux und OSX möglicherweise das Schlüsselwort voranstellen constund unter Windows #pragmadas Segment explizit als ausführbar markieren.

Als Beispiel wird das folgende Programm im obigen Stil Hello, World!unter Linux und OSX auf x86 und x86_64 gedruckt.

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};

Probieren Sie es online!

Retina , 6 Zeichen

$%`{¶

Sowie Linefeeds (0x0A).

Einerseits wundert es mich, dass ich es so tief hinbekommen habe. Andererseits bin ich sehr unzufrieden mit der Aufnahme von %¶. Jeder von$`{ wird für zwei oder sogar drei Zwecke wiederverwendet, aber %¶ zusammen dienen sie nur einem Zweck. Dadurch wirken sie eher verschwenderisch und zerstören die Eleganz des Ansatzes leicht. Ich hoffe, dass es einen Weg gibt, diese Konstruktion zu schlagen.

Auf zum Beweis. Ich werde einen einfachen Weg zum Übersetzen beschreiben zyklische Tag-Systeme mit den obigen Zeichen in Retina .

Zunächst verwenden wir `und {für das binäre Alphabet anstelle von 0und 1. Diese sind praktisch, da sie nicht in einer regulären Schreibweise maskiert werden müssen, sondern entweder für die Retina oder in der Substitutionssyntax eine Bedeutung haben. Ich benutze `für 0und {für 1, aber diese Wahl ist willkürlich. Außerdem werden wir die Zeichenfolge (und die Produktionen) im Speicher umkehren, da wir bei der Arbeit mit dem letzten Zeichen $und verwenden können$` anstelle von ^und $'maximieren können.

Wenn das Anfangswort mit bezeichnet ist Sund die ith (umgekehrte) Produktion aufgerufen wirdpi wird, sieht das resultierende Programm folgendermaßen aus:

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Diese Konstruktion wächst mit jeder Anwendung einer Produktion unvermeidlich im Speicher, und es ist unwahrscheinlich, dass sie beendet wird - an dem Punkt, an dem das zyklische Tag-System beendet wird (wenn der Arbeitsstring leer wird), ändert sich das Verhalten des resultierenden Retina-Programms im Grunde undefiniert.

Schauen wir uns an, was das Programm macht:

S

Wir beginnen mit der Initialisierung des Arbeitsstrings bis zum Anfangswort.

{`

Dies schließt den Rest des Programms in ein Programm ein, das so lange ausgeführt wird, bis die resultierende Zeichenfolge nicht mehr geändert werden kann (hey, naive integrierte Endlosschleifenerkennung kostenlos ...). Die beiden Zeilenvorschübe dort sind nicht wirklich notwendig, aber sie trennen die Schleife klarer von den einzelnen Produktionen. Der Rest des Programms durchläuft jede der Produktionen, und aufgrund der Schleife verarbeiten wir sie effektiv zyklisch immer und immer wieder.

Jede Produktion wird in zwei Schritten bearbeitet. Zuerst beschäftigen wir uns mit dem Fall, dass das führende (oder in unserem Fall nachfolgende) Symbol ist {. In diesem Fall verwenden wir die Produktion:

{$
¶pi$%``

Der reguläre Ausdruck stimmt nur überein, wenn die Zeichenfolge auf endet {. In diesem Fall ersetzen wir es durch:

• Ein Zeilenvorschub (¶ ). Wir werden immer nur mit der letzten Zeile der Arbeitszeichenfolge arbeiten, daher wird die Arbeitszeichenfolge bis jetzt effektiv verworfen (weshalb die Speichernutzung des Programms immer größer wird).
• Die aktuelle Produktion (pi ), die wir hiermit dem Arbeitsstring voranstellen (wo das zyklische Tag-System sie anfügt).
• Die vorher verbleibende Arbeitszeichenfolge ( $%`). Aus diesem Grund müssen wir Folgendes einfügen ¶: $%`nimmt alles auf, was vom Spiel übrig ist, aber nur in derselben Zeile. Daher sieht dies nicht den ganzen Müll, den wir von früheren Produktionen übrig haben. Mit diesem Trick können wir etwas am Ende der Arbeitszeichenfolge abgleichen, um etwas am Anfang der Arbeitszeichenfolge einzufügen , ohne etwas wie (.+)und verwenden zu müssen$1 die die Anzahl der Zeichen deutlich sprengen würde wir brauchen.
• Ein einzelnes Backtick ( `). Dadurch wird das {( 1-Zeichen), das wir abgeglichen haben, durch ein `( 0-Zeichen) ersetzt, sodass die nächste Stufe nicht wissen muss, ob wir die aktuelle Produktion bereits verarbeitet haben oder nicht.

Der zweite Teil jeder Produktion ist dann der triviale Fall, in dem die Produktion übersprungen wird:

``$

Wir löschen einfach ein Trailing `. Der Grund, warum wir `in der ersten Zeile zwei brauchen , ist, dass Retina den ersten Backtick als Trennlinie zwischen Konfiguration und Regex ansieht. Dies gibt ihm einfach eine leere Konfiguration, so dass wir Backticks im Regex selbst verwenden können.

Java 7, 18 17 Zeichen

\bcdefu0123456789

Der gesamte Java-Quellcode kann auf Unicode-Codepunkte reduziert werden. "a" wird nicht benötigt, da es nur für verwendet wird*:jJzZ . Das Sternchen wird für Multiplikations- oder Blockkommentare verwendet. Die Multiplikation wird einfach wiederholt und Sie können stattdessen einzeilige Kommentare verwenden (oder sie einfach weglassen). Der Doppelpunkt wird für ternäre Operatoren verwendet, für die Sie stattdessen eine if-Anweisung verwenden können, und für foreach-Schleifen, die durch normal for-Schleifen ersetzt werden können. j und z sind in Java kein Bestandteil von Schlüsselwörtern.

Wenn Sie versuchen, ein anderes Zeichen zu entfernen, müssen Sie mindestens eines der in Java Boiler Plate erforderlichen Zeichen hinzufügen class a{public static void main(String[]a){}}. Siehe unten:

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

Hier ist ein Beispiel mit einem Hello World-Programm. Probieren Sie es online aus!

Java 8, 16 Zeichen

\bdefu0123456789

Vielen Dank an ais523 für den Hinweis. In Java 8 können Interfaces statische Methoden haben, was bedeutet, dass wir "c" löschen können, da wir es für das "l" in "class" nicht benötigen. "c" wird verwendet, ,<lL\|damit wir am Ende etwas mehr Java-Funktionalität verlieren, als wenn wir "a" entfernt hätten, aber wir haben immer noch genug, um vollständig zu sein. Probieren Sie es online!

Labyrinth , 5 Zeichen

~{}

Pluszeilenvorschübe (0x0A) und Leerzeichen (0x20).

Ich werde einen Beweis in Form einer Reduktion von Smallfuck (eine reduzierte Brainfuck-Variante, die 1-Bit-Zellen verwendet) skizzieren . Beachten Sie, dass Smallfuck selbst nicht Turing-vollständig ist, da die Sprache angibt, dass sein Band endlich sein muss. Wir gehen jedoch von einer Variante von Smallfuck mit einem unendlichen Band aus, das dann Turing-vollständig wäre (da Labyrinth keinen Speicher hat) Einschränkungen aufgrund des Designs).

Eine wichtige Invariante bei dieser Reduzierung ist, dass jedes Programm (oder Unterprogramm) zu einem Labyrinth-Programm (oder Unterprogramm) führt, das in derselben Zeile beginnt und endet und eine gerade Anzahl von Spalten umfasst.

Labyrinth hat zwei Stapel, die anfänglich mit einer unendlichen (impliziten) Menge von 0s gefüllt sind . {und }verschieben Sie den Spitzenwert zwischen diesen Stapeln. Wenn wir die Oberseite des Hauptstapels als die aktuelle "Zelle" betrachten, können diese beiden Stapel als die beiden semi-unendlichen Hälften des von Smallfuck verwendeten unendlichen Bands angesehen werden. Es ist jedoch praktischer, zwei Kopien jedes Bandwerts auf den Stapeln zu haben, um die oben erwähnte Invariante sicherzustellen. Deshalb <und >wird übersetzt werden {{und }}jeweils (man konnte sie tauschen , wenn Sie mögen).

Anstatt die Zellenwerte 0und zuzulassen 1, verwenden wir 0und -1, zwischen denen wir umschalten können ~(bitweise Negation). Die genauen Werte sind für die Turing-Vollständigkeit unerheblich. Wir müssen beide Kopien des Wertes auf dem Stapel ändern, was uns wieder eine Übersetzung mit gerader Länge gibt: *wird ~}~{.

Damit bleiben die Steuerflussbefehle erhalten []. Labyrinth hat keinen expliziten Kontrollfluss, sondern der Kontrollfluss wird durch das Layout des Codes bestimmt. Wir benötigen die Leerzeichen und Zeilenvorschübe, um dieses Layout zu erstellen.

Beachten Sie zunächst, dass dies ~~ein No-Op ist, da die beiden ~effektiv stornieren. Wir können dies verwenden, um beliebig lange Pfade im Code zu haben, solange ihre Länge gerade ist. Wir können jetzt die folgende Konstruktion verwenden, um AA[BB]CCin Labyrinth zu übersetzen (ich verwende Doppelbuchstaben, damit die Größe jedes Ausschnitts in Labyrinth gleichmäßig ist, wie von der Invariante garantiert):

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

Hier ..ist eine geeignete Anzahl, ~die der Breite von entspricht BB.

Auch hier ist zu beachten, dass die Breite der Konstruktion gleichmäßig bleibt.

Wir können jetzt durchgehen, wie diese Schleife funktioniert. Der Code wird über die eingegeben AA. Der erste ~~tut nichts und lässt uns die Kreuzung erreichen. Dies entspricht in etwa dem [:

• Wenn der aktuelle Zellenwert Null ist, fährt die IP geradeaus fort, was letztendlich überspringt BB. Der ..Teil ist immer noch ein No-Op. Dann erreichen wir eine einzelne ~an einer anderen Kreuzung. Wir wissen jetzt , dass der aktuelle Wert nicht Null ist, sodass die IP die Kurve nach Norden nimmt. Es geht oben um die Kurve, bis es nach sechs eine weitere Kreuzung erreicht ~. Zu diesem Zeitpunkt ist der aktuelle Wert immer noch ungleich Null und die IP biegt erneut ab, um sich nach Osten in Richtung zu bewegen CC. Beachten Sie, dass die drei ~vor dem CCden aktuellen Wert zurückgeben 0, wie es sein sollte, wenn die Schleife übersprungen wurde.
• Wenn der aktuelle Zellenwert am Anfang der Schleife nicht Null ist, nimmt die IP die Abzweigung nach Süden. Es läuft noch sechs ~vor Erreichen BB(die nichts tun), und dann noch sechs ~vor Erreichen der nächsten Kreuzung. Dies entspricht in etwa der ].
  • Wenn die aktuelle Zelle Null ist, bewegt sich die IP weiter nach Norden. Der nächste ~macht den Wert ungleich Null, so dass die IP diesen zweiten Knotenpunkt einnimmt, der den Pfad mit dem Fall zusammenführt, dass die Schleife vollständig übersprungen wurde. Wieder setzen die drei ~den Wert vor Erreichen auf Null zurück CC.
  • Wenn die aktuelle Zelle nicht Null ist, nimmt die IP die Abzweigung nach Westen. Es gibt ~vor der nächsten Kreuzung, was bedeutet, dass an diesem Punkt der aktuelle Wert Null ist, so dass die IP weiter nach Westen geht. Dann wird es eine ungerade Zahl von geben, ~bevor die IP die anfängliche Verbindung wieder erreicht, so dass der Wert zurückgegeben wird -1und die IP nach Süden in die nächste Iteration übergeht.

Wenn das Programm Schleifen enthält, muss die allererste AAbis zum Anfang des Programms erweitert werden, damit die IP die richtige Zelle zum Starten findet:

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

Das ist das. Beachten Sie, dass Programme, die aus dieser Reduzierung resultieren, niemals beendet werden. Dies ist jedoch nicht Teil der Anforderungen an die Vollständigkeit des Turing (siehe Regel 101 oder Fractran).

Schließlich bleibt die Frage, ob dies optimal ist. In Bezug auf die Arbeitslast bezweifle ich, dass es möglich ist, mehr als drei Befehle auszuführen. Ich könnte eine alternative Konstruktion sehen, die auf Minsky-Maschinen mit zwei Registern basiert, aber das würde erfordern =()oder =-~, nur einen Stapelmanipulationsbefehl, aber dann zwei arithmetische Befehle zu haben. Ich würde mich freuen, wenn ich in dieser Sache falsch liegen würde. :)

Was die Layout-Befehle angeht, sind meines Erachtens Zeilenvorschübe erforderlich, da ein nützlicher Kontrollfluss in einer einzelnen Zeile nicht möglich ist. Leerzeichen sind jedoch technisch nicht erforderlich. Theoretisch könnte es möglich sein, eine Konstruktion zu entwickeln, die das gesamte Raster mit ~{}(oder =()oder =-~) füllt , oder ein zackiges Layout zu verwenden, bei dem die Linien nicht alle gleich lang sind. Das Schreiben von Code wie diesem ist jedoch unglaublich schwierig, da Labyrinth dann jede einzelne Zelle als Junction behandelt und Sie sehr vorsichtig sein müssen, damit der Code nicht verzweigt, wenn Sie dies nicht möchten. Wenn jemand beweisen oder widerlegen kann, ob das Weglassen des Leerzeichens für die Turing-Vollständigkeit möglich ist, würde ich gerne eine beträchtliche Prämie dafür ausgeben. :)

Haskell, 5 7 Zeichen

()\->=;

Als funktionale Sprache hat Haskell natürlich Lambdas, so dass es einfach ist, die Lambda-Rechnung zu simulieren. Die Syntax für Lambdas ist so, dass wir mindestens die Zeichen benötigen . Zusätzlich benötigen wir eine unbegrenzte Anzahl variabler Symbole, um beliebige Lambda-Ausdrücke erstellen zu können. Zum Glück brauchen wir keine neue Zeichen dafür, weil , , , ... sind alle gültigen Variablennamen. Tatsächlich ist jede Kombination in Klammern ein gültiger Variablenname, mit Ausnahme von just und , die für Lambda-Ausdrücke reserviert sind und mit denen ein Zeilenkommentar beginnt.(\variable->body)argument()\->
(>)(>>)(>>>)\->\->--

Beispiele:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))Typ bis(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))Typ bist -> t1 -> t
• I = (\(>)->(>))Typent -> t

Bearbeiten: Wie in den Kommentaren von ais523 ausgeführt , implementiert diese Konstruktion typisierte Lambda-Berechnungen , die für sich genommen nicht vollständig sind, da sie keine Möglichkeit zum Eingeben von Endlosschleifen bieten. Um dies zu beheben, benötigen wir eine Funktion, die eine Rekursion durchführt. Bisher verwendeten wir unbenannte Lambdas, die sich nicht selbst nennen können, weil sie keinen Namen haben. Also müssen wir die Zeichen hinzufügen =und ;eine fixFunktion implementieren :

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

Mit dieser Deklaration wird unser Lambda-Kalkül Turing vollständig, jedoch hinzugefügt, =und ;wir brauchen keine Lambdas mehr, wie Sie in Nimis Antwort sehen können, die nur verwendet ()=;.

CJam, 3 Zeichen

Auf )Vorschlag von Martin Ender entfernt

'(~

Ähnlich wie bei der Python als Beispiel.

Mit können '~Sie den ~Charakter erhalten. Dann (können Sie es mit dekrementieren, um das gewünschte Zeichen zu erhalten ( ~das letzte druckbare ASCII-Zeichen). ~Evaliert einen beliebigen String als normalen CJam-Code. Zeichenfolgen können erstellt werden, indem das Zeichen [(durch Dekrementieren ~) ermittelt, ausgewertet, eine Folge anderer Zeichen eingefügt und dann ausgewertet wird ]. Auf diese Weise können Sie jedes CJam-Programm mit nur diesen drei Zeichen erstellen und ausführen.

Berechnung 2 + 2 nur mit '(~

Brain-Flak , 6 Zeichen

(){}[]

Brain-Flak ist eine minimalistische Sprache mit nur 8 verfügbaren Zeichen. Es kann jedoch nachgewiesen werden, dass es eine Teilmenge von Brain-Flak gibt, die mit nur 6 Zeichen ebenfalls vollständig ist.

Als erstes implementieren wir eine Minsky-Maschine mit nur einem Stapel Brain-Flak. Wenn wir beweisen können, dass eine Minsky-Maschine mit nur einem Stapel möglich ist, können wir zeigen, dass Brain-Flak ohne die Nullen <>und []vollständig ist. Dadurch werden keine Zeichen sofort gespeichert, dies wird jedoch in Zukunft der Fall sein, wenn wir zeigen, dass dies <...>nicht erforderlich ist.

Eine Minsky-Maschine ist eine Art Turing-Vollautomat mit einer endlichen Anzahl unbegrenzter Register und zwei Instruktionen:

• Erhöhen Sie das a-Register

• Wenn die Dekrementierung nicht Null ist, wird ansonsten zu einem bestimmten Befehl übergegangen

Um eine goto-Struktur in Brain-Flak einzurichten, können wir das folgende Snippet verwenden:

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

Dadurch wird der Zähler dekrementiert und %sbei Null ausgeführt. Ein Bündel dieser verketteten Elemente ermöglicht es uns, eine Zahl auf den Stapel zu legen, die angibt, zu welcher Zeile wir wechseln möchten. Jeder dieser Befehle dekrementiert den oberen Bereich des Stapels, aber nur einer führt den Code tatsächlich aus.

Wir verwenden dies als Hülle für alle unsere Minsky-Maschinenanweisungen.

Das Inkrementieren eines bestimmten Registers ist ziemlich einfach, ohne den Stapel zu wechseln. Es kann mit dieser Zeichenfolgeformel erreicht werden:

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

Um beispielsweise das 3. Register zu erhöhen, schreiben wir den folgenden Code:

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

Jetzt müssen wir nur noch die zweite Operation implementieren. In Brain-Flak ist es ziemlich einfach zu überprüfen, ob eine Zahl Null ist:

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

wird nur ausgeführt, %swenn der TOS Null ist. So können wir unsere zweite Operation machen.

Da Minsky-Maschinen vollständig funktionieren, funktioniert Brain-Flak auch vollständig, ohne die <>und []-Operationen zu verwenden.

Allerdings haben wir die Anzahl der Zeichen noch nicht reduziert, da <...>und [...]werden noch verwendet. Dies kann durch einfache Substitution behoben werden. Da <...>ist eigentlich [(...)]{}in allen Fällen gleichbedeutend . Somit ist Brain-Flak Turing komplett ohne die Verwendung der Zeichen <und >(plus aller No-Ops).

> <> , 3 Zeichen

> <> ist in 3 machbar mit 1p-:

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

pBietet Reflektion und modifiziert den 2D-Quellcode, indem Zeichen in die Codebox eingefügt werden. Mit 1-können Sie eine beliebige Zahl auf den Stapel legen, da Sie eine Zahl 1-abziehen und mit 111-1--( x-(1-1-1) = x+1) eine weitere hinzufügen.

Nachdem alle 1p-Befehle ausgeführt wurden, wird der Befehlszeiger umgebrochen, sodass der "echte" Code ausgeführt werden kann.

Ein Beispielprogramm, das die Fibonacci-Zahlen berechnet (aus dieser Antwort ), ist:

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

Probieren Sie es online! Nachdem alle 1p-Befehle ausgeführt wurden, sieht die Codebox folgendermaßen aus:

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

Abgesehen vvon der ersten Zeile ist dies ein Standardprogramm von Fibonacci> <>.

Bash, 9 Zeichen

01456\$ '

Bash hat eine Syntax $'\nnn'zur Eingabe von Zeichen mit ihren oktalen ASCII-Werten. Wir können den evalBefehl in diesem Format als eingeben $'\145\166\141\154'. Wir wandeln zuerst das gewünschte Ergebnis in seine Oktalwerte um. Wir konvertieren dann alle Oktalwerte unter Verwendung von anderen Ziffern als 0, 1, 4, 5 und 6 in Ausdrücke, die unter Verwendung von $(())und Subtraktion evalzu den Oktalwerten ausgewertet werden, wobei an an die Front angehängt wird . In unserem letzten Schritt fügen wir einen weiteren hinzu evalund konvertieren die Klammern und das Minuszeichen in ihre Oktalwerte. Mit dieser Methode können wir jeden bash-Befehl ausführen, sodass diese Teilmenge vollständig ist.

Beispiel:

dc wird

$'\144\143' was wird

$'\145\166\141\154' \$\'\\144\\$((144-1))\' was wird

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

Vorfall , 2 Zeichen

Es spielt auch keine Rolle, welche zwei Zeichen Sie auswählen. Jede Kombination von zwei Oktetten ist in Incident Turing-vollständig.

Es ist viel schwieriger zu beweisen, als Sie vielleicht erwarten, und zum Zeitpunkt des Schreibens ist die Diskussionsseite über Incident auf Esolang dem Problem gewidmet. Ich werde jedoch versuchen, den einfachsten bekannten Beweis im Folgenden zusammenzufassen.

Vor dem Beweis einige Hintergründe. Incident ermittelt die im Programm verwendeten Token anhand der Quelle (ein Token ist eine Zeichenfolge, die genau dreimal in der Quelle vorkommt, keine Teilzeichenfolge eines anderen Tokens ist und sich nicht mit einem anderen potenziellen Token überschneidet). Daher kann jedes Programm durch Ändern der Tokens so gut wie für jeden Zeichensatz konvertiert werden. Die Sprache ist Turing-vollständig (und auch für die E / A vollständig!), obwohl es unglaublich schwierig ist, sie zu programmieren. "Alles", was Sie benötigen, ist eine Methode zum Codieren von Tokens, damit sie mit nur zwei Zeichen funktionieren.

Und jetzt folgt eine Zusammenfassung des Beweises (der von Ørjan, dem in Esolang ansässigen Mathematiker, gefunden wurde). Die Idee ist, dass wir ein Token mit zwei Kopien eines Zeichens (sagen wir 1) in einem großen Meer des anderen Zeichens (sagen wir) codieren 0. Der Abstand zwischen den 1s ist für jedes Token unterschiedlich, beträgt jedoch immer ein Vielfaches von 4. Für das Auffüllen zwischen den Token verwenden wir eine zusätzliche Liste von 0s mit einem 1in der Mitte, aber der Anzahl der Nullen auf jeder Seite des 1is Nicht ein Vielfaches von 4, sondern eine Zahl, die für das jeweilige Vorkommen des Programms eindeutig ist und an keiner anderen Stelle im Programm angezeigt wird. Das heißt, dass jeder1 …1innerhalb des Paddings kann immer nur zweimal vorkommen, wird also nicht Teil eines Tokens sein; Jedes beabsichtigte Token enthält genau zwei Einsen, und kein Schein-Token kann mehr als eine enthalten 1. Dann fügen wir der Seite nur noch ein Polster hinzu, um alle möglichen Token mit einer 1oder Nullen zu entfernen, 1indem wir mindestens vier Kopien davon hinzufügen.

Retina , 3 Zeichen

{`

und newline.

Zunächst benötigen wir newline, um Substitutionen durchführen zu können (erforderlich, es sei denn, wir möchten das gesamte Programm in eine Regex einpassen, für die mehr Zeichen erforderlich wären). und `und {sind die am wenigsten zeichenintensive Methode, um Schleifen auszuführen. Es stellt sich heraus, dass wir nichts anderes brauchen.

Unsere zu implementierende Zielsprache ist eine deterministische Variante von Thue (der Nichtdeterminismus ist für die Turing-Vollständigkeit nicht erforderlich; es ist möglich, ein Thue-Programm zu schreiben, das unabhängig von der verwendeten Auswertungsreihenfolge korrekt funktioniert). Die Grundidee ist zu kompilieren pattern::=replacementin

`pattern
replacement

(Dies ist eine direkte Retina-Übersetzung des Thues; alternativ können Sie, wenn Sie Retina kennen, aber nicht Thue, lernen, wie Thue funktioniert.) In Ausnahmefällen wird {`stattdessen das allererste Muster vorangestellt (um das gesamte Programm in eine Schleife zu platzieren; die Programme laufen weiter, bis keine Substitutionen mehr möglich sind, und dies bewirkt, dass die Retina auf die gleiche Weise funktioniert).

Das bedeutet natürlich, dass wir Thue Turing mit nur {und `in den Mustern und Ersetzungen als vollständig beweisen müssen , aber das ist einfach genug; Wir ersetzen ein Zeichen mit ASCII-Code n durch `, n + 1 {und ein anderes `. Es ist eindeutig unmöglich, dass ein Muster irgendwo anders als an den Zeichengrenzen übereinstimmt, sodass dies am Ende das Gleiche tut wie das ursprüngliche Programm.

Brachylog , 5 Zeichen

~×₁↰|

Diese Untermenge von Zeichen ermöglicht es uns, eine Version von Fractran zu implementieren, in der die einzigen Zahlen, die auftreten können, Produkte von Repunits sind (dh Produkte von Zahlen, die nur unter Verwendung der Ziffer 1 in Dezimalform geschrieben werden können). ~×(mit einer Ganzzahl als Index) dividiert den aktuellen Wert durch diese Ganzzahl, aber nur, wenn er genau dividiert (andernfalls "schlägt" er fehl und sucht nach einem anderen auszuführenden Fall; |trennt die Fälle).×lassen Sie uns mit einer ganzen Zahl multiplizieren. Mit können ~×₁|wir also einen Schritt einer Fractran-Ausführung implementieren. Dann ↰lassen Sie uns den Vorgang wiederholen und das gesamte Programm erneut mit dem neuen aktuellen Wert ausführen. Hier ist ein Beispiel eines sehr einfachen Fractran-Programms ( 11111111111111111111111/111), das in Brachylog übersetzt wurde.

Ist das Turing also komplett? Alles, was wir brauchen, um Fractran Turing vollständig zu machen, ist eine ausreichend große Menge von Primzahlen (genug, um einen Interpreter für eine Turing-vollständige Sprache in Fractran selbst zu schreiben). Es gibt fünf nachgewiesene und vier vermuteteRepunit-Primzahlen, möglicherweise auch solche, die noch nicht entdeckt wurden. Das ist eigentlich mehr, als wir in diesem Fall brauchen. Das Programm überprüft die Möglichkeiten von links nach rechts, so dass wir ein Prim als Befehlszeiger und zwei weitere als Zähler verwenden können, um die Vollständigkeit von Turing mit nur drei Primzahlen zu demonstrieren (eine gute Sache auch, weil wir die Repunits mit 2, 19 verwenden können , und 23 Ziffern, ohne auf die bewährten, aber ärgerlich großen Umformulierungen mit 317 oder 1031 Ziffern zurückgreifen zu müssen, die das Schreiben des Quellcodes erschweren würden). Dadurch ist es möglich, eine Minsky-Maschine mit zwei Zählern zu implementieren (ausreichend für Turing-Vollständigkeit).

So funktioniert die Zusammenstellung im Einzelnen. Wir werden die folgenden zwei Befehle für unsere Minsky-Maschinenimplementierung verwenden (dies ist Turing complete), und jeder Befehl wird eine Ganzzahl als Bezeichnung haben:

• Label L: Wenn der Zähler {A oder B} Null ist, gehe zu X. Andernfalls dekrementiere ihn und gehe zu Y.
• Label L: Inkrementzähler {A oder B}, dann gehe zu Z.

Wir wählen den Befehl, der ausgeführt werden soll, indem wir Potenzen von 11 im Nenner setzen, wobei die höchsten Potenzen an erster Stelle stehen. Der Exponent von 11 ist die Bezeichnung des Befehls. Auf diese Weise ist der erste übereinstimmende Bruch der aktuell ausgeführte Befehl (da die vorherigen nicht durch alle diese 11er dividiert werden können). Im Fall eines Dekrementierungsbefehls setzen wir für Zähler A bzw. B auch einen Faktor von 11111111111111111111111111111111111111111111 im Nenner und folgen ihm mit einem anderen Befehl ohne diesen Faktor. Der "Dekrement" -Fall wird durch den ersten Befehl implementiert, der "Null" -Fall durch den zweiten. In der Zwischenzeit wird das "goto" durch eine entsprechende Potenz von 11 im Zähler und das "Inkrementieren" durch einen Faktor von 1111111111111111111 oder 1111111111111111111 im Zähler behandelt.

Befunge-98, 3 Zeichen

Soweit ich weiß, sollte Befunge-98 vollständig sein, daher müssen wir nur zeigen, wie ein Befunge-98-Programm mit nur drei Zeichen erstellt werden kann. Meine anfängliche Lösung beruhte auf den folgenden vier Zeichen:

01+p

Wir können jede positive Ganzzahl auf den Stapel bekommen, indem wir mehrere 1Werte zusammen mit dem +Befehl addieren , und für Null verwenden wir einfach 0. Sobald wir die Möglichkeit haben, eine beliebige Zahl zu pushen, können wir die verwendenp Befehl (put) einen beliebigen ASCII-Wert an eine beliebige Stelle im Befunge-Spielfeld schreiben.

Wie Sp3000 hervorhob , kommt man jedoch nur mit den drei Zeichen zurecht :

1-p

Jede negative Zahl kann berechnet werden, indem mit begonnen 1und dann wiederholt subtrahiert wird 1(z. B. -3 wäre 11-1-1-1-). Dann kann jede positive Zahl durch Subtrahieren von 1-n von 1 dargestellt werden, wobei 1-n eine negative Zahl ist, mit der wir bereits umgehen können (z. B. 4 = 1 - (- 3))111-1-1-1-- ).

Wir können also unsere drei Zeichen verwenden, um eine Art Bootloader zu schreiben, der langsam den eigentlichen Code generiert, den wir ausführen möchten. Sobald dieser Loader die Ausführung beendet hat, springt er zum Anfang der ersten Zeile des Spielfelds, die zu diesem Zeitpunkt den Anfang unseres neu generierten Codes enthalten sollte.

Beispiel: Hier ist ein Bootloader, der den Befunge-Code generiert, der erforderlich ist, um 2 + 2 zu summieren und das Ergebnis auszugeben: 22+.@

Und für ein etwas komplizierteres Beispiel ist dies "Hallo Welt": "!dlroW olleH"bk,@

Rubin, 8 Zeichen

eval"<1+

Inspiriert von den Antworten von Python

Wie es funktioniert

• Mit eval kann ein beliebiger String ausgeführt werden.
• "<1+ ist die Mindestanzahl von Zeichen, die zum Erstellen einer Zeichenfolge erforderlich sind

Eine Zeichenfolge in Ruby kann mit der leeren Zeichenfolge als Ausgangspunkt erstellt und mit ASCII-Zeichen versehen werden. Beispiel:

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

ist eigentlich gleichbedeutend mit

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

welches den String auswertet

p"o"

OCaml, 9 Zeichen

fun->()`X

Diese Zeichen reichen aus, um den SKI Combinator Calculus in OCaml zu implementieren. Insbesondere können wir die Verwendung von Speicherplatz mit ausreichenden Klammern vermeiden. Leider erfordern Lambda-Ausdrücke in OCaml diefun Schlüsselwort, sodass eine knappere Lösung nicht möglich ist. Die gleichen Buchstaben können verwendet werden, um beliebige Variablennamen zu bilden, wenn jedoch komplexere Lambda-Ausdrücke gewünscht werden.

S Kombinator:

fun(f)(u)(n)->f(n)(u(n)) mit typ ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Kombinator:

fun(f)(u)->u mit typ 'a -> 'b -> 'b

Ich Kombinierer:

fun(f)->f mit typ 'a -> 'a

Wie von ais523 festgestellt, ist es nicht ausreichend, SKI einfach zu codieren. Hier ist eine Kodierung für Z unter Verwendung polymorpher Varianten zur Manipulation des Typsystems. Damit sollte meine Untergruppe vollständig sein.

Z Kombinator:

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

mit typ (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Stapelbasierte verkettete Sprachen, 4 Zeichen

Unterlast

():^

GolfScript

{}.~

CJam

{}_~

GS2

• Rücktaste, Tabulator, @Leerzeichen (Ich wusste, dass GS2 oft nicht druckbare Zeichen verwendet, aber das ist lächerlich ...)

dc (vorgeschlagen von @seshoumara)

[]dx

Unterlast wurde Turing-complete nur mit dem Einsatz von ():^(dank Esolangs ansässigem Mathematiker Ørjan) nachgewiesen. Der Beweis ist viel zu lang, um ihn hier zu erklären, aber wenn Sie interessiert sind, können Sie hier darüber lesen .

Die fraglichen Befehle sind ()(Code-Literal auf dem Stapel platzieren), :(oberes Stapelelement duplizieren) und ^(Stapeloberseite auswerten). Diese Befehle sind in stapelbasierten Sprachen (insbesondere in verketteten Sprachen) ziemlich verbreitet, und deshalb habe ich oben eine Auswahl davon gegeben. Diese Sprachen sind alle Turing-komplett in 4 Zeichen aus dem gleichen Grund wie Underload.

Leerzeichen, 3 Zeichen

STL

Sist Leerzeichen, Tist Tabulator und List Zeilenvorschub.

Schläger (Schema), 4 Zeichen

(λ)

Mit nur λ, Klammern und Leerzeichen können wir die Lambda-Kalkül-Teilmenge des Schemas direkt programmieren. Wir verwenden das λ-Zeichen für alle Bezeichner erneut, indem wir sie miteinander verknüpfen, um eine beliebig große Anzahl eindeutiger Bezeichner bereitzustellen.

Als Beispiel sei hier der klassische Omega-Kombinator genannt, der für immer eine Schleife bildet.

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

Python 3, 9 Zeichen

exc('%1+)

Siehe meine Python 2-Antwort für eine grundlegende Erklärung. Diese Antwort baut auf dieser auf.

Anstatt einfach die gleichen Zeichen wie in Python 2 mit dem Zusatz von zu verwenden (), können wir ein Zeichen löschen, da jetzt Klammern verwendet werden. Die Programme haben weiterhin die Grundform von

exec('%c'%stuff)

aber wir verkürzen die Programmlänge, indem wir +anstelle von verwenden -, und dann können wir entfernen, ~indem wir 1anstelle von verwenden 0. Anschließend können wir hinzufügen 1, 11und 111die erforderlichen ASCII-Werte abrufen.

Das Programm print()wird zum kürzesten:

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

Probieren Sie es online aus

Sie denken sich vielleicht, wie schafft man ein NUL-Byte ohne 0? Fürchte dich nicht, junge Heuschrecke! denn wir haben die Fähigkeit, auch %für Mathematik zu verwenden und mit Null zu erzeugen 1%1.

PHP 7, 6 Zeichen

'().;^

Die Idee ist, dass es möglich ist, beliebigen Code mit der folgenden Konstruktion auszuführen:

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

eval würde hier nicht funktionieren, weil es ein Sprachkonstrukt ist und nicht mit variablen Funktionen aufgerufen werden kann.

create_function und der Code könnte als eine Verkettung von bitweisen XORs verfügbarer Zeichen geschrieben werden:

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

Mit ().;^for <charX_Y>können wir bekommen

()./:;<=JKLMXY^_bcdepqvw

und einige nicht druckbare Zeichen. Es ist nicht genug, aber jetzt können wir auch 'eXp'()einige numerische Zeichen aufrufen und abrufen :

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

Es gibt uns 1, 2und 3(andere Zeichen durch XOR ignoriert werden, wenn die andere Zeichenfolge ein Zeichen lang ist). Aus können ().;^123wir nun den gesamten ASCII-Zeichensatz generieren.

Probieren Sie es online aus

Pyke, 5 Zeichen

0h.CE

Dies ist in der Lage, eine unendlich große Zahl zu erzeugen, sie in eine Zeichenkette umzuwandeln und sie dann als Pyke-Code auszuwerten.

Erklärung des Codes:

0- Addiere 0 zum Stapel. Dies ist erforderlich, um eine Nummer zu starten

h- Erhöhen Sie die Nummer zuvor. Wenn Sie dies beliebig oft wiederholen, können Sie Zahlen erstellen, die unendlich groß sind. Pyke unterstützt Bignums, wie es in Python geschrieben ist, das sie als Standard verwendet.

.C- Verwandle eine Zahl mit dem folgenden Algorithmus in einen String: ( Github-Link )

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

Zu diesem Zeitpunkt können wir in Pyke eine beliebige Anzahl von Zeichenfolgen und natürlichen Zahlen mit beliebigen Werten erstellen. Zahlen können in der Form erstellt werden, die dem regulären Ausdruck entspricht, 0(h)*und Zeichenfolgen können mit erstellt werden 0(h)*.C. Sie können miteinander verwoben werden, um eine beliebige Mischung aus Zeichenfolgen und ganzen Zahlen zu erstellen.

E- einen String als Pyke-Code auswerten. Dies verwendet die gleiche Umgebung wie der Pyke-Code, der bereits ausgeführt wird, sodass Dinge wie die Eingabe geteilt werden.

Versuchter Beweis, dass Pyke Turing Complete ist.

Eine der einfachsten Möglichkeiten, eine Sprache vollständig darzustellen, ist die Implementierung von Brainf * ck. Dies ist in Pyke wahrscheinlich viel schwieriger als in vielen anderen Sprachen, da die Listen- und Wörterbuchoperationen so gut wie nicht vorhanden sind, da sie in dem Bereich, in dem Pyke ausgeführt werden soll, nicht benötigt werden: Code-Golf .

Zuerst erstellen wir einen Interpreter für brainf * ck und codieren ihn mit unserem obigen Algorithmus, um eine Zahl zu erstellen und diese Zahl dann mit 0und auszudrücken h. Wir erstellen dann den String, der den Code enthält, der genauso ausgeführt werden soll. Wenn wir es dabei belassen würden, hätten wir den Stapel als

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

Dies bedeutet, dass der Code in der entgegengesetzten Form vorliegen muss, da der Pyke-Stack als Erster an letzter Stelle steht.

Nun zum spaßigen Teil: dem Brainf * ck-Interpreter mit satten 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

Probieren Sie es hier aus!

Wenn Sie den Code in unvollständiger, aber bearbeitbarer Form ausprobieren möchten, ausprobieren probieren Sie ihn hier aus!

Um einen String in eine Zahl umzuwandeln, können Sie den folgenden Python-Code verwenden:

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

Die (fast) endgültige Lösung kann sein ausprobiert werden!

Erklärung des Brainf * ck-Interpreters

Lassen Sie uns zuerst das Programm in Teile trennen:

• Die Initialisierung:

Für den Fall, dass Sie nicht mehr weiterkommen möchten

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

• Die Hauptschleife:

Für den Fall, dass Sie nicht mehr weiterkommen möchten

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.

• Die Anleitungen
  • Aufwärts- / Abwärts:+-

Für den Fall, dass Sie nicht mehr weiterkommen möchten

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

• Eingabe ,:

Für den Fall, dass Sie nicht mehr weiterkommen möchten

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

• Ausgabe .:

Für den Fall, dass Sie nicht mehr weiterkommen möchten

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

• Verschiebung nach links / rechts <>:

Für den Fall, dass Sie nicht mehr weiterkommen möchten

~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

• Die Bedingungen [:

Für den Fall, dass Sie nicht mehr weiterkommen möchten

~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

- Und ] :

Für den Fall, dass Sie nicht mehr weiterkommen möchten

~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

Gestapelt, 5 Zeichen

{!n:}

Das ist überraschend kurz. Wenn Stacked jede der SKI-Kombinationen implementieren kann, ist Turing Complete. Rekapitulieren:

• I Kombinator - die Identitätsfunktion. x -> x
• K kombinator - die konstante funktion. x -> y -> x
• S Kombinator - die Substitutionsfunktion. (x, y, z) -> x(z)(y(z))

Ich kombiniere: {!n}

Nun zu den gestapelten Details. {! ... }ist ein n-Lambda. Es ist eine unäre Funktion, deren Argument implizit ist n. Dann wird der letzte Ausdruck von der Funktion zurückgegeben. Somit {!n}ist eine Funktion, die ein Argument annimmt nund ergibt n.

K-Kombinator: {!{:n}}

Nun {:...}ist eine Funktion, die keine Argumente akzeptiert und zurückgibt .... Wenn wir dies mit unserer n-Lambda-Formation kombinieren, erhalten wir

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

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

Ok, das sieht etwas komplizierter aus. Ein Lambda benötigt also Argumente, die durch nicht identifizierende Zeichen getrennt sind. Das Lambda im Header ist also gleichbedeutend mit:

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

Dies ist eine Lambda , die drei Argumente übernimmt, n, nn, und nnn. Lassen Sie uns ersetzen diese mit x, yund zfür Klarheit:

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

Die beiden {!n}!sind nur Identitätsfunktionen, um erneut Leerzeichen zu vermeiden, wobei !"Ausführen" bedeutet. Also nochmal, Reduzierung:

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

Mit einer Erklärung:

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

Und deshalb ist dies der S-Kombinator.