Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Unentscheidbarkeitsbeweis mit Reduktion
Hallo,
am 20. Oktober schreibe ich eine Klausur in Theoretischer Informatik.
Wir haben von Herrn Dr. Milius eine Probeklausur erhalten. Folgende Aufgabe verstehe ich nicht:
Ich würde vom allgemeinem Halteproblem reduzieren und zeigen, dass es entscheidbar wäre, wenn L = {c(M1)c(M2) | M1 und M2 sind Turingmaschinen und L(M1)⊇L(M2)} entscheidbar wäre.
Doch was ist hier eigentlich gemeint? Ist im Kontext der Aufgabenstellung mit „folgende Sprache nicht entscheidbar“ gemeint, dass das das Wortproblem der Verkettung dieser beiden Sprachen nicht entscheidbar ist?
Und was genau soll mir der Hinweis sagen?
Danke vorab für jede Hilfe.
LG Forumsnutzer
Auf welche zwei Sprachen beziehst du dich mit „beide“? Meinst du L und Lε aus der Aufgabenstellung? Dann nein. Ich denke, der Hinweis soll dir sagen, dass du L auf Lε reduzieren sollst. In Formeln Lε <= L (falls ihr diese Notation hattet).
Lε ist eine recht offensichtlich unentscheidbare Sprache – eben eine Variante des klassischen Halteproblems. Hattet ihr Lε in der Vorlesung?
Lass uns also L auf Lε reduzieren. Dazu musst du eine Funktion f: Lε → L angeben, die bestimmte Bedingungen erfüllt. Eine dieser lautet: für w in {0,1}* haben wir: [m]w in Lε <=> f(w) in L[/m]
Lass uns erstmal die Richtung => betrachten, um f zu konstruieren. Sei w in Lε, d.h. w = c(M) und ε in L(M) – also eine Kodierung einer Turingmaschine, die auf leerer Eingabe akzeptierend hält. Wir müssen nun M1 und M2 konstruieren, sodass L(M1) ⊇ L(M2) und das genau kodiert, dass ε in L(M). Wähle also z. B. M2 := M und M1 als eine der vielen möglichen Turingmaschinen, die nur für ε akzeptierend hält. Lass uns die ausgewählte TM M* nennen. (Eine solche TM kannst du selbstverständlich konstruktiv angeben. Ich lass das hier mal weg.)
Wir definieren f also via: [m]f(w) = if (w = c(M) for some M via syntax check) { c(M*)c(M) } else { 0 }[/m]
Schaffst du es alle Bedingungen an f zu zeigen, damit f eine Reduktionsfunktion ist? Also [m]w in Lε <=> f(w) in L[/m] und dass f berechenbar ist. (Habe ich eine vergessen?)
Zusatzaufgabe für dich: wie kannst du den Beweis abändern, damit er stattdessen L auf das Halteproblem reduziert? Es sind nur kleine Änderungen – die Idee bleibt gleich.
1 „Gefällt mir“
Moment, bist du eigentlich derjenige, mit dem ich mal über das Informatikstudium an sich telefoniert habe? 
[quote=Marcel[Inf]]
Moment, bist du eigentlich derjenige, mit dem ich mal über das Informatikstudium an sich telefoniert habe?
[/quote]
Guten Abend,
vielen Dank für die äußert schnelle Antwort! - die ich nun nachzuvollziehen versuche,
(bin heute erst gegen 17:00 Uhr von der Arbeit gekommen, und hatte gar nicht mit einer so schnellen Antwort gerechnet)
Ja, erinnere ich mich richtig erinnere, dass Du N**** bist, der Marcel als Deckname benutzt?
Vielen Dank nochmal für das Gespräch! - denn ich habe mich inzwischen entschieden für Informatik als zweites Unterrichtsfach.
Würde mich später hier nochmal etwas schreiben, wenn ich noch Rückfragen zu Deinen Erklärungen habe.
LG M****** 
Ich muss gestehen, bis jetzt bin ich nicht entscheidend vorangekommen.
Da ich leider ein Anfänger bin, muss ich mich vorrangig natürlichsprachlich artikulieren:
Ich verstehe die Reduktion vom Leerheitsproblem so.
Beispielsweise kann man vom Komplement des Halteproblems [Gegeben eine Maschine M und Wort w: Hält M nicht an auf Wort w?] reduzieren auf das Leerheitsproblem, indem man eine Maschine M’ baut, die die gleichen Ja- und Nein-Instanzen aufweist wie M, aber umgebaut wird mit gewissen Eigenschaften.
Baue M’ also wie folgt:
• Falls Eingabewort ɛ, schreibt M’ w auf das Band, geht zurück in die Startposition und führt M aus auf w.
• Falls M anhält auf w, hält M’ ebenfalls an.
Gäbe es eine Maschine M’, die bei Eingabe des leeren Wortes anhielte, so wäre ihr Dasein ein Beleg für die Entscheidbarkeit des Gegenstücks zum Halteproblem. Da aber das (Gegenstück vom) Halteproblem nicht entscheidbar ist, ist auch das Leerheitsproblem nicht entscheidbar.
Ich finde die Aufgabenstellung allerdings sehr komisch formuliert.
L = {c(M1)c(M2) | M1 und M2 sind Turingmaschinen und L(M1) ⊇ L(M2)}.
Welche Bewandtnis hat es denn für den Reduktionsbeweis, dass L(M2) eine Teilmenge von L(M1) ist?
Und ist mit Unentscheidbarkeit von L die Frage gemeint, ob das Wortproblem für L unentscheidbar ist?
Und was ist eigentlich eine Sprache L {c(M1)c(M2)}? Eine Sprache, die aus der Verkettung zweier kodierter Turingmaschinen besteht?
Was genau bedeutet das?
Servus,
jetzt bin ich nicht Marcel[Inf], der dir hier antwortet, aber vlt. passt das ja auch.
Was du beschreibst, ist nicht ganz das Komplement des Halteproblems, sondern eher ein Nicht-Halteproblem. Sprachen sind ja schlussendlich nur Mengen von Wörtern über einem gewissen Alphabet S (also Teilmengen von S^), weswegen das Komplement vom Halteproblem (also S^ \ H) andere Dinge bezeichnet als das hier beschriebene Nicht-Halteproblem.
Zudem ist das Leerheitsproblem eigentlich, ob eine Sprache leer ist, also sie kein Wort akzeptiert. Was hier eigentlich beschrieben ist, hat verschiedene Namen unter anderem auch initiales Halteproblem oder eventuell Leeres-Wort-Problem.
Nein, das funktioniert so nicht. Aber von Grund auf: Beweise per Reduktionen funktionieren, indem wir eine total berechenbare Funktion f: S_1^* → S_2^* angeben, so dass der folgende Zusammenhang erfüllt ist:
[m]x ist Element von L1 <=> f(x) ist Element von L2. (*)[/m]
Dann wird L1 mittels der Funktion f auf L2 reduziert und es gilt, dass wenn L1 unentscheidbar ist auch L2 unentscheidbar ist.
In obigem Beispiel (Halteproblem auf „Leerheitsproblem“) ist deine angegebene Funktion nicht berechenbar, denn du verwendest darin schon die Lösung zum Halteproblem (Punkt 2). Also nochmals etwas formeller:
Wir definieren f also wie folgt:
f(x) = c(Feste_Maschine(c(M), w)) wenn x von der Form c(M)w ist und f(x) = 0 sonst.
Wir konstruieren nun die Feste_Maschine(c(M), w) wie folgt (hier über Angabe eines Algorithmus, da bekannt ist, dass Registermaschine und Turingmaschine von gleicher Ausdrucksstärke sind):
[m]
(1) Die Eingabe sei x;
(2) Starte Turingmaschine M mit Eingabe w; // Dies ist über Simulation zu erledigen → Berechenbar !
(3) wenn x = ε dann
(4) | halte;
(5) sonst
(6) | // Mache hier irgendetwas, da dies nicht relevant ist!
(7) ende
[/m]
Wir zeigen nun die totale Berechenbarkeit: Eine Funktion ist total, wenn sie für jeden Eingabewert einen Ausgabewert produziert. Dies ist sie aber offensichtlich. Bleibt die Berechenbarkeit: Eine Funktion heißt berechenbar, wenn es eine Turingmaschine M gibt, so dass M gestartet mit der Eingabe endet und am Schluss der Funktionswert als Ausgabe steht. Das ist sehr kompliziert nachzuweisen, hier reicht es auf Grundprinzipien abzubilden, von welchen man weiß, dass sie berechenbar sind. Beispielsweise wenn du Wortprobleme mit offensichtlich entscheidbaren Sprachen hast, sind die wiederum entscheidbar. Da muss man dann keine extra Turingmaschine angeben.
Hier ist die Fallunterscheidung mittels Syntaxanalyse entscheidbar (Die Form ist ja nur ein String, das geht in (nahezu) linearer Laufzeit), genauso lässt sich die Turingmaschine Feste_Maschine(c(M), w) kodieren und ausgeben. Also ist die Funktion berechenbar, und damit auch total berechenbar.
Zu zeigen bleibt noch die Äquivalenz, dies ist jedoch einfach:
„=>“: Ist also c(M)w ein Element des Halteproblems (der Sprache dahinter), so dauert Zeile (2) nur endliche Zeit und wir erreichen die Abfrage in Zeile (3). Damit ist c(Feste_Maschine(c(M), w)) ein Element von Lε.
„<=“: Ist also c(M)w kein Element des Halteproblems (der Sprache dahinter), so erreichen wir Zeile (3) niemals (Zeile (2) terminiert ja nicht). Damit ist c(Feste_Maschine(c(M), w)) kein Element von Lε.
Damit ist die Äquivalenz gezeigt und wir haben das Halteproblem auf die Sprache Lε reduziert. Damit ist das Wortproblem für die Sprache Lε nicht entscheidbar.
Hoffentlich eine große, denn das definiert ja genau die Sprache L hier.
Ja. Man nennt eine Sprache L entscheidbar (oder unentscheidbar), wenn das Wortproblem der Sprache (un)entscheidbar ist.
Ja, also in der Sprache befinden sich all diejenigen Wörter, die aus der Verkettung zweier Kodierungen von Turingmaschinen besteht und für dessen Sprachen die Teilmengenbeziehung erfüllt ist. (Daran denken: Eine Sprache ist eine Menge an Wörtern)
Genau das was ich oben schon beschrieben habe. Hier hat dir Marcel[Inf] bereits netterweise eine Reduktionsfunktion gegeben. Du musst nun nur noch zeigen, dass sie total (klar) und berechenbar ist, sowie dass die Äquivalenz von oben (markiert mit *) erfüllt ist.
Bei Fragen gerne weiterfragen und ich hoffe ich konnte dir helfen.
Die Notationen [m]f(x) = … wenn … und … sonst[/m] und [m]f(x) = if(…) { … } else { … }[/m] von uns beiden sind übrigens als dieselbe Notation wie in https://en.wikipedia.org/wiki/Piecewise zu lesen. Bei Reduktionsfunktionen, die so definiert werden, ist es besonders wichtig, dass die Bedingungen aller Zweige entscheidbar sind.* Mit meinem “by syntax check” habe ich genau das ein bisschen angedeutet: üblicherweise definiert man die Notation c(.) (“Gödelisierung”) so, dass der Syntaxcheck, ob eine gegebene Zahl tatsächlich die Gödelisierung einer (und auch welcher!) TM ist, dafür entscheidbar ist.
Noch genauer sagt ist meine Notation [m]if (w = c(M) for some M via syntax check) { X } else { Y }[/m] so zu lesen, dass die Syntaxanalyse durchgeführt wird und wenn sie erfolgreich ist, dass die betreffende TM, die hinter dem w steckt auch extrahiert wird und im Block X verfügbar ist.
*) das folgende Nitpicking kannst du überspringen, erwähne ich der Vollständigkeit halber: ich vermische hier die Funktionsdefinition und die angedachte Realisierung einer TM, die die Berechenbarkeit dieser zeigen soll. Natürlich kannst du eine Funktion (also eine mathematische; so wie alle Funktionen, von denen hier die Rede ist) definieren mittels der \left{ Zweignotation, sodass alle Bedingungen unentscheidbar sind, die Funktion an sich jedoch berechenbar ist. Etwa [m]f(x) = if (x \in H) { 0 } else { 0 }[/m]. Beide Zweige (also [m]x \in H[/m] und [m]not (x \in H)[/m]) sind unentscheidbar, die Funktion aber trotzdem berechenbar, da sie die konstante Nullfunktion ist. Üblicherweise “denkt” man jedoch intuitiv so, dass man aus der Zweignotation direkt die Vorschrift einer TM extrahieren kann, die die Berechenbarkeit zeigt. Und das ist auch i. O., solange man sich der Edge Cases bewusst ist.
1 „Gefällt mir“
Danke zunächst einmal für Eure großartige Hilfsbereitschaft und die sehr ausführlichen Antworten.
[Folgendes Vorwort ist überspringbar, es befasst sich aber mit meiner aktuellen emotionalen Situation.]
Ich habe keinerlei Mathe-Hintergrund und belegte im Sommer TheoInfo also erstes Fach in Informatik. Ich komme mir seither vor wie jemand, der sich für ein Studium der Japanistik eingeschrieben hat, aber außer „Hallo“ und „Ich heiße“ und „Wie geht’s?“ kein Wort Japanisch kann, nun aber konfrontiert ist mit japanischer Literatur, Gedichtsinterpretation und Grammatikanalyse. Ich finde den Schwierigkeitsgrad, auf den man losgelassen wird, wirklich fies.
Eure Antworten habe ich inzwischen zum dritten oder vierten Mal durchgelesen, aber verstehe nicht was damit gemeint sein soll, einfach weil mir die Denkmuster nicht geläufig sind. Dass mir Herrn Milius’ Skript/Vorlesung da beinahe gar nicht weiterhilft, brauche ich glaub ich kaum zu erwähnen. Es ist ja nicht so, dass ich es nicht versucht hätte. Ein paar Denkfortschritte habe ich Youtube-Videos dieser Art zu verdanken.
Ich hab manches leichtere Thema verstanden, daher rechne ich mir Chancen aus, die Klausur am Dienstag immerhin mit einer 4,0 zu bestehen. Was natürlich berauschend ist für den Lernaufwand. Nun gut, dafür versuche ich aktuell, die Vorkehrungen zu treffen. [Vorwort Ende]
Ich versuche mich mal etwas heranzutasten:
[quote]Was du beschreibst, ist nicht ganz das Komplement des Halteproblems, sondern eher ein Nicht-Halteproblem. Sprachen sind ja schlussendlich nur Mengen von Wörtern über einem gewissen Alphabet S (also Teilmengen von S^), weswegen das Komplement vom Halteproblem (also S^ \ H) andere Dinge bezeichnet als das hier beschriebene Nicht-Halteproblem.
Zudem ist das Leerheitsproblem eigentlich, ob eine Sprache leer ist, also sie kein Wort akzeptiert. Was hier eigentlich beschrieben ist, hat verschiedene Namen unter anderem auch initiales Halteproblem oder eventuell Leeres-Wort-Problem.[/quote]
Ok, Danke, das verstehe ich soweit. Doch wie formuliert sich dann das Komplement vom Halteproblem als Frage?
Wenn die Maschine M anhält, gib Nein aus? Und wenn sie nicht anhält, gibt Ja aus? Wie fragt man danach, wenn nicht mit [Gegeben eine Maschine M und Wort w: Hält M nicht an auf Wort w?]?
Warum ist
berechenbar? Was ist, wenn die Simulation ein M und ein w erhält, bei denen sie nicht anhält? Du sagstest doch, dass mein Punkt
sei ja auch nicht berechenbar. Was ist da der Unterschied?
Was ist eine feste Maschine?
Was ist c von ()? Warum c? Der Code?
Ich verstehe das so: Die Funktion f(x) gibt wieder die Kodierung der Kodierung (doppelte Klammer) einer Festen Maschine namens c(M) zuzüglich eines Wortes w,
falls x von der Form her eine Kodierung der Maschine M zuzüglich des Wortes w entspricht?
Und wenn es nicht dieser Form entspricht, soll f(x) eine 0 ausgeben?
[quote]„=>“: Ist also c(M)w ein Element des Halteproblems (der Sprache dahinter), so dauert Zeile (2) nur endliche Zeit und wir erreichen die Abfrage in Zeile (3). Damit ist c(Feste_Maschine(c(M), w)) ein Element von Lε.
„<=“: Ist also c(M)w kein Element des Halteproblems (der Sprache dahinter), so erreichen wir Zeile (3) niemals (Zeile (2) terminiert ja nicht). Damit ist c(Feste_Maschine(c(M), w)) kein Element von Lε.[/quote]
Ist mit „c(M)w“ immer gemeint eine Kodierung einer Maschine plus ein Wort?
Also beispielsweise: xyxyxyxyxyyyyxyxxyxxxxx wäre eine solche Eingabe, wenn der Anfangsteil eine kodierte Maschine ist, und, sagen wir, die letzen fünf x’e ein Wort w darstellen würden?
Also eine Funktion, die aus einer Eingabe für Lε eine Eingabe macht für L?
Was bedeutet das, evtl. natürlichsprachlich ausgedrückt?
Deine Hilfsbereitschaft in hohen Ehren, aber hier sind viel zu viele Worte nicht in der von meinem kopfeigenen Parser akzeptierten Sprache, so dass sich M(mein Kopf) in einer geistigen Endlosschleife verfängt…
Mit anderen Worten: Ich kapier es nicht. :-/
Ich bitte um Entschuldigung, wenn ich mit meinen womöglich töricht klingenden Fragen nerve!
LG Forumsnutzer
Kein Stress, ich glaube den meisten ist es so ergangen als sie das erste Mal auf eine Reduktion stießen (Mir zumindest).
Ein Wort ist in der Sprache des Komplements des Halteproblems, wenn es entweder nicht einer Kodierung einer Turingmaschine mit anschließender Eingabe entspricht oder, wenn es der Kodierung entspricht, die Turingmaschine gestartet mit der Eingabe nicht anhält. Deine Frage ist schon richtig, aber es fehlen noch sehr viele andere Wörter, die auch in der Sprache sind. Wie fragt man danach:
[Gegeben eine Eingabe x: Ist x nicht Element der Sprache H?]
Ich glaube ich habe dich missverstanden. Ich dachte, dass du die Halteeigenschaft davon abhängig machst, ob M auf w anhält. Sprich, dass dein „Code“ für die Turingmaschine ungefähr wie folgt aussieht:
Falls Eingabewort ɛ, schreibt M’ w auf das Band, geht zurück in die Startposition und führt M aus auf w.
[m]
Lese Eingabe w;
wenn w = ɛ dann
| Schreibe w auf das Band;
| Bewege dich zurück in die Startposition;
| Führe M gestartet mit w aus;
ende
wenn M gestartet mit w anhält dann // (*)
| Halte
ende
[/m]
In diesem Fall fragst du in Zeile m[/m] nach, ob c(M)w ein Element von H ist, du möchtest also das Wortproblem des Halteproblems entscheiden. Das ist nicht möglich, sprich es gibt keine Turingmaschine, welche das berechnen kann. Inzwischen glaube ich allerdings, dass das nur eine Feststellung war und keine direkte Anweisung an die Turingmaschine. Da bitte ich um Verzeihung, denn die erste Zeile von dir ist natürlich berechenbar.
Zu der Frage warum das berechenbar sei? Weil wir nur die Ausgabe der Reduktionsfunktion betrachten, nicht aber die Maschine selbst. Wichtig ist uns, dass wir eine Turingmaschine angeben könnten, welche die durch den Algorithmus beschriebene Turingmaschine ausgeben kann. Das ist aber möglich wegen der Äquivalenz von solchen Algorithmen und Turingmaschinen.
Eine Turingmaschine, welche nur abhängig von den Parametern (hier: Kodierung einer Turingmaschine M und eine Eingabe w) ist und deren Algorithmus fest angegeben werden kann. Dadurch, dass die Maschine hier fest ist, können wir die Turingmaschine in endlicher Laufzeit auf das Ausgabeband schreiben. Sprich wir müssen hier nicht irgendwelche Abfragen treffen um den Code der Maschine zu bekommen.
Naja, wir wollen ein Element der Sprache Lɛ ausgeben, welche ja wie folgt definiert wurde: Lɛ = { c(M) | M ist eine Turingmaschine und ɛ ist ein Element der Sprache L(M). }
Deswegen brauchen wir hier die Kodierung einer Turingmaschine, welche das leere Wort genau dann akzeptiert, wenn x ein Element der Sprache des Halteproblems war. (Wichtig für die Äquivalenz)
Die Turingmaschine, welche wir hier ausgeben wollen ist die vorher beschriebene Feste_Maschine, welche von der jeweiligen Eingabe, sprich der Kodierung einer Turingmaschine und einem Wort, abhängt.
Ja fast, bloß ist die feste Maschine keine Kodierung, sondern eine Beschreibung für eine Turingmaschine, weswegen wir auch hier eine Kodierung bräuchten. Also wenn die Eingabe von der Form her eine Kodierung einer Maschine M zuzüglich des Wortes w entspricht, so geben wir die Kodierung einer Festen Maschine abhängig von der Kodierung c(M) der Maschine M und des Wortes w zurück. Wenn dem nicht so ist, so geben wir 0 zurück.
Ja. Als Kodierung wird meistens auch die Gödelnummer verwendet, da sie halt besonders schöne Eigenschaften hat.
Ich hatte ja ähnliches geschrieben:
In natürlicher Sprache: Gib eine Funktion f an, welche aus einer Eingabe für die Sprache L1 (hier Lε) ein Element der Sprache L2 (hier L) macht. Dabei soll gelten, dass x ein Element der Sprache L1 (hier: Lε) ist nur und nur wenn der Funktionswert f(x) ein Element der Sprache L2 (hier: L) ist.
Die Funktion muss außerdem noch berechenbar sein und darf keinen Fall vergessen (Totalität). Totalität bekommt man meistens sehr einfach geschenkt, da Fallunterscheidung und für die Berechenbarkeit muss man (meistens nur) überprüfen, ob alle Fälle der Fallunterscheidung entscheidbar sind und die Funktionswerte auch in endlicher Zeit ausgegeben werden können.
Ich versuche mal, dass ganze noch etwas ausführlicher zu gestalten:
Wir wollen bei dem Problem nun eine Funktion f konstruieren, welche die obig beschriebene Äquivalenz erfüllt und noch (total) berechenbar ist. Dazu schauen wir uns erstmal nur die Hinrichtung der Äquivalenz an und bemühen uns jetzt da eine Funktion herauszufinden:
Wir fangen an mit einem Wort der Sprache Lε, also eine Kodierung c(M) einer Turingmaschine, welche das leere Wort ε akzeptiert (ε ist ein Element der Sprache von M (nennt man auch L(M))). Wir suchen ein Wort der Sprache L, also zwei Kodierungen von Turingmaschinen M1 und M2, so dass L(M1) ⊇ L(M2) gilt. Die Maschinen dürfen jetzt nur von bekanntem, also von der Maschine M abhängen. Jetzt gibt es verschiedene Möglichkeiten die Maschinen zu wählen.
1. Möglichkeit: Wähle M1 als solche Turingmaschine, welche für jegliche Eingabe hält, und M2 als M. Die Bedingung auf der rechten Seite („L(M1) ⊇ L(M2)“) ist nun klar erfüllt, aber das nützt uns jetzt eher wenig für die Rückrichtung. Denn ist die Kodierung der Turingmaschine M jetzt kein Element des ε-Halteproblems, so wäre die eben konstruierte Folge von Turingmaschinen immer noch ein Element der rechten Seite (also L), denn jegliche Turingmaschine hat eine Sprache, welche weniger oder gleich viele Wörter wie M1 akzeptiert. Hier scheitert also die Rückrichtung der Äquivalenz!
2. Möglichkeit: Wähle M1 als M, und M2 als solche Turingmaschine, welche für keine Eingabe hält. Die Bedingung auf der rechten Seite („L(M1) ⊇ L(M2)“) ist nun klar erfüllt, aber das nützt uns jetzt eher wenig für die Rückrichtung. Denn ist die Kodierung der Turingmaschine M jetzt kein Element des ε-Halteproblems, so wäre die eben konstruierte Folge von Turingmaschinen immer noch ein Element der rechten Seite (also L), denn jegliche Turingmaschine hat eine Sprache, welche mehr oder gleich viele Wörter wie M2 akzeptiert. Hier scheitert also auch die Rückrichtung der Äquivalenz!
3. Möglichkeit: Wähle M1 als M, und M2 als solche Turingmaschine, welche ausschließlich für das leere Wort ε hält. Die Bedingung auf der rechten Seite („L(M1) ⊇ L(M2)“) ist nun wieder klar erfüllt, und diesmal gilt das sogar in der Rückrichtung. Denn ist die Kodierung der Turingmaschine M jetzt kein Element des ε-Halteproblems, so wäre ε kein Element von L(M1), aber ein Element von L(M2). Damit kann dan nicht mehr L(M1) ⊇ L(M2) gelten.
Deswegen entscheiden wir uns jetzt für die dritte Möglichkeit. Sprich wir definieren uns die Funktion so, dass
[m]
.-
| c(M)c(M2) für x = c(M)
f(x) = <
| 0 sonst.
.-
[/m]
gilt, wobei M2 so wie eben in der 3. Möglichkeit beschrieben gewählt wird.
Jetzt fehlt nochmal eine Erklärung wie oben, warum die Äquivalenz gilt (Vergiss nicht die zwei Fälle bei der Rückrichtung: Entweder es erfüllt die Kodierung und akzeptiert das leere Wort nicht oder es erfüllt nicht die Kodierung!) und dass die Funktion total berechenbar ist. Für letztes reicht hier aus zu sagen, dass die Kodierung einer Turingmaschine endlich ist und deswegen der Syntaxcheck auf Kodierung in endlicher Zeit von statten gehen kann. Die Totalität folgt aufgrund der Fallunterscheidung mittels sonst-Fall.
Kein Stress, dafür gibt es ja das Forum 
Ich hoffe ich konnte ein wenig weiterhelfen.
Guten Morgen yq53ykyr,
Hut ab für Deinen langen, sehr ausführlichen Beitrag!
Danke dafür! Also das ein oder andere Missverständnis hast Du dankenswerterweise für mich ausräumen können.
Doch ist der letztliche “Heureka-Moment” bei mir noch ausgeblieben. Das Problem ist auch: meine Fähigkeit zur “Mustererkennung” für diese Art von Aufgabe ist einfach noch viel zu gering ausgeprägt, als dass ich noch große Hoffnung hätte, hier groß zu punkten.
Ich hab jetzt nochmal ne Nacht über deinen Ausführungen geschlafen, aber stelle fest, dass ich trotz stundenlangen Grübelns nicht mal eine Aufgabe zu Hause am Schreibtisch mit Internetz gebacken, wie soll das dann in einer neunzigminütigen Klausur gut gehen? Da ist Geschwindigkeit gefragt.
Deine Mühen waren nicht vergebens, spätestens wenn ich durchfalle, werde ich mir das Thema sicher nochmal gründlicher anschauen, oder eines Tages zum Staatsexamen. Wo es mir noch begegnen wird auf meiner Reise durchs Informatik für Lehramt-Studium, ist mir noch nicht klar. Ein Kumpel von mir, IT-Praktiker, dem ich die Aufgabe gestern gezeigt hatte, musste angesichts der Praxisferne und unserem späteren Einsatz als Realschullehrer angesichts dieser Inhalte nur den Kopf schütteln.
Aktuell habe ich meine Bemühungen auf andere Aufgabentypen verlagert, bspw. Induktionsbeweise. Hier kann ich schon mal einen Lösungsansätze vorlegen, die wir, so Interesse, gerne nochmal besprechen könnten. Ich hoffe, darin einige Punkte noch erbeuten zu können.
LG Forumsnutzer
Hast du dir dieses Fach (“TheoInfWL”?) selbst für den Einstieg in das Lehramt Informatik ausgesucht oder ist es so empfohlen? Solche Themengebiete wie Turingmaschinen und Reduktionsbeweise machen für mich als Einstieg überhaupt keinen Sinn. Selbst Personen, die reine Informatik studieren, hören solche Themen erst im dritten Semester – eben nach u.a. zwei Semestern Mathematik (d.h. formales + abstraktes Denken).
Entscheidbarkeitsprobleme und Reduktions_beweise_ machen einfach keinen Sinn, wenn man formale Herangehensweisen nicht vorher beigebracht bekommen hat.
Normalerweise beginnt das Studium ja im Wintersemester, ich war aber im Sommer bereits erstmalig mit Informatik eingeschrieben.
Dachte, ich wage mich mal an das Fach, in der Modulbeschreibung war nirgendwo die Rede von irgendwelchen vorausgesetzten Vorkenntnissen.
Manche Lehrämtler scheinen dies im zweiten Semester zu belegen.
Nun ja, irgendetwas wollte ich eben belegen, nachdem ich P&F Programmierung abbrach, das zu viel A&D voraussetzte.
[quote=Forumsnutzer]Doch ist der letztliche “Heureka-Moment” bei mir noch ausgeblieben. Das Problem ist auch: meine Fähigkeit zur “Mustererkennung” für diese Art von Aufgabe ist einfach noch viel zu gering ausgeprägt, als dass ich noch große Hoffnung hätte, hier groß zu punkten.
Ich hab jetzt nochmal ne Nacht über deinen Ausführungen geschlafen, aber stelle fest, dass ich trotz stundenlangen Grübelns nicht mal eine Aufgabe zu Hause am Schreibtisch mit Internetz gebacken, wie soll das dann in einer neunzigminütigen Klausur gut gehen? Da ist Geschwindigkeit gefragt.[/quote]Ich habe TheoInf nie selber geschrieben. Aber eine 4,0 ist in BFS und Gloin ohne Verständnis für die Theorie dahinter gut machbar.
[quote=Forumsnutzer]Deine Mühen waren nicht vergebens, spätestens wenn ich durchfalle, werde ich mir das Thema sicher nochmal gründlicher anschauen, oder eines Tages zum Staatsexamen. Wo es mir noch begegnen wird auf meiner Reise durchs Informatik für Lehramt-Studium, ist mir noch nicht klar. Ein Kumpel von mir, IT-Praktiker, dem ich die Aufgabe gestern gezeigt hatte, musste angesichts der Praxisferne und unserem späteren Einsatz als Realschullehrer angesichts dieser Inhalte nur den Kopf schütteln.[/quote]Als Realschullehrer wäre ein Kurs in Microsoft Office am hilfreichsten. In der Informatik geht es aber genauso wenig um Computer, wie in der Astronomie um Teleskope.
https://www.isb.bayern.de/download/15802/lehrplan_informationstechnologie_082008.pdf