Eine Gesamtsprache, die nur eine Turing-Gesamtsprache interpretieren kann

16

Jede Sprache, die nicht vollständig ist, kann keinen Dolmetscher für sich selbst schreiben. Ich habe keine Ahnung, wo ich das gelesen habe, aber ich habe es einige Male benutzt. Es scheint, als ob dies zu einer Art "ultimativer" nicht-Turing-vollständiger Sprache führt; die, die nur könnenvon einer Turingmaschine interpretiert werden. Diese Sprachen wären nicht notwendigerweise in der Lage, alle Gesamtfunktionen von Naturmenschen zu Naturmenschen zu berechnen, noch wären sie notwendigerweise isomorph (das sind möglicherweise die letzten Sprachen A und B, so dass es eine Funktion F gibt, die A berechnen kann, B jedoch nicht). Agda kann Gödels System T interpretieren und Agda ist total, so dass eine solche ultimative Sprache strikt mächtiger sein sollte, als es scheint, als ob Gödels System T. Mir scheint, dass eine solche Sprache mindestens so mächtig ist wie Agda (obwohl ich keine Beweise habe, nur eine Ahnung).

Wurde in dieser Richtung geforscht? Welche Ergebnisse sind bekannt (ist nämlich eine solche "ultimative" Sprache bekannt)?

Bonus: Ich mache mir Sorgen, dass es einen pathologischen Fall gibt, bei dem Funktionen, die Godels System T noch nicht berechnen konnte, nur von einer Turing-Maschine interpretiert werden können, weil damit einige wirklich merkwürdige Funktionen berechnet werden können. Ist dies der Fall oder können wir wissen, dass eine solche Sprache alles berechnen kann, was Godels System T berechnen könnte?

Jake
quelle
2
Ihre Aussagen sind aufgrund der Art und Weise, wie Sie die Terminologie verwenden, verwirrend. Anstatt sich auf die Terminologie zu verlassen, versuchen Sie, Ihre Frage mathematisch genau und klar zu formulieren, damit wir Ihre Frage verstehen können. Was meinen Sie mit Programmiersprache im Kontext der Berechenbarkeitstheorie? Meinen Sie eine Aufzählung von berechenbaren Funktionen?
Kaveh
1
Meine Vermutung zu dem, was Sie lesen: Wenn eine Sprache stark genug ist und die universelle Funktion einer anderen Klasse von Funktionen enthält, kann sie die diagonale Funktion für diese Klasse definieren. Wenn es sich um eine Klasse von Gesamtfunktionen handelt, kann die Diagonalfunktion nicht in der Klasse enthalten sein.
Kaveh
Es wurde informell angegeben, wo ich es gefunden habe. Etwas im wahrsten Sinne des Wortes, was ich hier gegeben habe. Ich weiß auch nicht, wie ich das mathematisch ausdrücken soll. Nach einigem Lesen bin ich mir nicht sicher, was die "diagonale Funktion einer Funktionsklasse" ist. Ich denke, in Ihren Begriffen meine ich, dass "eine Klasse von Gesamtfunktionen keine eigene universelle Funktion enthalten kann" und ich denke, ich frage "für welche Klasse von Gesamtfunktionen C ist es der Fall, dass keine Klasse von Gesamtfunktionen die enthält universelle Funktion für C ". Wenn ich verstehe, was eine "universelle Funktion" ist, denke ich, dass das richtig ist.
Jake
1
Genau genommen ist dies keine Frage auf Forschungsebene. Warum ist das ein Community-Wiki? Oder ist es?
Andrej Bauer
"Es sieht so aus, als würde daraus eine Art" ultimative "nicht zutreffende vollständige Sprache entstehen; die eine oder die anderen, die nur von einer Turing-Maschine interpretiert werden können." Folgen Sie nicht dieser Behauptung, es scheint keine Folge zu sein. Was meinst du, warum scheint das so zu sein?
Freitag,

Antworten:

42

Dies ist eine schlecht formulierte Frage. Lassen Sie uns zunächst einen Sinn daraus ziehen. Ich werde es im Stil der Berechenbarkeitstheorie machen. Daher werde ich Zahlen anstelle von Zeichenfolgen verwenden: Ein Teil des Quellcodes ist eine Zahl und keine Zeichenfolge. Es spielt eigentlich keine Rolle, Sie können unten durch s t r i n g ersetzen .NstrichnG

Lassen Sie sein , Pairing - Funktion .m,n

Nehmen wir an, dass eine Programmiersprache durch die folgenden Daten gegeben ist:L=(P,ev)

  1. eine entscheidbare Menge von "gültigen Programmen" undPN
  2. ein berechenbarer und Teilfunktion .ev:P×NN

Die Tatsache, dass entscheidbar ist, bedeutet, dass es eine vollständig berechenbare Abbildung v a l i d gibt : N{ 0 , 1 }, so dass v a l i d ( n ) = 1Pveinlichd:N{0,1} . Informell sagen wir, dass es möglich ist, festzustellen, ob eine bestimmte Zeichenfolge ein gültiger Code ist. Die Funktion e v ist im Wesentlichen ein Interpreter für unsere Sprache: e v ( m , n ) führtbei Eingabe n denCode m aus- das Ergebnis kann undefiniert sein.veinlichd(n)=1nPevev(m,n)mn

Wir können nun einige Begriffe einführen:

  1. Eine Sprache ist total, wenn eine Gesamtfunktion für alle m P ist .nev(m,n)mP
  2. Eine Sprache interpretiert die Sprache L 2 = ( P 2 , e v 2 ), wenn es u P 1 gibt, so dass e v 1 ( u , n , m ) e v 2 ( n , m ) für alle n PL1=(P1,ev1) L2=(P2,ev2)uP1ev1(u,n,m)ev2(n,m)nPund . Hier ist u der Simulator für L 2 , der in L 1 implementiert ist . Es ist auch als Universalprogramm für L 2 bekannt .mNuL2L1L2

Andere Definitionen von " interpretiert L 2 " sind möglich, aber lassen Sie mich jetzt nicht darauf eingehen.L1L2

Wir sagen, dass und L 2 äquivalent sind, wenn sie sich gegenseitig interpretieren.L1L2

Es gibt die "mächtigste" Sprache von Turingmaschinen (die Sie als "Turingmaschine" bezeichnen), in der n N eine Kodierung einer Turingmaschine ist und φ ( n , m ) ist die partielle berechenbare Funktion, die "die mit n codierte Turing-Maschine bei Eingabe m ausführt ". Diese Sprache kann alle anderen Sprachen interpetieren, da wir vorausgesetzt haben, dass e v berechenbar ist.T=(N,φ)nNφ(n,m)nmev

Unsere Definition von Programmiersprachen ist sehr entspannt. Damit das Folgende durchgehen kann, benötigen wir drei weitere Bedingungen:

  • implementiert die Nachfolgerfunktion: es gibt s u c c P, so dass e v ( s u c c , m ) = m + 1 für alle m N ,LsuccPev(succ,m)=m+1mN
  • Implementiert die diagonale Funktion: es wird d i ein g P , so dass e v ( d i a g , m ) = m , m für alle m N ,LdicheinGPev(diag,m)=m,mmN
  • ist unter Zusammensetzung von Funktionen geschlossen: Wenn L Arbeitsgeräte f und g dann implementiert auch f g ,LLfgfg

Ein klassisches Ergebnis ist folgendes:

Satz: Wenn eine Sprache sich selbst interpretieren kann, ist sie nicht vollständig.

Beweis. Angenommen , ist das Universalprogramm für insgesamt Langauge L in realisiert L , das heißt für all m P und n N , E v ( u , m , n ) e v ( m , n ) . Als Nachfolger werden Diagonale und e v ( u , - ) in L implementiert , ebenso wie ihre Zusammensetzung k uLLmPnN

ev(u,m,n)ev(m,n).
ev(u,)L . Es gibt n 0P , so dass e v ( n 0 , k ) e v ( u , k , k ) + 1 , aber dann e v ( u , n 0 , n 0) e v (kev(u,k,k)+1n0Pev(n0,k)ev(u,k,k)+1 Da es keine Zahl gleich seinen eigenen Nachfolger ist, folgt, dass L nicht vollständig oder daß L nicht selbst interpretieren. QED.
ev(u,n0,n0)ev(n0,n0)ev(u,n0,n0)+1
LL

Beachten Sie, dass wir die Nachfolgekarte durch eine andere Karte ohne Fixpunkte ersetzen können.

Hier ist ein kleiner Satz, von dem ich denke, dass er ein Missverständnis beseitigen wird.

Satz: Jede Gesamtsprache kann von einer anderen Gesamtsprache interpretiert werden.

Beweis. Sei eine Gesamtsprache. Wir erhalten eine Summe L ', die L interpretiert, indem wir an L seinen Bewerter e v anschließen . Genauer gesagt, lassen P ' = { 0 , n | n P } { 1 , 0 } und definieren e v ' als e v ' ( b , n , mLLLLevP={0,nnP}{1,0}ev Offensichtlich L ' istweil insgesamt L total. Um diesesehen L ' können simulieren L nur nehmen u = 1 , 0

ev(b,n,m)={ev(n,m)if b=0,ev(m0,m1)if b=1 and m=m0,m1
LLLL , Da dann e v ' ( u , m , n ) e v ( m , n ) ,nach Bedarf. QED.u=1,0ev(u,m,n)ev(m,n)

Aufgabe: [hinzugefügt am 27.06.2014] Die oben konstruierte Sprache ist nicht kompositorisch abgeschlossen. Fixiere den Beweis des Theorems so, dass L ' die zusätzlichen Anforderungen erfüllt, wenn L dies tut.LLL

Mit anderen Worten, Sie brauchen nie die volle Leistung von Turing-Maschinen, um eine Gesamtsprache zu interpretieren - eine etwas leistungsstärkere Gesamtsprache L ' reicht aus. Die Sprache L ' ist strikt mächtiger als L, weil sie L interpretiert , aber L sich selbst nicht interpretiert.LLLLLL

Andrej Bauer
quelle
Wenn ich das Wiki-Kontrollkästchen aktiviert habe, war es unbeabsichtigt.
Andrej Bauer
2
Gibt es zusätzliche Möglichkeiten in Sprachen, bei denen Sie nicht sagen können, ob ein bestimmtes Programm gültig ist oder nicht?
Phylliida
3
@DaniPhye: Wenn die Sprachsyntax nicht halbentscheidbar ist, können Sie die Rechenleistung in der Syntax "verbergen". Beispielsweise könnten die Sprachregeln verlangen, dass jede Funktion mit einem Bit ausgestattet ist, das angibt, ob die Funktion vollständig ist. Wir könnten dann implementieren is_total, was ansonsten nicht zurechenbar ist, aber keine Auswertung implementieren (da Sie auch das Bit der resultierenden Funktion berechnen müssten). Im Allgemeinen würde ich sagen, dass es keine Programmiersprache ist, wenn Sie nicht einmal einen Parser dafür implementieren können.
Andrej Bauer
3
Wie geliert "Wenn eine Sprache sich selbst interpretieren kann, dann ist es nicht total" mit diesem Ergebnis: Ein Selbstinterpreter für F-Omega ?
Cactus
18

Jede Sprache, die nicht vollständig ist, kann keinen Dolmetscher für sich selbst schreiben.

Diese Aussage ist falsch. Betrachten Sie die Programmiersprache, in der die Semantik jedes Strings "Ignoriere deine Eingabe und halte sofort an" lautet. Diese Programmiersprache ist nicht vollständig, aber jedes Programm ist ein Dolmetscher für die Sprache.

David Richerby
quelle
Ah! Das ist ein guter Punkt. Daher müssen bestimmte Anforderungen an die Berechnung der Sprache gestellt werden. Es scheint, dass eine Mindestanforderung an die Macht der Sprache gestellt werden muss, um diese Aussage wahr werden zu lassen. Es scheint, als ob, wenn wir fordern, dass es in der Lage ist, grundlegende arithmetische Probleme zu lösen, dies möglicherweise zutrifft.
Jake
@Jake Sie könnten tatsächlich mit etwas unglaublich Schwachem davonkommen, wie "die Sprache definiert mindestens eine nicht konstante Funktion" oder "die Sprache definiert mehr als eine Funktion". Mein Gegenbeispiel ist für jede vernünftige Definition von "trivial" eindeutig trivial.
David Richerby
Klingt nach einem interessanten Problem, über das ich nachdenken muss. Wenn ich etwas finde, werde ich antworten.
Jake,