Beim Entwerfen einer Sprache ist es sehr wichtig festzustellen, ob eine Sprache vollständig ist. Es ist auch eine ziemlich schwierige Aufgabe für viele esoterische Programmiersprachen, aber lassen Sie es uns noch ein bisschen besser angehen. Lassen Sie uns einige Programmiersprachen erstellen, die so schwer zu beweisen sind, dass selbst die besten Mathematiker der Welt sie nicht beweisen können. Ihre Aufgabe ist es, eine Sprache zu entwickeln und zu implementieren, deren Turing-Vollständigkeit auf einem großen ungelösten Problem in der Mathematik beruht .
Regeln
Das von Ihnen gewählte Problem muss mindestens 10 Jahre zurückliegen und zum Zeitpunkt der Veröffentlichung dieser Frage ungelöst sein. Es kann jede nachweisbare Vermutung in der Mathematik sein, nicht nur eine der auf der Wikipedia-Seite aufgelisteten .
Sie müssen eine Spezifikation der Sprache und eine Implementierung in einer vorhandenen Sprache bereitstellen.
Die Programmiersprache muss genau dann vollständig sein, wenn die Vermutung zutrifft. (oder nur wenn die Vermutung nicht zutrifft)
Sie müssen einen Beweis beifügen, warum Turing aufgrund der gewählten Vermutung vollständig oder unvollständig wäre. Sie können beim Ausführen des Interpreters oder des kompilierten Programms den Zugriff auf den unbegrenzten Speicher übernehmen.
Da wir uns mit der Vollständigkeit von Turing befassen, ist I / O nicht erforderlich. Das Ziel ist jedoch, die interessanteste Sprache zu erstellen, damit dies hilfreich sein kann.
Dies ist ein Beliebtheitswettbewerb , bei dem die Antwort mit den meisten Stimmen gewinnt.
Zielkriterien
Was soll eine gute Antwort tun? Hier sind einige Dinge, auf die Sie bei der Abstimmung achten müssen, die jedoch technisch nicht erforderlich sind
Es sollte kein einfacher Patch einer vorhandenen Sprache sein. Das Ändern einer vorhandenen Sprache, um sie den Spezifikationen anzupassen, ist in Ordnung, aber das Korrigieren einer Bedingung wird nicht empfohlen, da dies langweilig ist. Wie von ais523 im neunzehnten Byte gesagt:
Ich ziehe es vor, die Gimmicks meiner Esolangs fester in die Sprache zu verankern
Es sollte als eigenständige esoterische Sprache interessant sein.
quelle
Antworten:
Legendre
Diese Sprache ist nur dann vollständig, wenn die Vermutung von Legendre falsch ist, dh es gibt eine ganze Zahl n> 0, so dass es keine Primzahlen zwischen n ^ 2 und (n + 1) ^ 2 gibt. Diese Sprache wurde von Underload inspiriert, unterscheidet sich jedoch in mancher Hinsicht erheblich davon.
Programme in Legendre bestehen aus einer Reihe positiver Ganzzahlen (0 ist besonders verboten, da es im Wesentlichen den gesamten Zweck der Sprache negiert). Jede Ganzzahl entspricht einem Basisbefehl in Legendre oder einem potenziellen benutzerdefinierten Befehl. Welchem Befehl er zugewiesen wird, hängt von der Anzahl der Primzahlen zwischen seinem Quadrat und der nächsten Ganzzahl ab (entspricht der OEIS-Sequenz A014085 ).
Die Sprachbefehle modifizieren einen Stapel, der beliebig große positive ganze Zahlen enthalten kann. Wenn der Stapel jemals 0 enthält, wird die 0 sofort entfernt. Im Detail sind die Befehle:
2 (kleinste Ganzzahl, die diesen Befehl erzeugt: 1): Schieben Sie die nächste Ganzzahl im Programm auf den Stapel.
3 (kleinste produzierende Ganzzahl: 4): Füge die oberste Ganzzahl in den Stapel ein und führe den dazugehörigen Befehl aus.
4 (kleinste: 6): Pop die oberste Ganzzahl. Wenn es 1 war, erhöhen Sie die oberste Ganzzahl auf dem Stapel.
5 (10): Vertausche die beiden obersten Stapelgegenstände.
6 (15): Verringert die oberste Ganzzahl auf dem Stapel. Wenn dies zu 0 führt, platzieren Sie die 0 und verwerfen Sie sie.
7 (16): Duplizieren Sie die oberste Ganzzahl auf dem Stapel.
8 (25): Die Ausführung anhalten und den Stapelinhalt drucken.
Dies ist der grundlegende Befehlssatz, der nichts Interessantes kann, geschweige denn eine Schleife. Es gibt jedoch einen anderen Befehl, auf den nur zugegriffen werden kann, wenn sich Legendres Vermutung als falsch herausstellt.
Wenn dieser Befehl irgendwie zugänglich ist, wird die Sprache zu Turing-complete, da man eine Minsky-Maschine darin simulieren kann.
Wenn der Befehl 8 ausgeführt wird oder das Programmende erreicht ist, wird das Programm beendet und das (Unicode-) Zeichen, das jeder Ganzzahl auf dem Stapel entspricht, wird gedruckt.
Beispielprogramme
Dieses einfache Programm drückt die Zahl 2, dann 3 und schließlich eine 10, bevor eine 4 (Befehl: 3) ausgeführt wird, wodurch die 10 (Befehl: 5) abgesetzt und ausgeführt wird, wobei die 2 und 3 vertauscht werden.
Dieses Programm demonstriert die Verwendung der indirekten Entsprechung von Ganzzahlen zu Befehlen. Zuerst wird eine 5 gedrückt, dann eine 15 und eine 1, wobei drei verschiedene Methoden zum Codieren des 2-Befehls verwendet werden. Dann wird die 1 getoppt und als Ergebnis wird die 15 zu einer 16 inkrementiert und schließlich ausgeführt. Das Programm endet mit zwei Instanzen der Nummer 5 auf dem Stapel.
Dieses Programm demonstriert die Verwendung des Befehls 0 unter Verwendung von? als Platzhalterzahl. Das Programm speichert zuerst '1 5' in der Funktion 9, dann '15 31' in 10, bevor die Funktion 9 (unter Verwendung von 24) ausgeführt wird, die 5 auf den Stapel schiebt, und diese wiederholt dekrementiert, bis sie 0 erreicht und entfernt wird . Dann stoppt das Programm.
Minsky-Maschine
Um eine Minsky Maschine zu Legendre - Code zu konvertieren, das 0 Befehl muss verwendet werden. Da auf diesen Befehl nur zugegriffen werden kann, wenn die Vermutung von Legendre falsch ist, habe ich einen Platzhalter verwendet? stattdessen.
Beachten Sie, dass alle Minsky-Maschinenbefehlszeilennamen Ganzzahlen mit unterschiedlichen A014085-Entsprechungen voneinander und von den Basisbefehlen sowie 24 (9) und 31 (10) haben müssen.
Initialisierung: x INC (A / B) y:EIN:
B:
x DEZ (A / B) yz:EIN:
B:
x HALT:Um das endgültige Programm zu erstellen, hängen Sie alle Teile an (wobei x, y, z durch ihre Gegenstücke ersetzt werden) und fügen Sie eine einzelne Ganzzahl hinzu, um die erste Anweisung in der Kette zu starten. Dies sollte die Turing-Vollständigkeit der Sprache beweisen, falls die Vermutung von Legendre durch ein Gegenbeispiel als falsch erwiesen wird.
Dolmetscher
Dieser Interpreter ist in Python (3) geschrieben und wurde an allen drei obigen Beispielen getestet. Verwenden Sie die Flags -a / - allowZero, um zuzulassen? Zu verwenden ist -f / - file, um Code direkt aus einer Datei auszuführen, und -s / - stackOut, um den Stack stattdessen als Python-Liste auszugeben. Wird keine Datei angegeben, wechselt der Interpreter in eine Art REPL-Modus, der am besten mit --stackOut verwendet wird.
quelle
Union geschlossen
Diese Programmiersprache ist vollständig, wenn die Vermutung der unionsgeschlossenen Mengen falsch ist.
Kontrollen
Liste der Befehle:
x ++ Inkrementiere x (INC)
x-- Dekrementiere x (DEC)
j (x, y) Füge den Befehlssatz x hinzu, wenn y 0 ist, um das Ende der Befehlswarteschlange zu erreichen
Alle Variablen werden mit 0 initialisiert
Syntax
Programme werden als eine Reihe von Befehlssätzen geschrieben.
Befehl1 Befehl2 Befehl3 ... Befehl1 Befehl2
...
...
Um festzustellen, ob das Programm unionsgeschlossen ist, berücksichtigt jede Menge nur die Liste der verschiedenen Befehle, die in der Menge
j (x, y)! = J (a, b)
+ (x)! = + (Y) enthalten sind.
Wenn ein Befehlstyp (+, -, j) in mindestens der Hälfte der Sätze vorkommt, hat dies keine Auswirkungen.
Programme können enden, wenn sich am Ende der Anweisungswarteschlange keine Anweisungen befinden
Endlosschleifen, einschließlich der leeren Schleife, können mit j (x, y) erreicht werden
Dolmetscher
Code-Snippet anzeigen
Vollständigkeit prüfen
Wenn alle drei Befehle, j (x, y), Inkrementieren und Dekrementieren, verfügbar sind, kann eine Minsky-Maschine simuliert werden.
Jede Menge mit nur j (x, y), die mit j (x, y) erreicht wird, ist HALT.
X ++ ist INC.
X-- ist DEC.
J (x, y) ist JZ
Wenn die Vermutung der Union Closed Sets korrekt ist, wird mindestens einer der drei Befehle immer deaktiviert, wodurch es unmöglich wird, dass diese Sprache vollständig ist.
quelle
Fermat-Primzahlen
Die Sprache funktioniert auf zwei potenziell unendlichen Bändern, auf denen an jeder Stelle des Bandes eine beliebige Ganzzahl gespeichert werden kann. Beide Bänder werden
-1
zu Beginn mit gefüllt . Es gibt auch zwei Bandköpfe, die auf beiden Bändern bei Position 0 beginnen.Der Interpreter liest zuerst die Eingabe und speichert die Werte ab Position 0 auf dem ersten (Daten-) Band.
Dann liest es das mitgelieferte Programm. Für jede Zahl, auf die es trifft, wird zuerst geprüft, ob der Wert eine Fermat-Primzahl ist oder nicht. Wenn ja, wird auf das zweite (Anweisungs-) Band geschrieben, welches Fermat-Prime es ist, andernfalls wird
-1
auf das Anweisungsband geschrieben.Überprüfen Sie als Nächstes den Wert am Anweisungszeiger und führen Sie einen der folgenden Schritte aus:
-1
oder weniger: Beenden Sie das Programm0
: Bewegen Sie das Datenband um eine Position nach links. Bewegen Sie das Anweisungsband um eine Position nach rechts1
: Bewegen Sie das Datenband um eine Stelle nach rechts. Bewegen Sie das Anweisungsband um eine Position nach rechts2
: Erhöhen Sie den Wert an der Position des Datenbands. Bewegen Sie das Anweisungsband um eine Position nach rechts3
: Verringern Sie den Wert an der Position des Datenbands. Bewegen Sie das Anweisungsband um eine Position nach rechts4
: Wenn der Wert an der aktuellen Position des Datenbands Null ist, schieben Sie das Anweisungsband nach rechts, bis Sie entweder einen übereinstimmenden5
(oder einen größeren) Wert auf dem Anweisungsband oder einen kleineren Wert als erreichen0
. Wenn es ein5
(oder größer) ist, bewegen Sie den Anweisungszeiger erneut nach rechts, wenn er kleiner0
ist, beenden Sie das Programm. Wenn der Wert der aktuellen Datenbandposition nicht Null ist, schieben Sie das Anweisungsband einfach um eins nach rechts5
oder mehr: Bewegen Sie den Anweisungszeiger nach links, bis Sie den entsprechenden4
Wert erreichen, oder Sie finden etwas weniger als0
. Beenden Sie in letzterem Fall das Programm.(Bei Übereinstimmung
5
(oder mehr) mit4
Werten bedeutet dies, dass bei der Suche nach dem richtigen Wert auf dem Anweisungsband immer dann, wenn es auf denselben Wert stößt wie der ursprüngliche Befehl (entweder5
(oder mehr) oder4
), die entsprechende Nummer übersprungen werden muss des anderen Wertes (4
oder5
(oder mehr) auf der Suche)Schleife, bis die Anweisung besagt, dass Sie das Programm beenden müssen.
Wenn das Programm beendet wird, geben Sie die Werte auf dem Datenband von der Position
0
bis zur ersten Bandposition aus, die einen-1
Wert enthält .Beweis
Beachten Sie, dass die Sprache im Wesentlichen einem E / A-freien Brainfuck-Interpreter zugeordnet
F_5
ist, in dem alle möglichen Schleifen ausgeführt werden müssen.Basierend auf der Fermat-Prim-Vermutung gibt es jedoch nur 5 Fermat-Primzahlen (
F_0
-F_4
). WennF_5
vorhanden, ist die Sprache Turing-vollständig, da wir wissen, dass Brainfuck Turing-vollständig ist. Ohne könnenF_5
Sie jedoch weder verzweigen noch schleifen und sind im Grunde genommen an sehr einfache Programme gebunden.Implementierung
(getestet mit ruby 2.3.1)
Beispiele:
Dies wird
H
(kurz fürHello World!
) mit einer neuen Zeile auf den Bildschirm schreiben:Speichern unter
example.fermat
und starten Sie es wie folgt (Hinweis: Sie müssen immer eine Eingabe haben):In diesem nächsten Beispiel wird eine einfache Caesar-Verschlüsselung durchgeführt, indem jeder Wert der Eingabe um eins erhöht wird. Sie müssen natürlich durch
?
die 5. Fermat-Primzahl ersetzen :Sie können ausprobieren, dass es funktioniert, indem Sie den Cheat-Modus aktivieren und
2 4 1 2 5 3
als Quellcode verwenden:quelle
5
. Ich hoffe sie haben eine gute Tastatur.Schwalben mit Kokosnuss v2
Da die vorherige Version Fehler aufwies, die sie für diesen Wettbewerb ungültig machten, und ich nicht möchte, dass die Upvotes der vorherigen Version für diese Version zählen, die sich erheblich unterscheidet, wird diese Version als neuer Beitrag übermittelt.
Diese Sprache ist nicht vollständig, wenn die Collatz-Vermutung für alle positiven ganzen Zahlen bewiesen werden kann. Ansonsten ist die Sprache Turing vollständig.
Diese Sprache basierte auf Kardinal .
Zunächst wird der contVal des Programms mit der Formel
contVal = sum (summe (ASCII-Werte der Zeile) * 2 ^ (Zeilennummer-1)) berechnet.
Als nächstes werden an jedem A oder E 2 Schwalben mit entgegengesetzter Richtung erzeugt und alle bedingten Turn-Anweisungen werden so eingestellt, dass sie auf die Initialisierung warten.
Schwalben, die an einem E erstellt wurden, werden nach links / rechts geleitet, und Schwalben, die an einem A erstellt wurden, werden nach oben / unten geleitet.
Schließlich führt der Code Schritte aus, bis alle Zeiger entfernt wurden oder contVal auf eins gefallen ist.
Bei jedem Schritt wird contVal% 2 == 0 durch 2 geteilt, andernfalls wird es mit drei multipliziert und mit eins inkrementiert.
Befehle:
0: Wert auf 0 setzen
+: Wert um 1
erhöhen>: Richtung nach rechts
ändern v: Richtung nach unten
ändern <: Richtung nach links
ändern ^: Richtung nach oben ändern
R: Nachfolgende Zeiger nach dem ersten Zeiger vergleichen mit dem Wert des erster Zeiger. Wenn gleich, fahren Sie geradeaus, sonst biegen Sie rechts ab.
L: Nachfolgende Zeiger nach dem ersten Zeiger vergleichen mit dem Wert des ersten Zeigers. Wenn gleich, geradeaus, sonst links abbiegen.
E: Den Zeiger duplizieren, aber in die Richtungen nach links und rechts zeigen
A: Den Zeiger duplizieren, aber in die Richtungen nach oben und unten zeigen
? : Entfernen Sie den Zeiger, wenn der Wert 0 ist
Code-Snippet anzeigen
Erläuterung:
Wenn die Collatz-Vermutung für alle positiven ganzen Zahlen bewiesen werden kann, ist die Dauer eines in dieser Sprache ausgeführten Programms begrenzt, da contVal immer gegen 1 konvergiert und damit das Programm beendet.
Ansonsten muss ich nur beweisen, dass diese Sprache die folgenden Funktionen implementieren kann
Inkrement: Wird durch +
Konstante dargestellt. 0
Wird durch 0 dargestellt. Variablenzugriff: Variablen werden als Zeiger während der Fahrt gespeichert.
Anweisungsverkettung: Durch Ändern der zurückgelegten Entfernung zu Operationen kann die Reihenfolge, in der Operationen ausgeführt werden, geändert werden.
For-Schleife: In dieser Sprache
fungiert als for-Schleife> zählt bis zu 1 (weiterer Code könnte zur Schleife hinzugefügt werden)
Ebenso der Code
Wirkt so lange wie möglich, bis der in der R-Schleife festgelegte bedingte Wert erreicht ist.
quelle
contVal
bei jedem Schritt angewendet wird (und daher gibt es, wenn die Vermutung wahr ist, keine Endlosschleifen) - aber ich sehe das nirgends in der Antwort explizit. ??Perfektion / Unvollkommenheit
Puh, das hat Spaß gemacht.
Perfektion / Unvollkommenheit ist nur dann vollständig, wenn es unendlich perfekte Zahlen gibt. Wenn es welche gibt, nennt man sie Perfektion, und wenn es keine gibt, nennt man sie Imperfektion. Bis dieses Rätsel gelöst ist, enthält es beide Namen.
Eine perfekte Zahl ist eine Zahl, deren Teiler sich zur Zahl addieren, also ist sechs eine perfekte Zahl, weil
1+2+3=6
.Perfektion / Unvollkommenheit hat folgende Funktionen:
Perfektion / Unvollkommenheit ist stapelbasiert, mit einem Null-Index-Stapel.
Befehle:
p(x, y)
: schiebt x in die y-te Position zum Stapel.z(x, y)
: drückt x in der y-ten Position auf den Stapel, entfernt das, was vorher in der y-ten Position warr(x)
: Entfernt den x-ten Gegenstand vom Stapelk(x)
: Gibt das x-te Element auf dem Stapel zurücka(x, y)
: fügt x und y hinzu. Bei Verwendung mit Zeichenfolgen werden diese in der Reihenfolge xy zusammengefasst.s(x, y)
: subtrahiert y von x. Entfernt mit Strings das letzte len (y) von xm(x, y)
: multipliziert x und y. Bei Verwendung mit Zeichenfolgen wird x mal len y multipliziert.d(x, y)
: dividiert x durch yo(x)
: druckt xi(x, y)
: Wenn x true ergibt, führt es die Funktion y ausn()
: gibt den Zähler zurück, auf den der Codeblock aufgerufen wird.q()
: gibt die Länge des Stapels zurückt()
: Benutzereingabee(x, y)
: Wenn x eine Ganzzahl ist und x und y denselben Wert haben, wird 1 zurückgegeben. Wenn y eine Zeichenfolge ist, wird die Länge von y abgerufen. Wenn x eine Zeichenfolge ist, konvertiert es y in eine Zeichenfolge und überprüft, ob sie identisch sind. Wenn dies der Fall ist, wird 1 zurückgegeben. Andernfalls wird 0 zurückgegeben.l(x, y)
: Wenn x größer als y ist, wird 1 zurückgegeben. Wenn eine Zeichenfolge vorhanden ist, wird die Länge der Zeichenfolge verwendet.b()
: stoppt das Programm.c(x, y)
: Läuft x, dann y.Um das Äquivalent zu einem Python zu erhalten
and
, multiplizieren Sie die beiden Werte. Füror
, fügen Sie die Werte und fürnot
subtrahieren Sie den Wert von 1. Das funktioniert nur , wenn der Wert 1 oder 0 ist, die durch Teilen der Zahl von selbst erreicht werden kann.Datentypen: Ganzzahlen und Zeichenfolgen. Zeichenfolgen werden mit gekennzeichnet
''
, und alle nicht ganzzahligen Zahlen werden gerundet.Syntax:
Code besteht aus verschachtelten Funktionen innerhalb von zehn
{}
Sekunden. Zum Beispiel kann ein Programm , das würde sich mit den Eingängen und ausdrucken würde hinzugefügt:{o(a(t(), t()))}
. Im Hintergrund des Programms befindet sich ein Zähler, der bei 0 beginnt und bei jeder Ausführung eines Codeblocks um 1 fortschreitet. Der erste Codeblock läuft um0
und so weiter. Sobald die zehn Codeblöcke ausgeführt sind, wird der sechste jedes Mal ausgeführt, wenn der Zähler eine perfekte Zahl erreicht. Sie müssen nicht alle zehn Codeblöcke haben, damit das Programm funktioniert, aber Sie benötigen 7, wenn Sie eine Schleife erstellen möchten. Um besser zu verstehen , wie diese Sprache funktioniert, führen Sie das folgende Programm, das den Zähler druckt jedes Mal , wenn der Zähler eine perfekte Zahl erreicht:{}{}{}{}{}{}{o(n())}
.Den Interpreter finden Sie hier: repl.it/GL7S/37 . Wählen Sie entweder 1 aus, und geben Sie Ihren Code im Terminal ein, oder fügen Sie Ihren Code in die
code.perfect
Registerkarte ein und wählen Sie 2, wenn Sie ausgeführt werden. Es macht Sinn, wenn Sie es versuchen.Nachweis der Turing-Vollständigkeit / Mangel an Turing-Vollständigkeit.
Gemäß diesem Artikel über den Austausch von Software-Engineering-Stapeln muss ein Turing-Abschluß in der Lage sein, eine Form der bedingten Wiederholung des Sprungs zu haben und einen Weg zum Lesen oder Schreiben des Speichers zu haben. Es kann Speicher in Form des Stapels lesen / schreiben und es kann eine Schleife ausführen, da der sechste Codeblock jedes Mal ausgeführt wird, wenn der Zähler eine perfekte Zahl erreicht. Wenn es unendlich viele perfekte Zahlen gibt, kann es eine Endlosschleife geben, und Turing ist abgeschlossen. Andernfalls ist dies nicht der Fall.
Self Bitwise Cyclic Tag-Interpreter, der 5 Zeichen (1 oder 0) als Eingabe akzeptiert:
Es kann erweitert werden, um eine beliebige Anzahl von Zeichen als Eingabe zu verwenden. Es könnte unendlich viele Eingaben erfordern, aber nur, wenn es unendlich perfekte Zahlen gibt!
quelle
Sohlen
Diese Programmiersprache ist vollständig, wenn die Scholz-Vermutung wahr ist.
Ich habe diese Sprache geschrieben, weil @SztupY sagte, dass es keine Ergebnisse geben würde, bei denen davon ausgegangen wird, dass die Vermutung wahr ist, dass Turing vollständig ist
Liste der Befehle
Mit diesen Befehlen kann diese Sprache eine Minsky-Maschine simulieren
Dolmetscher
Ich würde empfehlen, dies nicht auszuführen. Es verwendet eine außerordentlich langsame Methode zur Überprüfung der Additionskette.
Code-Snippet anzeigen
Vollständigkeit prüfen
Die Sprache verwendet einen Zähler für die Anzahl der ausgeführten Befehle, die sie anhand der Scholz-Vermutung überprüft, um die Vollständigkeit der Sprache zu ändern.
Wenn die Scholz-Vermutung wahr ist, funktioniert dieses Programm genau wie eine normale Minsky-Maschine mit
Increment
Decrement
Jump, wenn Zero
Halt
Wenn jedoch die Scholz-Vermutung falsch ist, erreicht der Zähler irgendwann einen Wert, für den die Scholz-Vermutung nicht gilt. Da die Sprache so konzipiert wurde, dass sie bei Erreichen einer Zahl beendet wird, bei der die Scholz-Vermutung falsch ist, wird das Programm jedes Mal beendet, nachdem so viele Befehle ausgeführt wurden. Daher haben alle Programme eine begrenzte Länge. Da dies nicht mit den Anforderungen für die Vollständigkeit der Sprache übereinstimmt,
Die Sprache wäre nicht vollständig, sollte die Scholz-Vermutung falsch sein
quelle
Verlobt
Verlobter Github .
Die Readme-Datei und die Spezifikation befinden sich auf dem Github unter "README.txt".
Im Allgemeinen besteht ein Verlobungsprogramm aus Linienpaaren, deren Länge aus unterschiedlichen Twin-Prim-Paaren oder Verlobungspaaren besteht (es können keine Duplikate auftreten). Das Programm wird ausgeführt, indem "biegsame Teilmengen" der ersten Zeile in dem Paar innerhalb der zweiten Zeile gefunden werden. Die Anzahl solcher Teilmengen, kombiniert mit dem Abstand zwischen der ursprünglichen zweiten Zeile und der zweiten Zeile ohne die biegsamen Teilmengen, bestimmen den auszuführenden Befehl.
Ich werde den Beweis für diesen Beitrag extrahieren:
quelle
b
. Dies interpretiert ein BF-Programm, das dahinter steht, wieb+++++.
. Die Größe des Programms ist jedoch auf 10 Zeichen begrenzt. Während es BF interpretieren kann, kann es nicht alle Programme berechnen, die eine Turing-Maschine kann.Einvernehmliche Parität
Diese Sprache basiert darauf, ob es einvernehmliche Zahlen mit entgegengesetzter Parität gibt .
Befehle
Kontrollfluss
Das Programm wechselt wiederholt von links nach rechts, bevor es zum Start zurückkehrt. Wenn es auf ein "j" stößt, überprüft es den Wert, um festzustellen, ob Zeilen geändert werden sollen. Wenn es sich bei der Zahl um eine freundliche Zahl mit entgegengesetzter Parität zu ihrer Übereinstimmung handelt, wird sie um eine Zeile nach unten verschoben (Schleife nach oben). Wenn es sich bei der Zahl um eine freundliche Zahl handelt, wird sie um eine Zeile nach oben verschoben, sofern sie nicht bereits in der oberen Zeile enthalten ist.
Das Programm kann nur beendet werden, wenn das Programm in einer Zeile außerhalb der obersten Zeile ein x erreicht.
Vollständigkeit prüfen
Mit diesem Programm kann eine Minsky-Maschine simuliert werden, vorausgesetzt, es gibt ein Paar von befreundeten Zahlen mit entgegengesetzter Parität.
j, {und} können verwendet werden, um JZ (r, x) zu simulieren, obwohl nach gütlichen Zahlen anstatt nach Null gesucht wird.
+ ist INC (r)
- ist DEC (r)
x ist HALT
Wenn Sie die erste Zeile nicht verlassen können, tun die Befehle x und} nichts. Dies führt dazu, dass das Programm nicht in den Status HALT wechseln kann, es sei denn, es ist ein leeres Programm. Daher wäre unter der Beschreibung, dass die Vollständigkeit von Turing einen HALT-Zustand erfordert , die Sprache Turing unvollständig.
Dolmetscher
Code-Snippet anzeigen
quelle
Neue Zeile
Disclaimer: Es ist ein bisschen chaotisch und ziemlich einfach. Dies ist die erste Sprache, die ich jemals geschrieben habe, und die Vermutung ist die einzige, die ich verstanden habe. Ich weiß, dass ein anderer Benutzer eine längere Antwort mit derselben hatte, aber ich habe mich trotzdem dazu entschlossen, diese zu schreiben.
Um in Newline zu schreiben, müssen Sie viel Zeit und Zeilenumbrüche haben (
\n
). Dies geht von der Legendre-Vermutung aus, dass sie wahr ist. Jeder Operator muss auf eine Zahl in der Legendre-Vermutung fallen, die wir mit n = 1 beginnen. Jedes Mal, wenn Sie einen Operator haben, nehmen Sie die Menge von \ n und stecken Sie diese in die Legendre-Vermutung und erhalten die Reichweite der nächsten Primzahl von \ Es muss n geben. Zu Beginn\n\n
wechseln Sie zu einem Operator, dann zu einem\n
anderen Operator. Wir haben 3 neue Zeilen. Der nächste ist 5, also addieren Sie\n\n
und stellen Sie sicher, dass die letzte Operatorzeile die richtige Anzahl von Zeilenumbrüchen enthält, die Sie auf einer Primzahl haben, die der Legendre-Vermutung entspricht, die wir gestartet haben.Zahlen (das Array) sind wie die Variablen. Jedes Mal, wenn ein Operator ausgeführt wird (der Zahlen verwendet), wird er inkrementiert.
Solange wir unbegrenzt Primzahlen haben, die den Regeln folgen, hat diese Sprache kein endliches Band.
Minsky-Maschine
Wie es funktioniert:
Probieren Sie es auf KhanAcademy aus .
quelle
Taggis
Taggis ist eine Sprache, die auf Tag-Systemen basiert .
Die Vollständigkeit von Taggis basiert auf der Collatz-Vermutung
Syntax
Die Syntax eines Taggis-Programms besteht einfach aus drei Zeichenfolgen (Produktionsregeln), die vollständig aus den durch Leerzeichen getrennten Buchstaben a, b und c bestehen.
Ausführung
Der einzige Programmstatus von Taggis ist eine Zeichenfolge, die aus den gleichen drei Zeichen besteht.
Taggis implementiert ein TS (3, 2) -Tag-System, bei dem in jedem Schritt die ersten zwei Buchstaben des aktuellen "Tags" entfernt werden und dem allerersten Buchstaben, der sich in diesem entfernten Teil befand, die entsprechende Produktionsregel an das Ende von angehängt wird die Saite.
Das Taggis-Programm
bc a aaa
implementiert beispielsweise das 3n + 1-Problem, bei dem Iterationen durch eine entsprechende Anzahl vona
s dargestellt werden und der 3n + 1-Schritt durch (3n + 1) / 2 [1] ersetzt wird, was zur Programmausgabe führt:Vollständigkeit prüfen
Natürlich mag dieses einfache System viel zu einfach erscheinen, um die Turing-Vollständigkeit zu emulieren, aber es stellt sich heraus, dass jede Turing-Maschine mit 2 Symbolen (eine Klasse, die Universalmaschinen umfasst) in ein Tag-System mit 2 entfernten Zeichen vom Kopf konvertiert werden kann. und 32 * m Produktionsregeln, wo
m
ist die Anzahl der Zustände in der Turing-Maschine.Die kleinste bekannte Universal-Turing-Maschine mit nur 2 Symbolen verwendet 18 Zustände und somit enthält das entsprechende Tag-System satte 576 Produktionsregeln [2].
Die rechnerische Klasse der Menge aller Tag-Systeme mit 3 Produktionen und 2 entfernten Symbolen ist jedoch an die Collatz-Vermutung gebunden [2]. Wenn sich die Collatz-Vermutung als falsch herausstellt, ist Taggis vollständig. Ansonsten basiert es auf einem weiteren ungelösten Problem in der Mathematik, eine kleinere Turing-Maschine zu finden als
Dies entspricht der ursprünglichen Collatz-Funktion, da 3n + 1 einer ungeraden
n
immer gerade ist und daher die Division automatisch angewendet werden kannTag-Systeme und Collatz-ähnliche Funktionen, Liesbeth De Mol ,
quelle