# Hilfe bei Turing Maschine



## Wirtschaftsinformatiker (12. Jun 2022)

Kann jemand es beweisen, warum L aufzählbar ist aber nicht entscheidbar?


----------



## thecain (12. Jun 2022)

Postest du jetzt nur noch die Aufgaben? Zu deiner Frage: Bestimmt kann das jemand und du bald auch, wenn du übst


----------



## Wirtschaftsinformatiker (12. Jun 2022)

thecain hat gesagt.:


> Postest du jetzt nur noch die Aufgaben? Zu deiner Frage: Bestimmt kann das jemand und du bald auch, wenn du übst


Ich weiß nicht  wie ich diese Aufgabe lösen kann, brauche Hilfe, um diese Aufgabe zu  lösen.


----------



## KonradN (12. Jun 2022)

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 (12. Jun 2022)

KonradN hat gesagt.:


> 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 (12. Jun 2022)

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.


----------



## mihe7 (12. Jun 2022)

Wirtschaftsinformatiker hat gesagt.:


> Ich habe meine Unterlagen nochmal geguckt aber ich verstehe noch nicht, warum L aufzählbar ist.


Was muss denn gelten, damit L aufzählbar ist?


----------



## httpdigest (12. Jun 2022)

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. (13. Jun 2022)

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 (13. Jun 2022)

httpdigest hat gesagt.:


> Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:
> 
> L = { ... }
> 
> ...


Ich kenne alle Bedeuteung von Notation aber ich weiß nicht, wie ich es beweisen soll


----------



## M.L. (13. Jun 2022)

Wirtschaftsinformatiker hat gesagt.:


> wie ich es beweisen soll


Im Grund wie bei einem mathematischen Beweis: was ist gegeben, was ist gesucht, auf welche _bewiesenen_ Aussagen / Theorien kann man sich (im Idealfall 100%-ig) verlassen ?  Dann wird umgeformt bis die Aussage erbracht ( und bewiesen)  ist.


----------



## mihe7 (13. Jun 2022)

Wirtschaftsinformatiker hat gesagt.:


> Ich kenne alle Bedeuteung von Notation aber ich weiß nicht, wie ich es beweisen soll


Anfang: s.. #7


----------



## Wirtschaftsinformatiker (13. Jun 2022)

httpdigest hat gesagt.:


> 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.
> ...


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.


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


----------



## Wirtschaftsinformatiker (13. Jun 2022)

httpdigest hat gesagt.:


> Zuerst einmal können wir ja die Notation klären, um überhaupt zu verstehen, was hier bewiesen werden muss:
> 
> L = { ... }
> 
> ...


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 (13. Jun 2022)

Wirtschaftsinformatiker hat gesagt.:


> 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.


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


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.


----------

