Warum erkennt eine Turingmaschine genau eine Sprache?

13

Ich versuche, die Existenz nicht erkennbarer Sprachen zu verstehen. Um dies zu erreichen, muss ich wissen, warum eine Turing-Maschine nur eine Sprache erkennt, nicht mehrere. Warum ist das?

Anonym
quelle
12
Ich vermute, dass Sie keine klare Vorstellung davon haben, was wir unter "Sprache" verstehen. Können Sie sagen, was Sie für eine "Sprache" halten?
Eric Lippert
Warum musst du das wissen? Inwiefern könnte das einen Unterschied machen?
Babou

Antworten:

29

Die von einer Turing-Maschine erkannte Sprache ist per Definition die Menge der Zeichenfolgen, die sie akzeptiert. Wenn eine Eingabe an die Maschine gesendet wird, wird diese entweder akzeptiert oder nicht. Jede bestimmte Eingabe in diese Maschine wird entweder immer akzeptiert (in der Sprache) oder immer nicht akzeptiert (nicht in der Sprache). Es gibt also keinen Mechanismus, mit dem eine einzelne Turing-Maschine mehr als eine Sprache aufnehmen könnte.

David Richerby
quelle
6
"Per Definition" ist genau das, was ich gesagt hätte.
Dave Clarke
1
@ DaveClarke Natürlich ist es per Definition. Dies scheint mir jedoch etwas kurz zu sein, da es auch besagt, dass wir unsere Definition ändern könnten, sodass ein TM zwei Sprachen oder eine beliebige Zahl akzeptieren würde. Eigentlich stimme ich David Richerbys Aussage nicht zu, dass es keinen Mechanismus gibt, mit dem ein TM zwei Sprachen akzeptieren könnte: Es liegt nur daran, dass wir sie ignorieren, und wir könnten es auch anders machen. Daher ist die Frage nicht vollständig beantwortet, wenn wir nicht erklären, was dies rechtfertigt.
Babou
2
Ich denke, das Problem hier ist die Sprache, die verwendet wird, um "Sprache" selbst zu beschreiben. Eine Turing-Maschine akzeptiert alles in Form einer Zeichenfolge, unabhängig von unserer Sprachdefinition. Das TM definiert Sprache durch das, was es akzeptiert. Dies ist nicht dasselbe wie unser (menschliches) Sprachverständnis. Deshalb ist diese Antwort gut und lautet "... vollständig beantwortet".
David Barker
2
Ich stimme David zu, der OP hat höchstwahrscheinlich irgendwo gelesen, dass Turing-Maschinen nur eine Sprache zulassen und versucht zu verstehen, was das bedeutet. Da dies wahrscheinlich aus einer normalen Quelle stammt, können wir annehmen, dass sie die normale Definition von "Sprache", wie sie in der Computertheorie definiert ist, und keine andere Definition verwendeten. Die Definition kann willkürlich sein, ist aber eine gut verstandene und vereinbarte willkürliche Definition.
Cort Ammon - Setzen Sie Monica wieder ein
3
Eine Turing-Maschine, die zwei Sprachen akzeptiert, ist eine Turing-Maschine, die eine Sprache akzeptiert, die die Vereinigung von zwei Sprachen ist.
Simon Richter
9

Stellen Sie sich das so vor: Ein TM ist wie ein Computer mit einer geladenen Software. Jede Software macht eine Sache, oder? Denken Sie beispielsweise an Ihren Computer und nehmen Sie an, dass nur 1 Programm darauf geladen ist. Dann macht PC + "Photoshop" nur Photoshop, während PC + "Mine Sweeper" nur Minen fegt.

Eine Turingmaschine ist also eine sehr einfache Kreatur, die bei jedem Lauf eine einzige Eingabe erhält und entweder eine Ja oder eine Nein ausgibt . An welchen Eingängen es Ja sagt und an welchen Nein sagt - dies wird durch das "Programm" des TM eingestellt, das durch seine Zustände und seine Übergangsfunktion bestimmt wird. Sobald diese behoben sind, ist das "Programm" festgelegt, und für eine bestimmte Eingabe gibt es nur eine Antwort: Ja oder Nein (akzeptieren / ablehnen). Dies definiert genau eine einzelne Sprache = alle Eingaben, die ein Ja ergeben, wenn sie dem TM übergeben werden.

Auf der anderen Seite das Set von allen ist TMs entspricht den Satz von Computern + „Software“ mit allen möglichen Programmen. Jetzt können mehr Sprachen entschieden werden - aber dennoch entscheidet (oder erkennt) jedes spezifische TM nur eine Sprache.

Ran G.
quelle
Kleiner Punkt: Ich würde nicht sagen, dass ein TM "entweder ein Ja oder ein Nein" ausgibt, da dies die Nichtbeeinflussung vernachlässigt. Diese Vereinfachung kann später zu weiteren Problemen führen.
Chi
4

Turing Machine funktioniert genauso wie sie, weil wir sie so definieren. Wir könnten differenziertere Definitionen haben, aber die Frage ist, ob dies einen Zweck erfüllen würde, ob es uns erlauben würde, mehr Dinge zu tun. Und soweit wir wissen, lautet die Antwort nein.

Es ist sehr einfach, Modelle von Turing-Maschinen herzustellen, die zwei Sprachen erkennen. Bei gegebenen Sprachen und L 2 könnten wir ein TM mit zwei Arten von Akzeptanzzuständen definieren: einen für L 1 und einen für L 2 . Man würde sagen, dass ein TM akzeptiertL1L2L1L2wenn es irgendwann in einen entsprechenden Akzeptanzzustand eintritt. Es würde jedoch die Berechnung wieder aufnehmen, um zu sehen, ob es auch in die andere Art des Akzeptanzzustands eintreten kann. Und wir könnten verlangen, dass es später anhält oder möglicherweise nicht. Sie könnten dann die gesamte Theorie auf solchen Maschinen aufbauen. Es würde funktionieren und viel komplizierter sein als das, was wir normalerweise tun.Li

Um die Aussage von David Richerby zu beantworten , dass " es keinen Mechanismus gibt, durch den eine einzelne Turing-Maschine sogar mehr als eine Sprache akzeptieren könnte ", liegt es nur daran, dass wir uns dafür entscheiden, solche Mechanismen nicht in Betracht zu ziehen. Selbst wenn Sie TM auf das Standardmodell beschränken, können Sie sagen, dass die Eingabe in der Sprache erkannt wird, wenn das TM in einem akzeptierenden Zustand mit einer ungeraden Anzahl von Schritten anhält und in L istL1L2 wenn das TM akzeptiert mit einer geraden Anzahl von Schritten. Dank des Nichtdeterminismus würde dies das TM nicht daran hindern, beide sich überschneidenden Sprachen zu erkennen.

Der Punkt ist, dass alle Arten von Varianten verwendet werden können, um die Theorie zu tun. Es wurden auch sehr unterschiedliche Ansätze zur Modellierung von Berechnungen versucht, z.

Es hat sich immer gezeigt, dass keiner von ihnen etwas tut, was mit unserem einfachen Modell, bei dem TM nur eine Sprache erkennt, nicht möglich ist. In einem solchen Ausmaß, dass vermutet wurde, dass es alles tut, was getan werden kann. Das nennt man die Church-Turing-These . Es ist der Eckpfeiler der Berechenbarkeitstheorie, der nach unserem Kenntnisstand bestimmt, welche Sprachen erkennbar sind oder nicht.

Wir könnten also genauso gut ein einfaches Modell verwenden, da ein komplexes unser Leben ohne wirklichen Nutzen erschweren wird.

Natürlich verwenden wir manchmal andere Modelle, weil sie es uns ermöglichen, einige Probleme besser zu verstehen.

babou
quelle
Ich halte den ersten Absatz für etwas irreführend. Ich bin bereit zu wetten, dass die OP nicht fragt, warum wir die Dinge so definieren, aber dass sie nicht einmal wussten, dass dies der Fall ist. "Wir könnten differenziertere Definitionen haben, aber die Frage ist, ob es einem Zweck dienen würde" lässt es scheinen, als müsste man den Zweck eines Konzepts kennen, bevor man es benennen kann - meiner Meinung nach ist das schlecht Weg zu lernen.
Interessanterweise ist der
Das OP sagt, er möchte wissen, warum TM nur eine Sprache erkennt, um etwas anderes zu verstehen. Ich antworte ihm, sie tun es, weil wir sie so definieren. Ich füge hinzu, das stimmt, wir könnten verschiedene Definitionen verwenden, aber das würde die Theorie nicht ändern. Auf diese Weise kann man ihm sagen, dass die Wahl der Definition, wonach er sich sehnt, unerheblich ist und dass die Erkennbarkeit genau dieselben Mengen abdecken kann. Der Grund für die Wahl der Definition ist Bequemlichkeit und Fruchtbarkeit, und deshalb entwickeln sie sich mit der Zeit, ebenso wie die Art und Weise, wie Konzepte benannt oder notiert werden.
Babou
Okay, das macht Sinn. Ich denke, ich bin größtenteils gegen die Verwendung von "anspruchsvoll" - dies impliziert, dass eine weniger einfache Definition wünschenswert ist.
Interessanterweise
3

Ich möchte auf einen Punkt in Richerbys Antwort eingehen:

Wenn eine Eingabe an die Maschine gesendet wird, wird diese entweder akzeptiert oder nicht.

Der Grund dafür ist, dass die Turing-Maschine deterministisch ist: Wenn Sie dieselbe Eingabe und denselben Startstatus ausführen, wird sie immer dasselbe tun (entweder im selben Akzeptanzstatus oder im selben Ablehnungsstatus beenden oder eine Endlosschleife ausführen ).

Außerdem können wir leicht nachweisen, dass jede Turing-Maschine genau eine Sprache erkennt:

Angenommen, eine Turingmaschine M erkennt im Widerspruch zwei verschiedene Sprachen L1 und L2. Da L1 und L2 verschieden sind, muss eine Zeichenkette S existieren, die in L1 aber nicht in L2 ist (ohne Verlust der Allgemeinheit - es könnte umgekehrt sein, aber der Beweis würde in der gleichen Weise von hier mit L1 und L2 ablaufen, die ausgetauscht werden ). Führen Sie nun M auf S aus. Wenn es akzeptiert, dann ist ein Widerspruch erreicht, weil dann S in L2 wäre. Wenn es nicht akzeptiert (verwirft oder schleift), dann ist ein Widerspruch erreicht, weil S nicht in L1 wäre.

Atsby
quelle
2

Eine Turingmaschine erkennt eine Sprache, weil dies die Definition des Wortes " erkennen" ist : Die Sprache, die eine Turingmaschine erkennt, ist die Menge aller Zeichenfolgen / Eingaben, für die die Turingmaschine akzeptiert.

Interessanterweise gibt es
quelle
2
Willkommen in der Informatik ! Ihre Antwort ist (IMO) korrekt, aber ich denke nicht, dass sie zu den bereits vorhandenen Antworten beiträgt. Wir haben viele unbeantwortete Fragen, und es wäre viel interessanter und produktiver, eine dieser Fragen zu beantworten, als bestehende Antworten zu wiederholen.
David Richerby
1
Vielen Dank! Ich habe die aktuell akzeptierte Antwort zunächst nicht gesehen (was ich für gut halte), weil sie so kurz war, und ich hatte das Gefühl, dass die anderen Antworten die Frage nicht einfach beantworteten.
Interessanterweise
1

Die Antwort darauf hängt davon ab, was Sie genau verstehen, wenn Sie "Turing-Maschine" meinen. Jedes Rechenmodell besteht aus drei Komponenten (hier auf Entscheider / Akzeptoren beschränkt):

  • Syntax,
  • Semantik,
  • Akzeptanzkriterium.

Bei Turing-Maschinen ist die Syntax das Tupel aus Statusmenge, Alphabeten, Übergangsfunktion usw. Die Semantik wäre die Definition einer Berechnung , dh zu beschreiben, wie die Übergangsfunktion angewendet wird, um den Bandinhalt nach einigen Schritten abzuleiten. Das Akzeptanzkriterium lautet: "Wenn dies geschieht, hören wir auf und das Ergebnis ist das".

Sind Turing-Maschinen für Sie nur Syntax und Semantik, oder enthalten Sie auch das Akzeptanzkriterium? Wenn Sie das erstere tun, kann jedes TM mehrere Sprachen akzeptieren, indem verschiedene Akzeptanzkriterien verwendet werden. Sie können sich sogar Akzeptanzkriterien ausdenken, die mehrere akzeptierte Sprachen zulassen (z. B. Zwei-Parameter-TMs). Wenn Sie Letzteres tun, gibt es keinen Spielraum und das übliche Akzeptanzkriterium erlaubt tatsächlich genau eine Sprache pro TM (dieses Typs).

Die übliche Definition und Verwendung des Begriffs in TCS umfasst alle drei Komponenten. Das macht Sinn , weil sich insbesondere die Akzeptanzkriterium Änderung der Klasse von Objekten ändern der Automat stellt drastisch , so dass wir brauchen das Kriterium festlegen, um zu wissen, worüber wir sprechen.

Vergleichen Sie beispielsweise endliche Automaten und Büchi-Automaten . Syntax und Semantik sind genau gleich, aber einer akzeptiert endliche Wörter, während der andere unendliche Wörter akzeptiert!
Versuchen Sie herauszufinden, was passiert, wenn Sie das Akzeptanzkriterium von Büchi-Automaten in die TM-Definition einfügen.

Warum ist nun das übliche Akzeptanzkriterium sinnvoll? Solange Sie sich auf die Sprache der endlichen Zeichenketten beschränken, ändert sich auf konzeptioneller Ebene nicht viel, wenn Sie mehrere Sprachen pro TM haben: Wir werden weiterhin die gleichen Sprachen akzeptieren können. Wir bleiben also beim einfacheren Modell. Das heißt jedoch nicht, dass ein komplizierteres Modell für die Modellierung in Anwendungen nicht nützlich sein kann - dies würde jedoch den Rahmen von TCS (das die definitorische Autorität besitzt) sprengen.

Raphael
quelle
0

M1L1L2L1L2s1s1L1s1L2M1s1s1L2M1s1sL2sL1

MLsLMssMsL

sLMs

ATM

user3730788
quelle
Es ist nicht notwendig zu beweisen, dass ein TM nur eine Sprache erkennt: Dies ergibt sich unmittelbar aus der Definition von "erkennen". Angesichts dieser Definition ist nicht einmal klar, was es bedeutet, dass ein TM mehr als eine Sprache akzeptiert (wie Sie in Ihrem ersten Satz annehmen) oder ob ein Abzug von einer solchen Annahme (wie in Ihrem dritten Satz) gültig ist. Der Beweis durch Widerspruch funktioniert nur, wenn die Ableitungen wasserdicht sind: Hier könnte der Fehler in der Annahme liegen, wie sich ein TM verhält, das ein TM erkennt, und nicht in der Annahme, dass eine solche Maschine existiert.
David Richerby
-2

Eine Sprache ist eine Reihe von Zeichenfolgen. Ist die Vereinigung der beiden Sprachen L1 und L2 nicht eine Reihe von Zeichenfolgen (nennen wir sie L3) und wäre das auch eine andere Sprache? Wenn die Turing-Maschine dann beide Sprachen erkennt, erkennt sie L3, eine einzelne Sprache.

Joe Cash
quelle
2
Die Turing-Maschine erkennt jedoch nicht beide Sprachen, es sei denn, sie sind tatsächlich gleich. Das Erkennen von L1 bedeutet, dass keine Zeichenfolge außerhalb von L1 akzeptiert wird. L2 zu erkennen bedeutet, dass es nichts außerhalb von L2 akzeptiert. Wenn L1 und L2 unterschiedlich sind, kann es nicht beide erkennen.
David Richerby
-3

Keine anderen Antworten weisen auf die Existenz der Universal-Turing-Maschine (n) hin, wie sie zuerst von Turing in seinem stoppenden Beweis beschrieben / entdeckt wurden. ja, ein TM akzeptiert eine einzige rekursiv aufzählbare Sprache, aber die UTM kann jede rekursiv aufzählbare Sprache erkennen, wenn sie in der Eingabe zusammen mit der Eingabezeichenfolge codiert ist. Die Frage hat also eine gewisse zenartige Qualität. TMs akzeptieren nur eine Sprache und alle möglichen codierbaren Sprachen.

vzn
quelle
4
Nein. Eine universelle Turingmaschine akzeptiert die einzelne Sprache {M,xM akzeptiert x} für etwas Kodierung -von Turingmaschinen und Eingängen.
David Richerby
und wie unterscheidet sich das von dem, was geschrieben steht?
vzn
2
Das Erkennen von Sprachcodierungen ist nicht dasselbe wie das Erkennen von Sprachen.
David Richerby
ja genau wie angegeben
vzn
1
@DavidRicherby Ich denke, das ist eine Frage der Perspektive. Man kann ein universelles TM mit Sicherheit so betrachten, dass es viele Sprachen akzeptiert. schreibe es einfach als{(m,x)m=M,} und schauen Sie sich Sprachen von x für jede feste Nummer m(currying / smn). Die Beschränkung von TMs auf einen Parameter ist universell, aber nicht erforderlich.
Raphael