Entscheidbarkeit durch Reduktion zeigen

Question

Ich verstehe das Prinzip von Reduktionen nicht ganz. Grob gesagt haben wir zwei Probleme auf die wir immer reduzieren:

spezielle Halteproblem K = {w ∈  {0,1}* | Mw hält bei Eingabe w}

allgemeine Halteproblem H = {w#x | Mw hält bei Eingabe x}

Was ich jetzt verstanden habe ist, dass wir beim spez. Halteproblem eine funktion M' definieren, die den Inhalt ihrer eigenen TM M'w löscht, dann die Eingabe w auf das Band schreibt, zum Anfang geht und sich jetzt genau wie die urprüngliche Maschine Mw verhält.

Und beim allgemeinen Halteproblem ist das genau so, nur dass es zusätzlich eine Eingabe x gibt, oder?

Hier eine Beispielaufgabe:

L = {w | Mw hält auf genau 1000 Eingaben}

Ist diese TM entscheidbar?

Kann mir jemand das Prinzip der Reduktion anhand dieser Aufgabe erklären?

Answer 1

Im Allgemeinen heißt Reduktion ein komplexes Problem auf ein einfacheres zu reduzieren.
Ich nehme mal dein oberes Bespiel:
Das allgemein Halteproblem wäre dein einfacheres Problem.
Wenn ich jetzt irgendwie schaffe, die Eingabe I deines schwierigeren Problems (spezielles Halteproblem) so umzuformen(in deinem Fall mit einer totalen(!!!) Funktion), dass ich am Ende die umgeformte Eingabe I* erhalte, welche ich dann mit dem allgemeinen Halteproblem lösen kann.

Anschließend, erhalte ich dadurch auch eine Lösung des speziellen Problems(weil wir eine totale Funktion benutzt haben verhält sich das der Input so des allgemeinen Halteproblems so wie der ursprüngliche Input).

Dein Beispiel löst dies jetzt nicht direkt, aber hier noch einmal 2 Quellen bei denen das Prinzip hoffentlich klarer wird:
https://www.tu-chemnitz.de/informatik/ThIS/downloads/courses/ss03/ti/Loesungen/Uebung7.pdf

(bis ca. 12:30)