Welche Beziehung besteht zwischen Problemen und Sprachen?

Ich möchte genau fragen, in welchem ​​Verhältnis Probleme und Sprachen stehen. Wir wissen, dass die Menge aller Sprachen unzählig ist. Sind die Probleme auch unzählig? Kann jedes Problem durch eine Sprache definiert werden? Kann eine Sprache mehr als ein Problem lösen und umgekehrt? Gibt es eine Eins-zu-Eins-Entsprechung zwischen Problem und Sprachen?

Entscheidungsprobleme und Sprachen sind nur die beiden Seiten derselben Medaille: Jedes Problem kann als Mitgliedschaftsproblem einer Sprache umformuliert werden. Das Problem, beispielsweise zu bestimmen, ob eine Zahl eine Primzahl ist, ist genau das Mitgliedschaftsproblem der Sprache der Primzahlen.

Formal ist eine Sprache eine Menge endlicher Zeichenfolgen über einem festen endlichen Alphabet (manchmal dürfen die Zeichenfolgen unendlich sein; das ist ein anderes, aber verwandtes Szenario). Probleme, bei denen es sich nicht direkt um Fragen zu Zeichenfolgen handelt, müssen als Zeichenfolgen codiert werden. Daher wäre es präziser gewesen, den letzten Satz des vorherigen Absatzes wie folgt zu schreiben: "Wenn wir ein Alphabet und eine Codierung natürlicher Zahlen korrigieren." Als Zeichenfolgen über diesem Alphabet ist das Problem, beispielsweise zu bestimmen, ob eine Zahl eine Primzahl ist, genau das Zugehörigkeitsproblem der Sprache der Zeichenfolgen, die Primzahlen codieren. "

Um Ihre Unterfragen schnell durchzugehen,

Wir wissen, dass die Menge aller Sprachen unzählig ist. Sind die Probleme auch unzählig?

Ja, da Probleme und Sprachen im Wesentlichen dasselbe sind.

Kann jedes Problem durch eine Sprache definiert werden?

Entscheidungsprobleme, ja. Optimierungsprobleme (was ist das kleinste X mit Eigenschaft Y) und Zählprobleme (wie viele X haben Eigenschaft Y) können als Entscheidungsprobleme umformuliert werden (ist das Z das kleinste X mit Eigenschaft Y? Gibt es NX mit Eigenschaft Y?) Das ist normalerweise nicht die natürlichste Art, sie zu behandeln.

Kann eine Sprache mehr als ein Problem lösen und umgekehrt?

$\{10,11,101,111,1011,\dots\}$$\{2,3,5,7,11, \dots\}$$\{0, 10, 110, 1110, \dots\}$$2^k-2$$k$und das Problem zu bestimmen, ob eine Zeichenfolge von Einsen und Nullen genau eine 0 hat, was ihr endgültiges Zeichen ist. (Vielleicht kann jemand ein besseres Beispiel für eine Sprache finden, die natürlich zwei Probleme codiert, ohne dass eines eine so triviale Umformulierung des anderen ist.)

Gibt es eine Eins-zu-Eins-Entsprechung zwischen Problem und Sprachen?

Nein, da diese Frage nur die Ergänzung der vorherigen ist. :-)