Entscheidbar

Entscheidbar

In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch: 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.[1]

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.

Inhaltsverzeichnis

Definition

Struktur eines Entscheidungsproblems

Eine Teilmenge T einer Menge M heißt entscheidbar, wenn ihre charakteristische Funktion \chi_T: M\to \{0,1\} definiert durch

\chi_T(t)=\begin{cases} 1, & {\textrm{falls~}}t \in T\\ 0, & {\textrm{sonst}}\end{cases}

berechenbar ist. Der Entscheidbarkeitsbegriff ist somit auf den Berechenbarkeitsbegriff zurückgeführt.

Bei dieser Definition ist vorausgesetzt, dass alle Elemente der Menge M im Rechner dargestellt werden können. Die Menge M muss gödelisierbar sein. In der Theorie setzt man zum einfacheren Vergleich direkt M=\mathbb{N} oder M = {0,1} * voraus. Im letzteren Fall hat man das Problem als das Wortproblem einer formalen Sprache dargestellt.

Da nur abzählbare Mengen gödelisierbar sind, ist der Begriff der Entscheidbarkeit für überabzählbare Mengen wie die der reellen Zahlen nicht definiert. Es gibt jedoch Versuche, durch ein erweitertes Maschinenmodell den Begriff der Berechenbarkeit auf reelle Zahlen auszudehnen (z. B. das Blum-Shub-Smale-Modell).

Abgrenzung

Unentscheidbarkeit darf nicht verwechselt werden mit der praktischen oder fundamentalen Unmöglichkeit, einer Aussage einen Wahrheitswert zuzuordnen. Im Einzelnen geht es um folgende Begriffe:

  1. 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.
  2. 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.
  3. 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.

Geschichte

Das Entscheidungsproblem ist „das Problem, die Allgemeingültigkeit von Ausdrücken festzustellen“ [2]. „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.“[3]

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) ?“[4]

Beispiele

Alle endlichen Mengen, die Menge aller geraden Zahlen und die Menge aller Primzahlen sind entscheidbar. Zu jeder entscheidbaren Menge ist auch ihr Komplement entscheidbar. Zu zwei entscheidbaren Mengen sind deren Schnittmenge und deren Vereinigungsmenge entscheidbar.

Halteprobleme

Das Halteproblem für Turingmaschinen ist die Eigenschaft von Paaren von Turingmaschinen und Eingaben, dass die Turingmaschine für die Eingabe terminiert, das heißt nur endlich lange rechnet. Alan Turing zeigte, dass das Halteproblem für Turingmaschinen unentscheidbar ist. Auch das gleichmäßige Halteproblem für Turingmaschinen, nämlich die Eigenschaft von Turingmaschinen, für jede Eingabe schließlich zu halten, ist unentscheidbar.

Das Halteproblem für linear beschränkte Turingmaschinen ist hingegen entscheidbar.

Gültigkeit in der Aussagenlogik

Die Gültigkeit im Aussagenkalkül ist entscheidbar.[5] Bekannt ist das Komplement dazu, das Erfüllbarkeitsproblem der Aussagenlogik. Ein Entscheidungsverfahren ist die Methode der Wahrheitstafeln.

Gültigkeit in der Prädikatenlogik

Das (spezielle) Entscheidungsproblem für die Prädikatenlogik wurde 1928 von David Hilbert gestellt (siehe Hilbertprogramm). Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist (siehe Halteproblem).

Das Entscheidungsproblem ist nicht für die allgemeine Prädikatenlogik[6], sondern lediglich für einen Teilbereich der Prädikatenlogik, nämlich für die Prädikatenlogik "mit einstelligen Prädikaten 1. Stufe“[7] gelöst.

Lösbarkeit Diophantischer Gleichungen

Eine Polynomgleichung nennt man diophantisch, wenn alle Koeffizienten ganzzahlig sind und nur ganzzahlige Lösungen gesucht werden. Die Eigenschaft von Diophantischen Gleichungen, eine Lösung zu haben (Hilberts zehntes Problem), ist unentscheidbar. Die Lösbarkeit von Linearen Diophantischen Gleichungen dagegen ist entscheidbar.

Das Postsche Korrespondenzproblem

Man nennt eine endliche Liste von Paaren nichtleerer Wörter über einem endlichen Alphabet einen Problemfall. Eine Lösung zu einem Problemfall ist eine nichtleere endliche Folge von Nummern für Wortpaare in der Liste, so dass die ersten Komponenten der Wortpaare zusammengesetzt das gleiche Wort ergeben wie die zweiten Komponenten der Wortpaare.

Beispiel: \left(a,aba\right), (ab,bb), (baa,aa) hat die Lösung \left(1,3,2,3\right), denn es gilt a\cdot baa \cdot ab \cdot baa = abaaabbaa = aba \cdot aa \cdot bb \cdot aa.

Das Postsche Korrespondenzproblem, das heißt die Eigenschaft von Problemfällen, eine Lösung zu besitzen, ist unentscheidbar.

Verwandte Begriffe

Eine allgemeinere Klasse als die entscheidbaren Mengen sind die rekursiv aufzählbaren oder semi-entscheidbaren Mengen, bei denen lediglich entweder nur für „ja“ oder nur für „nein“ gefordert wird, dass die Berechnung in endlicher Zeit anhält. Wenn sowohl eine Menge als auch ihr Komplement semi-entscheidbar sind, dann ist die Menge entscheidbar. Das Halteproblem ist semi-entscheidbar, denn die Antwort „ja“ kann immer durch Laufenlassen des Programms gegeben werden. Das Komplement des Halteproblems ist jedoch nicht semi-entscheidbar.

Siehe auch

Einzelnachweise

  1. Arnim Regenbogen, Uwe Meyer (Hrsg.): Wörterbuch der philosophischen Begriffe. Sonderausgabe. Meiner, Hamburg 2006, ISBN 3-7873-1761-9, „entscheidbar“.
  2. David Hilbert, W. Ackermann: Grundzüge der theoretischen Logik. 6. Auflage. Springer, Berlin u. a. 1972, ISBN 0-387-05843-5, S. 119 (Die Grundlehren der mathematischen Wissenschaften 27).
  3. Alfred Tarski: Einführung in die mathematische Logik. 5. Auflage, erweitert um den Beitrag „Wahrheit und Beweis“. Vandenhoeck & Ruprecht, Göttingen 1977, ISBN 3-525-40540-5, S. 145 (Moderne Mathematik in elementarer Darstellung 5).
  4. Patrick Brandt, Rolf-Albert Dietrich, Georg Schön: Sprachwissenschaft. Ein roter Faden für das Studium der deutschen Sprache. 2. überarbeitet und aktualisierte Auflage. Böhlau, Köln u. a. 2006, ISBN 3-412-00606-8, S. 14 (UTB 8331).
  5. Hilbert/Ackermann: Grundzüge. 6. Auflage. (1972), S. 119.
  6. Willard Van Orman Quine: Grundzüge der Logik. 8. Auflage. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4, S. 247.
  7. Lothar Czayka: Formale Logik und Wissenschaftsphilosophie. Einführung für Wirtschaftswissenschaftler. Oldenbourg, München u. a. 1991, ISBN 3-486-20987-6, S. 45.

Literatur

  • Lothar Czayka: Formale Logik und Wissenschaftsphilosophie. Einführung für Wirtschaftswissenschaftler. Oldenbourg, München u. a. 1991, ISBN 3-486-20987-6, S. 45 ff.
  • Willard Van Orman Quine: Grundzüge der Logik. 8. Auflage. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4, S. 142 ff. (Suhrkamp-Taschenbuch Wissenschaft 65), ausführlich.
  • Paul Hoyningen-Huene: Formale Logik. Eine philosophische Einführung. Reclam, Stuttgart 1998, ISBN 3-15-009692-8, S. 226 ff. (Reclams Universal-Bibliothek 9692)

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Rekursiv entscheidbar — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Semi-entscheidbar — Als semi entscheidbare Menge (auch halb entscheidbare Menge) wird in der Berechenbarkeitstheorie eine Menge A bezüglich einer Grundmenge M bezeichnet, wenn ihre partielle charakteristische Funktion definiert durch berechenbar ist. Die Menge M… …   Deutsch Wikipedia

  • gerichtlich entscheidbar — justiziabel; justitiabel …   Universal-Lexikon

  • Entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Entscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Entscheidungsproblem — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Rekursiv entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Semientscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Unentscheidbares Problem — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Unentscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”