Hallo,
1.) Ich wollte mal fragen, warum das Halteproblem rekursiv-Aufzählbar ist?
Bekanntlich ist ja das Halteproblem nicht entscheidbar und das bedeutet ja das H und das komplement von H nicht Aufzählbar sein können?

2.) Bei Greedy-Algorithmus kann ja eine getroffene Entscheidung nicht rückgängig gemacht werden. Warum nicht?
Gib es Algorithmen die eine getroffene Entscheidung wieder rückgängig machen können?

1.) Ich wollte mal fragen, warum das Halteproblem rekursiv-Aufzählbar ist?
Bekanntlich ist ja das Halteproblem nicht entscheidbar und das bedeutet ja das H und das komplement von H nicht Aufzählbar sein können?

Tja, das hatte ich auch nicht so recht verstanden, warum das Ding aufzaehlbar ist. In den Folien steht's ja: Entweder haelt das Ding oder es laeuft unendlich weiter, mehr Moeglichkeiten gibt es nicht. Nur kam es mir ein bisschen komisch vor, unendlich warten zu muessen, um festzustellen, dass eine bestimmte Maschine + Eingabewort nicht haelt….

Vielleicht ist nur das Komplement nicht aufzaehlbar? Das waeren ja gerade die nicht haltenden Dinger. Hmm. Theorinix? ;-)

2.) Bei Greedy-Algorithmus kann ja eine getroffene Entscheidung nicht rückgängig gemacht werden. Warum nicht?
Gib es Algorithmen die eine getroffene Entscheidung wieder rückgängig machen können?

Naja, das ist [ein / das] Hauptcharakteristikum eines Greedy-Algorithmus. greedy = gierig…
Daraus folgt ja, dass eben nicht staendig neue Moeglichkeiten durchgeroedelt werden, sondern der Suchraum bestaendig kleiner wird. Natuerlich muss das Problem geeignet sein fuer einen Greedy-Algo, Gegenbeispiel die Muenzrueckgabe.

Das Halteproblem ist deswegen aufzählbar, weil Du eine Maschine bauen kannst, zumindest theoretisch, die Dir nach und nach diejenigen Programme auswirft, die halten.

Diese halten nämlich nach irgendeiner Anzahl von Schritten an, also gibst Du jedem nur eine Anzahl n an Schritten und dann wirfst Du diejenigen aus, die nach dieser Anzahl bereits zum Halten gekommen sind. Im nächsten Durchlauf erhöhst Du n um 1 , beginnst die Programmdurchläufe von vorn und erhältst die Programme, die bei n+1 Schritten halten, und so fort. Bei einer endlichen Anzahl an Programmen erhältst Du irgendwann alle Programme, die halten, musst aber trotzdem bis in alle Ewigkeit Deine Maschine laufen lassen, da ja diejenigen, die zu einem Zeitpunkt x nicht angehalten haben, irgendwann in einem Zeitpunkt y anhalten könnten.

Selbst bei einer unendlichen Anzahl an Programmen funktioniert dies in der Theorie, auch wenn wir uns alle einig sind, daß kein Programm mehr als die initiale Anzahl an Schritten durchlaufen könnte, aber es könnte ja eine Maschine geben, auf der alle gleichzeitig ablaufen, oder?

Ist alles schwer vorstellbar, aber wenn Du Dich darauf einläßt, daß Unendlichkeit irgendwie doch begrenzt ist, dann erkennen wir den Sinn mit unserem auf Endlichkeit ausgerichteten Gehirn schon. Nach einer unendlichen Anzahl von Programmdurchläufen mit n Schritten beginnt dann eben der nächste Schritt mit n+1 Schritten.

Auf Eurem aktuellen Aufgabenzettel ist genau so ein Algorithmus gefordert, nämlich Branch-and-Bound. Sehr viele Algorithmen sind nicht greedy, nämlich diejenigen, die nach der optimalen Lösung streben. Greedy sorgt dafür, daß Du nicht zuviele Schritte machen musst, und akzeptiert im Gegenzug, daß Du vielleicht nicht die optimale Lösung des Problems erhältst.