Flucht aus der Plane (Cops)

9

Dies ist eine Herausforderung für die darauf basiert, Sprachen zu definieren und zu beweisen, dass sie vollständig sind.

Dies ist der Thread der Polizei. Der Räuberfaden ist hier .

Cops

Als Polizist bereiten Sie zwei Dinge vor:

  • Eine formale Spezifikation einer Programmiersprache oder eines anderen Computersystems. (Computersysteme sind unten definiert.)

  • Ein Beweis dafür, dass Ihr System vollständig ist, gemäß der etwas strengen Definition unten.

Sie werden Ihre Spezifikation Ihrer Sprache veröffentlichen und die Räuber werden versuchen, sie zu "knacken", indem sie ihre Turing-Vollständigkeit beweisen. Wenn Ihre Einreichung nicht innerhalb einer Woche geknackt wird, können Sie sie als sicher markieren und Ihren Beweis veröffentlichen. (Ihre Antwort kann ungültig werden, wenn jemand einen Fehler in Ihrem Beweis findet, es sei denn, Sie können ihn beheben.)

Dies ist ein , daher ist der Gewinner die Antwort, die die meisten Stimmen hat und die nicht geknackt oder ungültig ist. Die Herausforderung ist offen - ich werde keine Antwort annehmen.

Für diese Herausforderung wird ein Rechensystem als vier Dinge definiert:

  • Ein "Programmsatz" P. Dies ist eine zählbar unendliche Menge, z. B. Zeichenfolgen, Ganzzahlen, Binärbäume, Konfigurationen von Pixeln in einem Raster usw. (siehe jedoch die technische Einschränkung unten.)

  • Eine "Eingabemenge" I, die ebenfalls eine zählbar unendliche Menge sein wird und nicht dieselbe Menge sein muss wie P(obwohl dies möglich ist).

  • Ein „output set“ O, das wird in ähnlicher Weise eine countably unendliche Menge sein , und kann oder kann nicht die gleiche sein wie PoderI

  • Eine deterministische, mechanistische Prozedur zum Erzeugen einer Ausgabe ovon Programm pund Eingabe i, wo p, iund osind Mitglieder P, Iund Ojeweils. Dieses Verfahren sollte so beschaffen sein, dass es im Prinzip auf einer Turing-Maschine oder einem anderen abstrakten Berechnungsmodell implementiert werden kann. Abhängig vom Programm und seiner Eingabe kann die Prozedur natürlich nicht angehalten werden.

Die Sets P, Iund Omuss so beschaffen sein , dass man sie als Zeichenkette in einer berechenbaren Weise ausdrücken kann. (Für die meisten vernünftigen Entscheidungen spielt dies keine Rolle. Diese Regel verhindert, dass Sie seltsame Sätze auswählen, z. B. den Satz von Turing-Maschinen, die nicht anhalten.)

Die Vollständigkeit wird wie folgt definiert:

  • Für jede berechenbare Teilfunktion fvon Ibis Ogibt es ein Programm, pin Pdem gegeben pund eingegeben wird i, die Ausgabe ist, f(i)wenn f(i)sie einen Wert hat. (Andernfalls wird das Programm nicht angehalten.)

Das Wort "berechenbar" in der obigen Definition bedeutet "kann mit einer Turing-Maschine berechnet werden".

Beachten Sie, dass weder Regel 110 noch bitweise zyklische Tags nach dieser Definition Turing-vollständig sind, da sie nicht die erforderliche Eingabe-Ausgabe-Struktur haben. Der Lambda-Kalkül ist Turing vollständig, solange wir die Kirchenzahlen definieren Iund Osein sollen . (Es ist nicht Turing-vollständig, wenn wir Lambda-Ausdrücke im Allgemeinen nehmen und sein.)IO

Beachten Sie, dass Sie keine Implementierung Ihrer Sprache bereitstellen müssen, aber Sie können gerne eine in Ihre Antwort aufnehmen, wenn Sie möchten. Sie sollten sich jedoch nicht auf die Implementierung verlassen, um die Sprache in irgendeiner Weise zu definieren - die Spezifikation sollte an sich vollständig sein, und wenn es einen Widerspruch zwischen der Spezifikation und der Implementierung gibt, sollte dies als Fehler in der Implementierung behandelt werden.

Nathaniel
quelle
9
Sorry Leute, aber der Beliebtheitswettbewerb ist ein objektives Gewinnkriterium. Ein Pop-Con zu sein, ist keine Herausforderung außerhalb des Themas und hat es nie getan. Die jüngste Metadiskussion hat einen Konsens von +27 dafür. Obwohl Sie fünf es vielleicht vorziehen, anders zu sein, haben Sie wirklich kein Standbein. Da diese Frage gegen die vereinbarte Politik geschlossen wurde, beantrage ich die Wiedereröffnung.
Nathaniel
2
(Beachten Sie, dass WhatWizard es aus einem anderen Grund geschlossen hat.)
user202729
2
Bitte verwenden Sie keine engen Abstimmungen als Schaltfläche "Ich bin nicht einverstanden" oder "Ich mag das nicht". Enge Abstimmungen sind zur Durchsetzung der Site-Richtlinien zu verwenden. Wenn Sie mit einer Richtlinie nicht einverstanden sind, nehmen Sie sie als Meta - schließen Sie keine Herausforderungen, die im Konsens der Community themenbezogen sind.
Mego
1
@ Mego Ich habe dafür gestimmt, dies als zu weit gefasst zu schließen, aber ich denke auch, dass dies aufgrund unserer bestehenden Regeln für Pop-Cons nicht zum Thema gehört. Wir erwarten, dass Beliebtheitswettbewerbe eine "klare Spezifikation des Ziels, das erreicht werden muss" haben. Diese Frage ist auf kreativste Weise ein Do X. Mir ist klar, dass es kein anderes Ziel gibt, als eine gültige Antwort zu geben, und dass das Pop-Con-Tag nur angebracht ist, um es offen zu halten.
Ad-hoc-Garf-Jäger
2
@WhatWizard Das Ziel, das erreicht werden muss, ist, dass Turing nicht vollständig ist. Die Nicht-Offensichtlichkeit wird dadurch bewertet, dass sie nicht innerhalb einer Woche geknackt wird. Ist das nicht klar?
Nathaniel

Antworten:

10

Arithmetik mit verbundenen Augen

Möglicherweise eine relativ einfache Sprache, relativ gesehen. (Es gibt Grenzen, wie schwierig eine Sprache sein kann, weil ich sie selbst beweisen muss!)

Für diese Sprache ist der Programmsatz der Satz von Arithmetikprogrammen mit verbundenen Augen, wie im Abschnitt "Programm" unten angegeben, der Eingabesatz ist der Satz positiver Ganzzahlen und der Ausgabesatz ist der Satz von Ganzzahlen (der gesamte Satz, nicht nur die positiven ganzen Zahlen).

Diese Sprache ist ziemlich interessant - vielleicht sogar praktisch nützlich -, da sie einen mehr oder weniger vollständigen Mangel an Kontrollfluss aufweist und vollständig auf Berechnungen von Zahlen basiert, die Sie nicht sehen können. Dies macht es möglicherweise als Sprache für die Implementierung von Programmen in homomorphen Verschlüsselungssystemen nützlich .

Spezifikation

Arithmetik mit verbundenen Augen ist eine esoterische Programmiersprache mit den folgenden Spezifikationen:

Datenspeicher

Ein Status eines laufenden Arithmetikprogramms mit verbundenen Augen besteht aus sechs Variablen, von denen jede eine Ganzzahl speichern kann. (Es gibt keine Grenzen, wie groß oder klein diese Zahlen bekommen können, insbesondere können sie negativ werden .) Die Variablen werden genannt a, b, c, d, e, und i.

Zu Beginn des Programms werden ato einclusive jeweils auf 0 und iauf eine positive Ganzzahl aus Benutzereingaben initialisiert. (Wenn keine Eingabe verfügbar ist, iwird diese auf 1 initialisiert.)

Wenn das Programm die Ausführung beendet (dies kann nur aufgrund der Division durch Null erfolgen), wird der Wert iunmittelbar vor dem Versuch der Division als Ausgabe des Programms verwendet.

Programm

Ein Arithmetikprogramm mit verbundenen Augen ist eine Liste von Befehlen, von denen jeder eine der folgenden Formen hat (wobei v durch einen beliebigen Variablennamen ersetzt werden kann, möglicherweise bei jeder Verwendung durch einen anderen Namen):

  • v = v + v
  • v = v - v
  • v = v * v
  • v = v / v

Man beachte , dass jeder Operand der Befehle muss eine Variable sein; Diese Sprache erlaubt nicht die Verwendung von Literal-Ganzzahlen.

Die Ausführung des Programms erfolgt durch Ausführen der einzelnen Befehle nacheinander, anschließendes Zurückschleifen zum Start und erneutes Ausführen der Befehle nacheinander ad infinitum (oder bis versucht wird, durch Null zu teilen, wodurch das Programm beendet wird). .

Jeder Befehl hat die gleiche Semantik, die Sie von der Notation erwarten würden, die sich nicht von der unterscheidet, die von den meisten praktischen Programmiersprachen verwendet wird: Die Werte der zweiten und dritten Variablen, die im Befehl angegeben sind, werden als arithmetische Operation (Addieren / Subtrahieren) verwendet / multiplizieren / dividieren jeweils für die vier Befehlsformen) wird auf sie angewendet und der resultierende Wert in der ersten Variablen gespeichert. Division ist hier eine ganzzahlige Division, die auf 0 gerundet wird.

Es gibt keinen anderen Kontrollfluss als den Programmausgang. Die Befehle werden immer nacheinander ausgeführt, bis eine Division durch Null (falls vorhanden) erfolgt und das Programm beendet wird. Insbesondere gibt es keine Möglichkeit, Variablen direkt zu lesen, sondern sie nur als Berechnungsquelle zu verwenden, deren Ergebnisse sich auf die Werte auswirken, die anderen Variablen zugewiesen wurden.

ais523
quelle
Können Sie überprüfen, ob meiner Antwort etwas fehlt?
user202729
@ user202729: (hier kommentieren, da ich dort nicht den Repräsentanten habe, um dort zu kommentieren) Sie können aus einem "Flip" und einem "Move if true" keinen "Move if false" simulieren, da Sie den Flip nicht rückgängig machen können nachdem Sie sich bewegen. Sie benötigen also eine andere Möglichkeit, um damit umzugehen (z. B. eine Möglichkeit, Tests umzukehren, die nicht schwierig sein sollte). Insbesondere ist dies jedoch ein Turing-Vollständigkeitsnachweis in Bezug auf das Stopp-Verhalten. Die Definition in der Frage erfordert jedoch, dass Sie auch E / A ausführen können. Sie müssen also beweisen, dass Sie dies tun können.
Ais523
Ich hoffe der E / A-Teil (jetzt) ​​ist in Ordnung. Was das andere Problem
betrifft, stelle
@ user202729: Es ist immer noch nicht ganz richtig (z. B. erfordert die Frage, dass Sie negative Zahlen ausgeben können, und Sie müssen auch den Zweck ändern, damit die Statusnummer i- die immer "halt" ist - nicht funktioniert Teil der Ausgabe sein), aber es ist nah genug, dass ich dies nicht als sicher markieren werde, da Sie bei ausreichender Zeit und ausreichender Klärung der Regeln eindeutig einen vollständigen Riss bekommen würden. Ich möchte diese technische Herausforderung nicht gewinnen.
Ais523
Dies liegt sehr nahe an den Einschränkungen, die de.ioccc.org/years-spoiler.html#1992_buzzard.1 verwendet. Diese Implementierung verwendet Ganzzahlen mit fester Größe und ist daher nicht Turing-vollständig, und diese ist in der Anzahl der Variablen, die Sie haben, stark eingeschränkt, aber ich denke, der Beweis ist dennoch ähnlich.
b_jonas