Gibt es eine unzählige Turing entscheidbare Sprache?

17

Es gibt viele (und ich meine viele) zählbare Sprachen, die Turing-entscheidbar sind. Kann jede unzählige Sprache entscheidend sein?

Jyotirmoy Pramanik
quelle
1
Wenn die Sprache aller möglichen Wörter unzählbar ist (was ein unzählbares Alphabet erfordert), dann liefert es sofort ein Beispiel für eine (trivial) entscheidbare, unzählbare Sprache von Turing. Wenn dies nicht der Fall ist (dh abzählbar ist), sind auch die Untersprachen nicht unzählbar.
Marc van Leeuwen

Antworten:

24

Jede Sprache über einem endlichen (oder sogar zählbaren) Alphabet ist zählbar. Vorausgesetzt, Ihr Turingmaschinen-Alphabet ist endlich, ist jede Sprache, die es möglicherweise akzeptieren kann, zählbar.

Yuval Filmus
quelle
Was ist mit einer Menge aller Sprachen mit einer endlichen Anzahl von Zeichenfolgen über einem zählbar unendlichen Alphabet? Ist es zählbar oder unzählbar? Auch konnte ich mir keinen Beweis für "Sprache über unendlich abzählbares Alphabet ist abzählbar" vorstellen.
am
Ihr Set ist auch zählbar.
Yuval Filmus
Dies beweist, dass "eine Menge von Sprachen über dem endlichen Alphabet abzählbar ist". Ich denke, wir können beweisen, dass "eine Menge von Sprachen, die unendlich viele Zeichenfolgen über endlichem Alphabet enthalten, zählbar ist", wenn wir denselben Beweisansatz aufgrund des endlichen Alphabets anwenden. Aber ich kann mir nicht vorstellen, wie dieser Ansatz für unendlich viele Buchstaben angepasst werden kann.
am
Sie können es nicht beweisen, da es falsch ist. Die Anzahl der unendlichen Binärfolgen ist bereits unzählig.
Yuval Filmus
11

Wir können nur unzählige Sprachen haben, wenn wir Wörter von unendlicher Länge zulassen, siehe zum Beispiel Omega-reguläre Sprache . Diese Sprachen heißen Sprachen. Ein weiteres Beispiel ist die Sprache einer Teilmenge von Realzahlen, die beispielsweise Dezimalerweiterungen aller Realzahlen enthält.ω

Es gibt einige Modelle, bei denen Turing-Maschinen so modifiziert sind, dass sie Sprachen akzeptieren . Einige dieser Modelle verwenden die Buchi-Bedingung für die Annahme. Da Sie nicht die gesamte Eingabe in endlicher Zeit sehen können, sagen wir, dass die Eingabe akzeptiert wird, wenn die Turing-Maschine unendlich oft in den Akzeptanzzustand wechselt. Wenn wir dies durch Analysieren der Eingabe beweisen können (nicht durch Ausführen), sagen wir, dass die Eingabe akzeptiert wird.ω

Shreesh
quelle
1
Warum sollte das Alphabet abzählbar sein müssen?
linksum den
2
Jedes untersuchte Modell hat ein endliches Alphabet. Wenn das Alphabet auch unendlich wird (zählbar oder unzählbar), ist es schwierig, ein vernünftiges Modell zu haben.
Shreesh
@Shreesh Nun, wenn das Alphabet unzählig ist, könnte eine naive Abbildung eines FSM (mit unzähligen Übergängen zwischen einer endlichen Anzahl von Zuständen) ziemlich mächtig sein?
Yakk
1
Es ist wahr, dass dies die Art von Erweiterungen sind, die Sprachklassen haben können, die Superklasse von RE- oder rekursiven Sprachen sein können. Aber wenn überhaupt, werden sie nicht gut studiert. Das größte Problem ist meiner Meinung nach, wie wir die Maschine endlich abbilden können. Dann müssen Sie das Symbol in eine Bandzelle schreiben. Sogar die bescheidene Zelle benötigt möglicherweise unendlichen Speicher, um die Beschreibung des zu schreibenden Bandsymbols zu speichern.
Shreesh
Dies ist eine großartige Erklärung. Ich würde hinzufügen, dass, selbst wenn ein gewöhnliches Annehmen / Ablehnen-Kriterium verwendet wird, man sagen könnte, dass es noch einige Sprachen gibt, über die eine Turing-Maschine entscheiden könnte und die technisch unzählige Zeichenfolgen haben würde, aber nur, weil die große Mehrheit der Zeichen " nutzlos "für die Sprache.
Owen
4

Die klassische Berechenbarkeit erörtert Funktionen über endliche Zeichenfolgen aus einem endlichen Alphabet. Infolgedessen sind alle Sprachen, ob entscheidbar oder unentscheidbar, zählbar.

Um unzählige Sprachen zu betrachten, müssen wir uns unendliche Zeichenfolgen anstelle endlicher Zeichenfolgen ansehen . (AFAIK, mit einem unendlichen Alphabet ist nicht sehr interessant und entspricht nicht einem realistischen Rechenmodell für sich.)

Es gibt Berechnungsmodelle, in denen wir mit unendlichen Zeichenfolgen umgehen können, mit denen wir Objekte aus unzähligen Bereichen wie reelle Zahlen darstellen können. Diese werden oft als Berechnungen höherer Art dargestellt. Ein Modell, das Turing-Maschinen verwendet, ist das TTE-Modell. In diesem Modell kann die Eingabe aus unendlichen Zeichenfolgen bestehen und die Maschinen können auf jedes Element in der Zeichenfolge zugreifen, das sie möchten. Die Maschine muss nicht beendet werden, es gibt jedoch Bedingungen, um sicherzustellen, dass die Ausgabe der Maschine konvergiert.

Nehmen wir an, dass die Eingabe unserer Maschine von , dh von unendlichen Zeichenfolgen aus dem Alphabet Σ , z. B. Σ = { 0 , 1 } . Dann gibt es Σ N = 2 N Strings. Daher gibt es 2 2 NΣωΣΣ={0,1}ΣN=2N22N mögliche Sprachen. Die Anzahl der TTE Turing-Maschinen ist noch zählbar. Die meisten dieser Sprachen sind also unentscheidbar.

Aber hier gibt es noch etwas Interessanteres: Wenn Sie möchten, dass die Maschine immer anhält, kann sie nur einen begrenzten Anfangsteil der Eingabe lesen. Als Ergebnis haben wir Folgendes: Sei eine TTE-Maschine, die immer anhält (in endlicher Zeit). Dann gibt es eine Vorsilbe freie Sprache L & Sigma; * und Turing Maschine N , so daß für eine beliebige x & Sigma; & ohgr; , M akzeptiert x iff N Anfangsteil akzeptiert x , die in ist L .MLΣNxΣωMxNxL

Einfach ausgedrückt wird die Berechnung von TTE-Turing-Maschinen, die immer anhalten, durch die Berechnung einer Turing-Maschine auf endlichen Saiten bestimmt.


Lassen Sie mich ein Beispiel für entscheidbare und unentscheidbare Sprachen unendlicher Zeichenfolgen geben:

  1. Für jedes die Sprache von unendlichen Zeichenketten, deren k- te Position 0 ist, bestimmbar. Dasselbe gilt für die k- te Position 1. Der Schnittpunkt von zwei entscheidbaren Sprachen ist entscheidbar, z. B. Zeichenfolgen, deren 3. Position 0 und deren 6. Position 1 ist.kNkk36

  2. Die Vereinigung von zwei entscheidbaren Sprachen ist entscheidbar. ZB Zeichenketten, die mit oder 10 beginnen .010

  3. Sei eine rechnerisch aufzählbare Liste entscheidbarer Sprachen. Dann ist L = i L i halbentscheidbar, dh es gibt eine Maschine, die anhält und akzeptiert, wenn eine Zeichenkette in L steht und nicht akzeptiert, wenn die Zeichenkette nicht in L steht . Wenn es nicht in L ist, stoppt die Maschine möglicherweise nicht. Jede halbentscheidbare Sprache kann durch Vereinigung einer Liste von Sprachen in der unter Punkt 1 angegebenen Form erhalten werden.LiL=iLiLLL

  4. Eine Sprache ist entscheidbar, wenn sowohl die Sprache als auch ihre Ergänzung teilentscheidbar sind.

  5. kk


xlgxxlgx


f{0,1}f1(1)". Es gibt auch viele andere Referenzen auf der Website für Berechenbarkeit und Komplexität in Analysis Network .

Kaveh
quelle
1
" Folglich sind alle Sprachen endlich " - Meinst du abzählbar?
Anton Trunov
Ich denke schon, Mr. Trunov.
Jyotirmoy Pramanik
Dies ist ein netter Beitrag, aber ich verstehe nicht, was der Hauptteil mit der hier gestellten Frage zu tun hat. Vielleicht wollten Sie ein Frage-Antwort-Paar erstellen?
Raphael