Significations et usages de Entscheidbar

Der Entscheid ist im schweizerischen Recht die Entscheidung der zuständigen Behörde über einen bestimmten strittigen Sachverhalt. Ein Entscheid ergeht sowohl im Einspracheverfahren als auch im Gerichtsverfahren.

  Literatur

•  Robert Hauser, Erhard Schweri: Kommentar zum zürcherischen Gerichtsverfassungsgesetz. Zürich 2002, ISBN 3-7255-4272-4, § 155, S. 515.

  Siehe auch

• Beschluss
• Urteil (Recht)
• Entscheid (Zürcher Zivilprozess)

Bitte den Hinweis zu Rechtsthemen beachten!

-bar ist ein häufiges Suffix beim Adjektiv, das der Wortbildung dient. In den meisten Fällen werden transitive Verben mit Hilfe von -bar zu Adjektiven abgeleitet. Beispiel: aus „heilen“ wird „heilbar“. Die Bedeutung von -bar lässt sich mit können umschreiben, da es auf eine Möglichkeit hinweist: „heilbar“ bedeutet dann, dass jemand „geheilt werden kann“.

  Bedeutungen

Man kann zwei Bedeutungen unterscheiden:

• eine aktivische wie bei „brennbar“, „haftbar“: „Das Holz ist brennbar“ lässt sich deuten als „Das Holz kann brennen“ oder „Das Holz brennt (leicht, nur schwer,…)“; „Peter ist haftbar“ als „Peter kann/ muss (unter bestimmten Umständen) haften.“
• eine passivische wie bei „lieferbar“, „reparierbar“: „Die Ware ist sofort lieferbar“ bedeutet: „Die Ware kann sofort geliefert werden“; „Das Fahrzeug ist nochmal reparierbar“ als „Das Fahrzeug kann nochmal repariert werden.“ Diese Bedeutung wird am meisten verwendet.

  Abweichende Bildungen

In der Werbesprache wurden vereinzelt -bar-Bildungen genutzt, indem regelwidrig Ableitungen aus Adjektiven gebildet wurden. Recht bekannt wurde das Beispiel „unkaputtbar“ für eine neu entwickelte Getränkeflasche aus Kunststoff. ^[1] Nach dem gleichen Muster wurde für Fahrradreifen der Ausdruck „unplattbar“ gebildet. ^[2] Die regelwidrige Bildungsweise weckt die Aufmerksamkeit der Leser und erreicht somit einen für die Werbung erwünschten Effekt.

  Herkunft

Das Suffix -bar geht zurück auf althochdeutsch bāri, das zum Verb beran „tragen“ gehört.

  Produktivität und Ausbreitung

-bar gehört zu den produktiven Wortbildungssuffixen des Deutschen: Es wurden über 2000 Wörter mit diesem Suffix nachgewiesen (Flury 1964). Die Ausbreitung der -bar-Bildungen im Deutschen wurde in Best (2003) untersucht.

  Literatur

• Karl-Heinz Best: Spracherwerb, Sprachwandel und Wortschatzwachstum in Texten. Zur Reichweite des Piotrowski-Gesetzes. In: Glottometrics 6, 2003, 9–34. Zu -bar: S. 17f.
• Duden. Die Grammatik. 7., völlig neu erarbeitete und erweiterte Auflage. Dudenverlag: Mannheim/ Leipzig/ Wien/ Zürich 2005. ISBN 3-411-04047-5
• R. Flury: Struktur- und Bedeutungsgeschichte des Adjektivsuffixes -bar. Keller, Winterthur 1964 (Diss. phil., Zürich)
• Kluge. Etymologisches Wörterbuch der deutschen Sprache. Bearbeitet von Elmar Seebold. 24., durchgesehene und erweiterte Auflage. de Gruyter, Berlin/ New York 2002. ISBN 3-11-017472-3

  Weblinks

•  Wiktionary: -bar – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

  Einzelnachweise

1. ↑ Nina Janich: Werbesprache. Ein Arbeitsbuch. 2., vollständig überarbeitete und erweiterte Auflage. Narr, Tübingen 2001. S. 106. ISBN 3-8233-4974-0.
2. ↑ Diese Form wurde über längere Zeit in einem Göttinger Fahrradladen in einem Aushang verwendet.

Dieser Artikel beschreibt die Entscheidbarkeit einer mathematischen Eigenschaft. Für andere Formen der Entscheidbarkeit siehe Entscheidung.

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.^[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.

  Definition

Struktur eines Entscheidungsproblems

Eine Teilmenge einer Menge heißt entscheidbar, wenn ihre charakteristische Funktion definiert durch

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

Bei dieser Definition ist vorausgesetzt, dass alle Elemente der Menge im Rechner dargestellt werden können. Die Menge muss gödelisierbar sein. In der Theorie setzt man zum einfacheren Vergleich direkt oder 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 konsistenten 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 Teilbereiche der Prädikatenlogik, wie 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: hat die Lösung , denn es gilt .

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

• Berechenbarkeit
• Semi-entscheidbare Menge
• Äquivalenzproblem
• Endlichkeitsproblem
• Leerheitsproblem
• Postsches Korrespondenzproblem

  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)
•  Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.