Gibt es eine unzählige Turing entscheidbare Sprache?

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

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.

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.$\omega$

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.$\omega$

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 $\Sigma^\omega$$\Sigma$$\Sigma = \{0,1\}$$\Sigma^\mathbb{N} = 2^\mathbb{N}$$2^{2^\mathbb{N}}$ 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 .$M$$L \in \Sigma^*$$N$$x\in \Sigma^\omega$$M$$x$$N$$x$$L$

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.$k\in \mathbb{N}$$k$$k$$3$$6$

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

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.$L_i$$L = \cup_i L_i$$L$$L$$L$

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

5. $k$$k$

$x \mapsto \lg x$$x$$\lg x$

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