Entscheidbarkeit der Sprachen

$L_1$ ist eine rekursiv aufzählbare Sprache über einem Alphabet . Ein Algorithmus zählt seine Wörter effektiv als . ist eine andere Sprache über als Betrachten Sie die folgenden Aussagen. $\Sigma$ $w_1, w_2, ...$
$L_2$ $\Sigma \cup \{\#\}$ $\{w_i\#w_j : w_i, w_j \in L_1, i < j\}$

$L_1$ ist rekursiv impliziert ist rekursiv $L_2$

$L_2$ ist rekursiv impliziert ist rekursiv $L_1$

Welche Aussagen sind / sind wahr?

Ich habe beide Aussagen für wahr befunden.

Aussage 1 ist wahr. ist rekursiv, es kann seine Zeichenfolgen lexikografisch auflisten. Die Mitgliedschaftsfrage für kann einfach mit dem Entscheider und lexikografischen Enumerator von geklärt werden . $L_1$ $L_2$ $L_1$

Aussage 2 ist wahr. Der Algorithmus, der entscheidet, kann geändert werden, um zu akzeptieren, ob die Eingabezeichenfolge entweder mit oder . Damit ist die Mitgliedschaftsfrage für . $L_2$ $w_i$ $w_j$ $L_1$

Die gegebene Lösung für diese Frage besagt jedoch, dass Aussage 2 falsch ist. Könnten Sie mich wissen lassen, ob meine Argumentation irgendwo falsch ist?

formal-languages computability Abhijith Madhav
quelle

"passt entweder zu oder " - wofür resp. ?

w_{i}

$w_i$

w_{j}

$w_j$

i

$i$

j

$j$

Raphael

@Raphael, ich meine zu sagen, dass der Algorithmus, der entscheidet, kann, um zu akzeptieren, ob die Eingabezeichenfolge mit oder von , der Form der Zeichenfolge von .

L_{2}

$L_2$

w_{i}

$w_i$

w_{j}

$w_j$

w_{i} # w_{j}

$w_i\#w_j$

L_{2}

$L_2$

Abhijith Madhav

Aber woher kommt es bekommt die

w_{i} # w_{j}

$w_i\#w_j$ ? Sie können nicht einfach nach einem suchen, das Ihnen nur Aufzählbarkeit und keine Entscheidbarkeit gibt. (Sie müssen hier wirklich genau sein!)

Raphael

Sie dürfen die Aufzählung von nicht ändern

L_{1}

$L_1$ In Schritt 1 ist Ihre Begründung für Schritt 1 also fehlerhaft, wenn Sie von der Aufzählung wechseln

w_{i}

$w_i$ zur lexikografischen Aufzählung.

Andrej Bauer

Du darfst das nicht. Die Erklärung des Problems gibt Ihnen einen Algorithmus zum Aufzählen

L_{1}

$L_1$ und Sie müssen diese in der Definition von verwenden

L_{2}

$L_2$ . Sie verstehen die Problemstellung falsch.

Andrej Bauer

Antworten:

Sie scheinen recht zu haben. Aber wie Raphael sagt, sei vorsichtig.

Aussage 1. Beachten Sie, dass die $L_2$ wird mit dem Aufzählungsalgorithmus definiert $\cal E$ zum $L_1$ , nicht von $L_1$ selbst. Um zu entscheiden, ob $u\#v \in L_2$ , entscheiden, ob beide $u,v$ im $L$ und wenn bestätigt, führen Sie den Enumerator aus $\cal E$ und sehen, ob $u$ wird vorher ausgegeben $v$ . Wie wir wissen, sind beide Saiten in $L_1$ Dies wird beendet.

Aussage 2. Wenn $L_1$ ist endlich, es ist rekursiv, also nehmen wir an $L_1$ ist unendlich. Lauf $\cal E$ und warte auf das erste Wort $w_1$ . Nun ein Entscheider für $L_2$ kann in eine für verwandelt werden $L_1$ wie folgt. Zu testen $u\in L_1$ Überprüfen Sie zuerst, ob $u=w_1$ und dann überprüfen $w_1\#u \in L_2$ . Dies entspricht dann $u\in L_1$ da müssen wir uns keine sorgen um die $i<j$ Anforderung, die jetzt durch Konstruktion wahr ist.

Ich bin mir nicht mal sicher, ob wir es wissen müssen $w_1$ durch Laufen $\cal E$ : Wir wollen nur überprüfen , ob es einen Entscheider gibt, nicht, ob einer effektiv konstruiert werden kann. Das scheint unmöglich.

( Bearbeiten ) Nur um zu beachten, dass Raphael eine explizitere "Implementierung" dieser Vorschläge veröffentlicht hat, wodurch mögliche Unklarheiten vermieden werden.

Hendrik Jan.
quelle

Zu Aussage 2:

w_{1}

$w_1$ kann fest codiert sein, und dann können wir die Annahme fallen lassen, dass

L_{1}

$L_1$ ist rekursiv aufzählbar.

Yuval Filmus

Hängt davon ab; das wissen wir nicht

E

$\cal{E}$ wiederholt sich nicht. Wenn ja,

w_{1} # w_{1} \in L_{2}

$w_1\# w_1 \in L_2$ Letztendlich. Das können wir nicht entscheiden

w_{1}

$w_1$ wird nie wiederholt. Natürlich gibt es immer einen sich nicht wiederholenden Enumerator, aber seitdem

L_{2}

$L_2$ hängt speziell davon ab

E

$\cal{E}$ Es ist nicht fair anzunehmen, dass wir eine haben.

Raphael

Hier überprüfen wir nie

w_{1} # w_{1}

$w_1\#w_1$ um Probleme zu vermeiden. Eingang

u

$u$ wird "manuell" auf geprüft

w_{1}

$w_1$ . Abgesehen davon schlägt die Formulierung eine Aufzählung ohne Wiederholung vor, gerade weil Ihr Kommentar.

Hendrik

@ HendrikJan Ich erklärte, warum überprüfen

u = w_{1}

$u=w_1$ reicht nicht aus, um das abzulehnen

u

$u$ allgemein. Die Formulierung schlägt keine Aufzählung ohne Wiederholung vor; Tatsächlich sagt das OP, dass die gegebene Lösung Ihrer Antwort widerspricht, was auf eine andere Interpretation hinweisen würde.

Raphael

Ich glaube, ich habe mich teilweise verwirrt. Ich habe selbst eine Antwort gepostet, die meiner Meinung nach Ihrer Absicht entspricht. Ich glaube, ich habe dabei ein Problem mit unserem Beweis für die erste Aussage gefunden.

Raphael

Anzeige 1: Die Aussage ist wahr, aber Ihre Argumentation ist nicht: Sie können die Aufzählung nicht ändern; Die Definition von $L_2$ ist eng mit der Reihenfolge der Elemente verbunden. Hier ist der einfache Algorithmus, der entscheidet $L_2$ ::

decide2(w) = {
  (u,v) = split (w,#) // w = u#v

  if ( decide1(u) && decide1(v) ) {
    i = 1
    while ( true ) {
      if ( enumerate1(i) == u ) {
        return true
      }
      else if ( enumerate1(i) == v ) {
        return false
      }
      i += 1
    }   
  }

  return  false
}

Hier decide1ist der Entscheider für $L_1$ und enumerate1ist der Enumerator für $L_1$ , die beide unter der Annahme existieren. Beachten Sie, dass die whileSchleife immer endet. An diesem Punkt wissen wir das $u,v \in L_1$ so wird die Schleife sie schließlich finden (tatsächlich diejenige, die zuerst auftritt).

Anzeige 2: Diese Aussage ist zwar richtig, aber auch aus anderen Gründen als von Ihnen angegeben.

Wenn $L_2$ ist rekursiv, das folgende Programm ist berechenbar und entscheidet $L_1$ ::

decide1(w) = {
  w1 = enumerate1(1)
  if ( w == w1 ) }
    return true
  }
  else {
    return decider2(w1#w)
  }
}

Wenn $w = w_1$ haben wir eindeutig $w \in L_1$ und das Programm entscheidet richtig. Wenn $w \in L_1 \setminus \{w_1\}$ , da ist ein $i > 1$ so dass $w_i = w$ , und deshalb $w_1\#w \in L_2$ ;; umgekehrt, wenn $w \not\in L_1$ gibt es keine solche $i$ und somit $w_1\#w \not\in L_2$ . Das Programm entscheidet in allen Fällen richtig.

Raphael
quelle

Wenn Sie sich das vorstellen, ist der erste Algorithmus fehlerhaft: Wenn die Aufzählung Wiederholungen aufweist, können wir die Eingabe nicht ablehnen, nur weil die ersten Vorkommen von

u, v

$u,v$ sind in der falschen Reihenfolge.

Raphael

Keine Hoffnung auf Patches, denke ich. Es gibt keine Möglichkeit zu entscheiden, ob das Wort jemals wieder vorkommen wird

u

$u$ (um es zu überprüfen tritt auch danach auf

v

$v$ ). Die Frage besagte jedoch, dass es Schwierigkeiten mit Problem 2 gab. Nicht Problem 1 :)

Hendrik Jan

@ Raphael, ich verstehe nicht, was du mit "du kannst die Aufzählung nicht ändern" meinst. Welche Aufzählung habe ich geändert? Meine Begründung für die Richtigkeit von Aussage 1 ist genau das, was Sie in Ihrer obigen Antwort geschrieben haben. Nach Verwendung des Entscheiders von

L_{1}

$L_1$ zu entscheiden

u

$u$ und

v

$v$ Verwenden Sie den Enumerator, um zu überprüfen, ob

u

$u$ wird vorher aufgezählt

v

$v$ . Ist das nicht so, weil Sie den Enumerator von erwarten

L_{1}

$L_1$ lexikographisch aufzuzählen, jetzt, wo die Hypothese von Aussage 1 dies sagt

L_{1}

$L_1$ ist rekursiv?

Abhijith Madhav

@ Raphael, Ihr folgender Kommentar hat mich mehr verwirrt. Warum denkst du jetzt, dass erste Vorkommen von

u, v

$u, v$ Möglicherweise in der falschen Reihenfolge, wenn die Aufzählung Wiederholungen enthält. Wie

L_{1}

$L_1$ ist rekursiv, kann die Aufzählung nicht haben

u, v

$u, v$ in der falschen Reihenfolge. Ich habe gerade auf ein Lehrbuch (Sipser) verwiesen, um sicherzustellen, dass mein "rekursiv impliziert lexikographisch aufzählbar" korrekt ist.

Abhijith Madhav

@Abhijith Aus dem, was Sie in Ihrer Frage schreiben, ist nicht klar, wie Sie genau ausnutzen, dass es eine lexikografische Aufzählung gibt. Sie können nicht die Aufzählung annehmen definieren

L_{2}

$L_2$ ist lexikografisch, und es scheint, als ob Sie das getan haben.

Raphael