Hi zusammen! Ich komme gerade aus einer Klausureinsicht. Die Klausur habe ich zwar bestanden, zu einer Aufgabe habe ich aber auch nach einiger Zeit jetzt keinen Ansatz gefunden und meine Hoffnung, es würde vielleicht eine Musterlösung zur Verfügung gestellt hat sich nicht bestätigt. Das Problem lautet wie folgt:

Wie ihr seht beschränkte sich mein kläglicher Ansatz in der Klausur auf das Wiederkäuen der Definitionen. 0,5 hat es gebracht. Seitdem habe ich mir die folgenden Gedanken gemacht: Wir müssen eine TM konstruieren, sodass, wenn diese TM-InfiniteDifferent entscheidet, sie sozusagen "aus Versehen" das Halt-for-Epsilon Problem mitentscheidet. Dafür habe ich aber irgendwie keinen Ansatz. Ideen die ich hatte sind z.B. ob man irgendwie aus dem Ergebnis ableiten kann, in welcher der Mengen epsilon enthalten ist. Oder ob man eine TM konstruieren kann, die erst TM-InfiniteDifferent entscheidet und dann genau dann akzeptiert wenn eine zweite TM für epsilon hält. Aber es ist vielleicht schon merklich: Mittlerweile verwirre ich mich eher selbst. Google ist kein Helfer, weder auf Englisch noch auf Deutsch.

Und nur falls das noch nicht klar geworden ist: Die Klausur ist zurückgegeben und bewertet, siehe Screenshot. Außerdem ist mir bewusst, dass der Satz von Rice das Problem trivial löst, und ich könnte auch noch andere Reduktionen angeben, die zeigen, dass TM-InfiniteDifferent unentscheidbar ist. Ich bin nur neugierig und an diesem Punkt ehrlicherweise auch frustriert, dass ich nicht auf die gewollte Lösung komme. Die Aufgabe soll ja in ca. 20min unter Klausurbedingungen lösbar sein!

Danke schonmal im Voraus!