Hilfe bei Turing Maschine

KonradN

Super-Moderator
Mitarbeiter
Das wird doch bestimmt in der Vorlesung behandelt worden sein. Bist Du das, was da behandelt wurde, noch mal durchgegangen? Und wenn Du Probleme hast, dem Stoff zu folgen: Es gibt zu den Themen auch meist gute Bücher, die man parallel zu den Vorlesungen lesen kann zum besseren Verständnis.

Denn es ist ja ein generelles Problem. Du solltest also auch überlegen, wie Du deine generelle Herangehensweise so anpassen kannst, dass Du die Vorlesungsinhalte verstehst.
 

Wirtschaftsinformatiker

Bekanntes Mitglied
Das wird doch bestimmt in der Vorlesung behandelt worden sein. Bist Du das, was da behandelt wurde, noch mal durchgegangen? Und wenn Du Probleme hast, dem Stoff zu folgen: Es gibt zu den Themen auch meist gute Bücher, die man parallel zu den Vorlesungen lesen kann zum besseren Verständnis.

Denn es ist ja ein generelles Problem. Du solltest also auch überlegen, wie Du deine generelle Herangehensweise so anpassen kannst, dass Du die Vorlesungsinhalte verstehst.
Ja, mache ich. Ich habe meine Unterlagen nochmal geguckt aber ich verstehe noch nicht, warum L aufzählbar ist.
 

AndiE

Top Contributor
Ich will mal versuchen, etwas Licht in die Sache zu bringen. Für all die Unkundigen wie mich.

Es geht im Prinzip um "Formale Sprachen". Das sind,vereinfacht ausgedrückt Zeichenfolgen, die einem "regulären Ausdruck" entsprechen. Ein Automat erkennt vereinfacht eine Folge von Zeichenfolgen als Zusammenhängend- das ist dann ein "Wort". Es gibt verschiedene Arten, wie ein Automat aufgebaut sein kann. Der Turing-Automat nutzt ein endloses Band, das in viele Zellen unterteilt ist.

Grundsätzlich kann man nun sagen, dass die Gesamtheit der Wörter, die ein Automat( hier eine Turing-Maschine) akzeptiert, eine Sprache ergibt.

Formal meint L={M} also die Sprache, die der Automat M akzeptiert, also alle Wörter, die dem zugrundeliegenden RegEx entsprechen.

Offtopic:

Ich finde die Idee mit dem endlosen Band gar nicht so schlecht, wenn man dem Band einen Akku entgegenstellt. Dann hat man recht wenig Befehle. Mich erinnert das ein bisschen an die Arbeit mit JDBC.
 

httpdigest

Top Contributor
Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:

L = { ... }

Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.

Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.

Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".

{b}* bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also: {b}* = {"", "b", "bb", "bbb", "bbbb", ...}.

Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:

Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.

Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.

Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.

Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrückt.
 

M.L.

Top Contributor
Generell gilt das man sich bei einer bewiesenen Theorie (z.B. aus der theoretischen Informatik, Satz von Rice) auch darauf verlassen kann welche Ergebnisse deren alleinige Anwendung (nicht) liefert.

Beispiel am Java-Code:
- "class Beispielklasse" (kann, muss aber nicht abgeleitet werden)
-"abstract class Beispielklasse" (der Compiler achtet wg. 'abstract' auf (mindestens) eine Ableitung dieser Klasse)
  • "final class Beispielklasse" (der Compiler verbietet wg. 'final' eine Ableitung dieser Klasse)
  • "final abstract class Beispielklasse" (Compilerfehler...)
 

Wirtschaftsinformatiker

Bekanntes Mitglied
Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:

L = { ... }

Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.

Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.

Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".

{b}* bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also: {b}* = {"", "b", "bb", "bbb", "bbbb", ...}.

Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:

Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.

Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.

Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.

Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrückt.
Ich kenne alle Bedeuteung von Notation aber ich weiß nicht, wie ich es beweisen soll
 

Wirtschaftsinformatiker

Bekanntes Mitglied
Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:​

L = { ... }

Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.

Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.

Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".

{b}* bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also: {b}* = {"", "b", "bb", "bbb", "bbbb", ...}.

Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:

Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.

Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.

Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.

Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrücd
Das ist meine Lösung, ist es richtig?
L ist aufzählbar:
Ein Element der Schnittmenge ist zwingend Teil von L(M) ist. Für alle e in L(M) terminiert M.
L kann wie folgt aufgezählt werden.

  1. Alle TM mit einem Zustand die in einem Schritt ε oder b akzeptieren
  2. Alle TM mit höchstens zwei Zuständen die in höchstens zwei Schritten ε oder b oder bb akzeptieren.
  3. Alle TM mit höchstens drei Zuständen die in höchstens drei Schritten ε oder b oder bb oder bbb akzeptieren.
  4. ...
 

Wirtschaftsinformatiker

Bekanntes Mitglied
Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:

L = { ... }

Das ist in diesem Fall die Definition einer Sprache als Menge von Wörtern, die Teil der Sprache sind.
Die geschweiften Klammern sind also eine "Mengendefinition".
In diesem konkreten Fall ist aber die Tatsache, dass eine "Sprache" aus "Wörtern" besteht, gar nicht so wichtig oder entscheidend. Wichtig hier ist, dass wir die Definition einer Menge haben und eine Beschreibung, welche Elemente alle Teil dieser Menge sind. Rein mathematisch gesprochen.

Das <M> mit den etwas gestreckten Klammern ist ein Turing-Maschinen-Programm.

Der Senkrechtstrich bzw. Bar bzw. Pipe bedeutet: "für das gilt: ...".

{b}* bedeutet die Anwendung des Kleeneschen Sterns/Operators und heißt hier einfach nur: Eine beliebige (auch leere) Menge von Konkatenationen des Zeichens "b", also: {b}* = {"", "b", "bb", "bbb", "bbbb", ...}.

Dass das jetzt "b" sein soll oder auch nur eine beliebig häufige Konkatenation von "b" ist hier aber auch eher irrelevant. Viel wichtiger ist, was jetzt damit gemacht wird:

Das umgedrehte "U" Zeichen bedeutet "Schnittmenge" und L(M) bedeutet "Die Sprache, die durch die bereits erwähnte Turingmaschine 'M' akzeptiert wird". Das durchgestrichene Gleichheitszeichen bedeutet dann noch "ungleich" (hier ist von der Ungleichheit zweier Mengen die Rede). Und die durchgestrichene Null soll die leere Menge bedeuten.

Also, alles nochmal in einem Satz: "L ist die Menge aller Turingmaschinen 'M', für die gilt, dass die Sprache {b}* (also Menge von Wörtern mit einer beliebigen Konkatenation von "b") eine Teilmenge der von 'M' akzeptierten Sprache (L) ist." Ob die Teilmenge echt oder unecht ist, wissen wir hier nicht.
Kleiner Hinweis: Wir können aber "echt" annehmen.

Die Tatsache, dass hier derselbe Buchstabe "L" sowohl für die Definition der Menge insgesamt benutzt wird als auch als Teil dieser Definition mit L(M) ist zwar unglücklich, gemeint sind hier aber zwei verschiedene L's , also zwei verschiedene Mengen.

Insgesamt ist die Definition von L hier der Satz von Rice, nur etwas anders ausgedrückt.
Sei für jede Turingmaschine M die Turingmaschine B(M) gegeben durch: Für jedes n ∈ ℕ0 akzeptiert B(M) das Wort bn genau dann, wenn M ein Wort der Länge n akzeptiert.

Dann ist B(M) ∈ L ⇔ {b}* ∩ L(B(M)) ≠ ∅ ⇔ L(M) ≠ ∅.

Das Leerheitsproblem ist aber nicht entscheidbar.
 

Wirtschaftsinformatiker

Bekanntes Mitglied
Kann jemand es beweisen, warum L aufzählbar ist aber nicht entscheidbar?Anhang anzeigen 18452
Ist meine Lösung richtig?
L ist aufzählbar:
L kann wie folgt aufgezählt werden.

  1. Alle TM mit einem Zustand die in einem Schritt ε oder b akzeptieren
  2. Alle TM mit höchstens zwei Zuständen die in höchstens zwei Schritten ε oder b oder bb akzeptieren.
  3. Alle TM mit höchstens drei Zuständen die in höchstens drei Schritten ε oder b oder bb oder bbb akzeptieren.
  4. ...


Sei für jede Turingmaschine M die Turingmaschine B(M) gegeben durch: Für jedes n ∈ ℕ0 akzeptiert B(M) das Wort bn genau dann, wenn M ein Wort der Länge n akzeptiert.

Dann ist B(M) ∈ L ⇔ {b}* ∩ L(B(M)) ≠ ∅ ⇔ L(M) ≠ ∅.

Das Leerheitsproblem ist aber nicht entscheidbar.
 

Neue Themen


Oben