Reduktion Flashcards
1
Q
allgemeine Halteproblem - Definition
A
2
Q
Reduktion - Definition
A
A <= B formalisiert die Intuition “A ist leichter als B” d.h.
“wenn wir B entscheiden könnten, dann könnten wir auch A entscheiden”
3
Q
Reduzierbarkeit Lemma 1 (nicht A)
A
4
Q
Reduzierbarkeit Lemma 2 (entscheidbar)
A
4
Q
A <= B informel
A
A <= B formalisiert die Intuition “ A ist leichter als B” d.h “wenn wir B entscheiden könnten, dann könnten wir auch A entscheiden
5
Q
Halteproblem für Sprachen von Turingmaschinen
A
6
Q
Halteproblem auf dem leeren Band
A
7
Q
Entscheidbarkeit des Halteproblems auf dem leeren Band
A
H_0 ist unentschuldbar. Bewiesen wird das durch eine Reduktion von H auf H_0. Also man zeigt: H <= H_0
