Sind Turingmaschinen und formale Sprachen dasselbe mathematische Objekt?

Turings Ziel beim Aufbau seines Konzepts war es, zu formalisieren, wie Menschen abstrakt argumentieren.

Korrigieren Sie mich jetzt, wenn ich falsch liege, aber diese Argumentation scheint nur eine Übung zu sein, bei der Sie eine Reihe formaler Anweisungen manipulieren, dh Zeichenfolgen ohne Semantik.

Wenn also Turing-Maschinen mit Argumentation identisch sind, gibt es einen Isomorphismus (oder ähnliches) zwischen formalen Sprachen und Turing-Maschinen?

formal-languages turing-machines Hieronymus
quelle

TMs sind in der Tat "äquivalent" zu den rekursiv aufzählbaren Sprachen (auch bekannt als Turing unten erkennbar)

vzn

Antworten:

Nicht ganz. Eine Turingmaschine wird durch dieses mathematische Objekt beschrieben:

(Q, Σ, δ, H, q_{0}, b)

$(Q,\Sigma,\delta,\mathcal H, q_0, b)$

$Q$ ist eine endliche Menge von Zuständen
$\Sigma$ ist ein Alphabet , eine endliche Menge von Symbolen
$\delta : Q \times \Sigma \rightarrow Q \times \Sigma \times\{\Leftarrow, \Rightarrow\}$ ist eine Übergangsfunktion
$\mathcal H \subseteq Q$ ist die Menge der Haltezustände
$q_0 \in Q$ ist der Ausgangszustand
$b \in \Sigma$ ist das "leere" Symbol

Die Maschine nimmt eine Eingabezeichenfolge, $x \in \Sigma*$ und verwendet die Übergangsfunktion, um einzelne Symbole in dieser Zeichenfolge bis iterativ zu aktualisieren $\delta$ Gibt einen Status zurück, der zu gehört $\mathcal H$ . An diesem Punkt sagen wir, dass die Maschine angehalten hat - was sie möglicherweise jemals tun wird oder nicht.

Im Vergleich dazu sind formale Sprachen viel einfachere Objekte. Eine Sprache ist nur eine Teilmenge der Menge aller Zeichenfolgen über einem Alphabet. Mit anderen Worten, $\mathcal L \subseteq \Sigma^*$ , wo $*$ ist der Kleene- Sternbetreiber.

Die Verbindung besteht darin, dass Turing-Maschinen verwendet werden können, um formale Sprachen zu definieren . Zum Beispiel:

L = {x \in Σ^{*} | M halts when given ⟨ x ⟩ as input}

$\mathcal L = \{x \in \Sigma^* | \mathcal M \text{ halts when given } \langle x \rangle \text{ as input }\}$

Definiert die formale Sprache $\mathcal L$ in Bezug auf die Turing-Maschine $\mathcal M$ . Für eine Sprache, $\mathcal L$ , wenn es eine Turing-Maschine gibt, die genau dann anhält, wenn ihre Eingabe dazu gehört $\mathcal L$ dann heißt die Sprache Turing-erkennbar . Einige Sprachen können von keiner Turing-Maschine definiert werden, was bedeutet, dass sie nicht berechenbar sind - kein endlicher Prozess kann entscheiden, ob eine beliebige Zeichenfolge zur Sprache gehört oder nicht.

Formale Sprachen sind nicht dasselbe wie Turing-Maschinen, aber die Turing-Erkennbarkeit hat einen interessanten Platz beim Studium formaler Sprachen. In der Chomsky-Hierarchie ist eine Sprache vom Typ 0 eine Sprache, die von jeder formalen Grammatik aufgezählt werden kann, und dies entspricht der Erkennung durch eine Turing-Maschine! Formale Grammatiken und Turing-Maschinen sind nur zwei von vielen Rechenmodellen, die alle gleich leistungsfähig sind!

Es wird allgemein angenommen, dass jedes Rechenmodell die gleiche Unterscheidung zwischen berechenbaren und nicht berechenbaren Sprachen trifft - dieser Begriff wird als Church-Turing-These bezeichnet .

EDIT: Meine Terminologie war nicht korrekt, als ich dies zum ersten Mal schrieb. Eine Turing-entscheidbare Sprache kann von einer Maschine entschieden werden, die immer anhält und ein definitives Ja oder Nein gibt, ob ihre Eingabe zur Sprache gehört. Wenn wir nur verlangen, dass die Maschine Mitglieder akzeptiert, aber Nichtmitglieder nicht unbedingt ablehnen kann, wird die zugehörige Sprache als Turing erkennbar oder häufiger als rekursiv aufzählbar bezeichnet. Das Erkennen erkennbarer Sprachen entspricht den Sprachen, die durch uneingeschränkte Grammatiken erzeugt werden können.

Einige Sprachen sind nicht einmal rekursiv aufzählbar - zum Beispiel ist die Menge aller Turing-Maschinen, die nicht anhalten, völlig unkenntlich. Es gibt eine Sprache, die diesem Satz entspricht und von keiner Grammatik generiert werden kann, die aber dennoch als "formale Sprache" bezeichnet werden kann. Nach dieser Definition gibt es keine vollständige Zuordnung von Turing-Maschinen zu formalen Sprachen und definitiv keinen Isomorphismus zwischen den beiden.

kebertx
quelle

@ kebertx Also können wir sagen, dass es einen Isomorphismus zwischen entscheidbaren Sprachen und Turing-Maschinen gibt?

Jerome

Es gibt definitiv eine Vermutung von Turing-Maschinen zu entscheidenden Sprachen, aber das Gegenteil ist nicht wahr. Jede entscheidbare Sprache entspricht tatsächlich einer unendlichen Anzahl von Turing-Maschinen, was bedeutet, dass es dort keinen Isomorphismus geben kann. - Beweis: Angenommen, Sie haben ein Programm, das entscheidet, ob eine beliebige Zeichenfolge zu einer Sprache gehört. Dann können Sie ein anderes Programm schreiben, das zuerst eine zufällige Berechnung durchführt, dann das Ergebnis verwirft und die gleiche Entscheidung wie das erste Programm trifft. Dies sagt uns, dass jedes Problem entweder null oder unendlich viele Lösungen hat!

Kebertx

Nein, sie sind nicht dasselbe. Eine Sprache ist eine Reihe von Wörtern über einem endlichen Alphabet. Eine Turingmaschine ist ein 7-Tupel wie in der Wikipedia definiert .

Für einige Sprachen ist es zweckmäßig, sie durch ein TM zu charakterisieren, das sie erkennt. Für jede Sprache, die von einem TM erkannt werden kann, gibt es unendlich viele TMs, die dieselbe Sprache erkennen. Sie müssten also einige zusätzliche Kriterien festlegen, um diese eindeutig zu machen.

Dies mag nach einem guten Start für einen Isomorphismus klingen, aber leider gibt es unendlich viele Sprachen, die von TMs nicht erkannt werden können. Dies kann durch ein einfaches Zählargument gesehen werden. Die Menge aller möglichen Wörter über einem festen Alphabet ist isomorph zu den natürlichen Zahlen. Daher ist die Menge aller Sprachen über diesem Alphabet (= die Menge aller Teilmengen der Wörter) unzählig. Andererseits gibt es nur zählbar viele Turingmaschinen. Es kann also nicht nur keine "Erkennung" zu einem Isomorphismus gemacht werden, es kann auch keinen Isomorphismus jeglicher Art geben, da dies bedeuten würde, dass die Menge der TMs dieselbe Kardinalität wie die Menge der Sprachen hat.

adrianN
quelle

Können wir nicht sagen, dass eine formale Sprache notwendigerweise von mindestens einem TM erkannt wird ?

Jerome

@ Jerome Nein. Es gibt unendlich viele Sprachen, die nicht einmal halb entscheidbar sind und daher von keiner Turing-Maschine entschieden oder akzeptiert werden.

David Richerby

@ adrianN. Richtig und umgekehrt? Wenn Sie also ein TM haben, kann es etwas anderes als eine formale Sprache erzeugen?

Jerome

@ Jerome Für jede Turing-Maschine gibt es eine (möglicherweise leere) Sprache, die sie akzeptiert. Sie ist definiert als die Menge von Wörtern, die das TM im YES-Status anhält. Es gibt eine Sprache für jedes TM, aber kein TM für jede Sprache.

Jmite

Okay, kann ich zu Recht sagen, dass zum Beispiel kein TM die von ZFC definierte formale Sprache akzeptiert? (da es einige Aussagen gibt, die in ZFC wahr sind, wo kein TM anhält)

Jerome