Das Entscheidbarkeitsproblem

Letztmalig dran rumgefummelt: 12.08.12 13:29:52

	In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch: rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht. Wenn es ein solches Entscheidungsverfahren nicht gibt, dann nennt man die Eigenschaft unentscheidbar. Als Entscheidungsproblem bezeichnet man die Frage, ob und wie für eine gegebene Eigenschaft ein Entscheidungsverfahren formuliert werden kann. Während die wichtigsten syntaktischen Eigenschaften von Programmen entscheidbar sind, sind nach dem Satz von Rice alle (nichttrivialen) semantischen Eigenschaften von Programmen unentscheidbar, zum Beispiel die Terminierung eines Programmes auf einer Eingabe (Halteproblem) oder die Funktionsgleichheit zweier Programme (Äquivalenzproblem). Ursprünglich speziell für die Gültigkeit von Formeln gemeint, wird der Begriff inzwischen für beliebige Eigenschaften auf abzählbaren Mengen verwendet. Der Begriff des Algorithmus setzt ein Berechnungsmodell voraus; wenn nichts Abweichendes gesagt wird, sind die Turingmaschinen oder ein gleichwertiges Modell gemeint.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösunsverfahren Logo für das Entscheidbarkeitsproblem Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Problembeschreibung

	Das Entscheidungsproblem ist „das Problem, die Allgemeingültigkeit von Ausdrücken festzustellen“. „Es handelt sich um das Problem, zu einer gegebenen deduktiven Theorie ein allgemeines Verfahren anzugeben, das uns die Entscheidung darüber gestattet, ob ein vorgegebener, in den Begriffen der Theorie formulierter Satz, innerhalb der Theorie bewiesen werden kann oder nicht.“ Entscheidend ist dabei, ob es ein rein mechanisch anzuwendendes Verfahren, einen Algorithmus, gibt, das in endlich vielen Schritten klärt, ob ein Ausdruck, eine Formel, in einem System gültig ist oder nicht. Nach Frege/Whitehead/Russell war die „Kernfrage der Logiker und Mathematiker: Gibt es einen Algorithmus ..., der von einer beliebigen Formel eines logischen Kalküls feststellt, ob sie aus gewissen vorgegebenen Axiomen folgt oder nicht (das so genannte Entscheidungsproblem) ?“
	Bletchley Park TM - also Turingmaschine ... Entwicklung der Bombas Church'sche These Das Entscheidbarkeitsproblem das HALTE-Problem Bletchley-Park Turingmaschine Bomben Alonzo Church David Hilbert Halteproblem
	Unentscheidbarkeit darf nicht verwechselt werden mit der praktischen oder fundamentalen Unmöglichkeit, einer Aussage einen Wahrheitswert zuzuordnen. Im Einzelnen geht es um folgende Begriffe: Inkonsistenz: Paradoxien oder Antinomien zeigen, dass ein Kalkül Widersprüche enthält, also nicht widerspruchsfrei ist. Die Russellsche Antinomie zum Beispiel zeigte, dass die naive Mengenlehre Widersprüche enthält. Unabhängigkeit: Aussagen, die zu einem widerspruchsfreien Kalkül hinzugenommen werden können, ohne einen Widerspruch zu erzeugen, heißen relativ widerspruchsfrei zu diesem Kalkül. Wenn auch deren Negation relativ widerspruchsfrei ist, dann ist die Aussage unabhängig. Zum Beispiel ist das Auswahlaxiom unabhängig von der Zermelo-Fraenkel-Mengenlehre. Unvollständigkeit: In Kalkülen, die mindestens die Ausdrucksstärke der Arithmetik haben, gibt es wahre Aussagen, die nicht im Kalkül bewiesen werden können. Solche Kalküle nennt man unvollständig. Entscheidbarkeit ist eine Eigenschaft von Prädikaten, und nicht von Aussagen. Das Prädikat ist dabei als wohldefiniert vorausgesetzt, es liefert also für jedes Element der Menge einen definierten Wahrheitswert. Unentscheidbarkeit besagt nur, dass das Prädikat nicht durch einen Algorithmus berechnet werden kann. Aussagen als nullstellige Prädikate betrachtet sind immer entscheidbar, auch wenn ihr Wahrheitswert noch ungeklärt ist. Wenn die Aussage wahr ist, dann ist der Algorithmus, der immer Eins ausgibt ein Entscheidungsverfahren. Sonst ist der Algorithmus, der immer Null ausgibt, ein Entscheidungsverfahren.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	effiziente Lösung nur als rekursiver Algorithmus
	gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf
	Das Flaggen-Problem wird in abgewandelter Form auf jedem Rangierbahnhof, in jedem Warenliefersystem, in der Postzustellung usw. praktisch gelöst

3. Lösungsalgorithmus

	Dies war die zweite Aufgabe des Flaggenproblems, nämlich nicht nur das Umsortieren der Steinchen, sondern auch das Umsortieren so effizient wie möglich zu machen. E. W. Dijkstra, der Entwickler des Flaggenproblems, ist dabei folgendermaßen vorgegangen. Er schrieb ein Programm in PASCAL in dem der gesuchte Algorithmus als Prozedur dargestellt wird. Hier eine vereinfachte Version seines entworfenen Algorithmus in PASCAL (blau sind die Erklärungen):

4. Programmvorschläge

5. Zusammenfassung

6. Weiterführende Literatur

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

7. Links zum Thema

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Mai 2007