imported>Minimalpolynom: /* growthexperiments-addlink-summary-summary:1|1|0 */

2025-02-24T19:11:06Z

growthexperiments-addlink-summary-summary:1|1|0

Neue Seite

{{Dieser Artikel|beschreibt die Entscheidbarkeit einer mathematischen Eigenschaft. Für andere Formen der Entscheidbarkeit siehe [[Entscheidung]].}}

In der [[Theoretische Informatik|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 „kein“ solches Entscheidungsverfahren 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.<ref>Arnim Regenbogen, Uwe Meyer (Hrsg.): ''Wörterbuch der philosophischen Begriffe.'' Sonderausgabe. Meiner, Hamburg 2006, ISBN 3-7873-1761-9, „entscheidbar“.</ref>

Während die wichtigsten [[Syntax|syntaktischen]] Eigenschaften von [[Computerprogramm|Programmen]] entscheidbar sind, sind im Allgemeinen nach dem [[Satz von Rice]] beliebige (nichttriviale) [[Semantik|semantische]] Eigenschaften von Programmen unentscheidbar, zum Beispiel die [[Terminiertheit|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ählbarkeit|abzählbaren]] Mengen verwendet. Der Begriff des Algorithmus setzt ein [[Berechnungsmodell]] voraus; wenn nichts Abweichendes gesagt wird, sind die [[Turingmaschine]]n oder ein gleichwertiges Modell gemeint.

== Definition ==
[[Datei:Entscheidungsproblem.svg|mini|Struktur eines Entscheidungsproblems]]

Eine Teilmenge <math>T</math> einer [[Abzählbarkeit|abzählbaren]] Menge <math>M</math> heißt entscheidbar, wenn ihre [[Indikatorfunktion|charakteristische Funktion]] <math>\chi_T\colon M\to \{0,1\}</math> definiert durch
: <math>\chi_T(t) = \begin{cases} 1, & \text{falls } t \in T\\ 0, & \text{sonst}\end{cases}</math>
[[Berechenbarkeit|berechenbar]] ist. Der Entscheidbarkeitsbegriff ist somit auf den Berechenbarkeitsbegriff zurückgeführt.

Bei dieser Definition ist vorausgesetzt, dass alle Elemente der Menge <math>M</math> im Rechner dargestellt werden können. Die Menge <math>M</math> muss [[Gödelnummer|gödelisierbar]] sein. In der Theorie setzt man zum einfacheren Vergleich direkt <math>M=\mathbb{N}</math> oder <math>M = \{0,1\}^*</math> voraus. Im letzteren Fall hat man das Problem als das [[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]] einer [[formale Sprache|formalen Sprache]] dargestellt.

Da nur abzählbare Mengen gödelisierbar sind, ist der Begriff der Entscheidbarkeit für [[Überabzählbarkeit|überabzählbare]] Mengen wie die der [[reelle Zahl|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:
# Inkonsistenz: [[Paradoxon|Paradoxien]] oder [[Antinomie]]n 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 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 [[Vollständigkeit (Logik)|unvollständig]].

Entscheidbarkeit ist eine Eigenschaft von [[Prädikat (Logik)|Prädikaten]], und nicht von Aussagen. Das Prädikat ist dabei als [[Wohldefiniertheit|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“.<ref>[[David Hilbert]], [[Wilhelm Ackermann (Mathematiker)|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).</ref> „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.“<ref>[[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).</ref>

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 [[Gottlob Frege|Frege]], [[Alfred N. Whitehead|Whitehead]] und [[Bertrand Russell|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)?“<ref>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).</ref>

[[Kurt Gödel]] veröffentlichte 1931 ein Werk zum Entscheidungsproblem; der Brite [[Alan Turing]] (1912–1954) formulierte in seiner für diesen Zweig der Mathematik grundlegenden Arbeit ''<span dir="ltr" lang="en">On Computable Numbers, with an Application to the “Entscheidungsproblem”</span>'' (28. Mai 1936) Gödels Ergebnisse von 1931 neu. Er ersetzte dabei Gödels universelle, arithmetisch-basierte formale Sprache durch einfache, formale Geräte, die als [[Turingmaschine]] bekannt wurden.

Der Logiker [[Heinrich Scholz (Logiker)|Heinrich Scholz (1884–1956)]] erbat (und erhielt) von Turing 1936 ein Exemplar dieser Arbeit.<ref>Das Exemplar wurde am ''Institut für Informatik'' der [[Westfälische Wilhelms-Universität|Westfälischen Wilhelms-Universität]] in [[Münster]] von Achim Clausing gefunden ([[Westfälische Nachrichten]]. 28. Januar 2013: ''Auf den Spuren eines Pioniers: In der Unibibliothek Münster liegen Originaldrucke des Informatikers Alan Turing''; [https://www.wn.de/Muenster/2013/01/Auf-den-Spuren-eines-Pioniers-In-der-Unibibliothek-liegen-Originaldrucke-des-Informatikers-Alan-Turing online]).</ref> Auf Basis dieser Arbeit hielt Scholz (laut Achim Clausing) „das weltweit erste Seminar über Informatik“.

== Beispiele ==
Alle [[Endliche Menge|endlichen]] Mengen, die Menge aller geraden Zahlen und die Menge aller [[Primzahlen]] sind entscheidbar. Zu jeder entscheidbaren Menge ist auch ihr [[Komplement (Mengenlehre)|Komplement]] entscheidbar. Zu zwei entscheidbaren Mengen sind deren [[Schnittmenge]] und deren [[Vereinigungsmenge]] entscheidbar.

=== Halteprobleme ===
Das [[Halteproblem]] beschreibt die Frage, ob ein [[Algorithmus]] mit einer Eingabe [[Terminiertheit|terminiert]]. [[Alan Turing]] wies die Unentscheidbarkeit dieser Frage nach. Formaler ist das Halteproblem die Eigenschaft von Paaren von Algorithmus und Eingaben, dass der Algorithmus für die Eingabe [[Terminiertheit|terminiert]], das heißt nur endlich lange rechnet. Auch das gleichmäßige Halteproblem, nämlich die Eigenschaft von Algorithmen, für jede Eingabe schließlich zu halten, ist unentscheidbar.

Das Halteproblem für viele schwächere Berechnungsmodelle, etwa [[linear beschränkte Turingmaschine]]n, ist hingegen entscheidbar.

=== Gültigkeit in der Aussagenlogik ===
Die Gültigkeit im Aussagenkalkül ist entscheidbar.<ref>Hilbert/Ackermann: ''Grundzüge.'' 6. Auflage. (1972), S. 119.</ref> Bekannt ist das Komplement dazu, das [[Erfüllbarkeitsproblem der Aussagenlogik]]. Ein Entscheidungsverfahren ist die Methode der [[Wahrheitstafel]]n.

=== 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,<ref>[[Willard Van Orman Quine]]: ''Grundzüge der Logik.'' 8. Auflage. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4, S. 247.</ref> sondern lediglich für Teilbereiche der Prädikatenlogik, wie die Prädikatenlogik mit einstelligen Prädikaten erster Stufe gelöst.<ref>Lothar Czayka: ''Formale Logik und Wissenschaftsphilosophie. Einführung für Wirtschaftswissenschaftler.'' Oldenbourg, München u. a. 1991, ISBN 3-486-20987-6, S. 45.</ref>

=== Lösbarkeit Diophantischer Gleichungen ===
Eine Polynomgleichung nennt man diophantisch, wenn alle Koeffizienten ganzzahlig sind und nur ganzzahlige Lösungen gesucht werden. Die Eigenschaft von [[Diophantische Gleichung|Diophantischen Gleichungen]], eine Lösung zu haben ([[Hilberts Liste von 23 mathematischen Problemen|Hilberts zehntes Problem]]), ist unentscheidbar. Die Lösbarkeit von [[Lineare diophantische Gleichung|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: <math>\left(a,aba\right), (ab,bb), (baa,aa)</math> hat die Lösung <math>\left(1,3,2,3\right)</math>, denn es gilt
<math>a\cdot baa \cdot ab \cdot baa = abaaabbaa = aba \cdot aa \cdot bb \cdot aa</math>.

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

=== Physik ===
Nach Toby Cubitt, David Perez-Garcia, Michael Wolf ist das folgende Problem aus der quantenmechanischen [[Vielteilchentheorie]] unentscheidbar.<ref>Cubitt, Perez-Garcia, Wolf: ''Undecidability of the spectral gap'', Nature, Band 528, 2015, S. 207, [https://arxiv.org/abs/1502.04573 Arxiv Preprint]</ref> Gegeben sei die Hamiltonfunktion eines quantenmechanischen Vielteilchenproblems. Hat das Spektrum eine Lücke vom ersten angeregten Zustand zum Grundzustand oder nicht? Die Autoren konstruierten explizit eine Familie von Quantenspinsystemen auf einem zweidimensionalen Gitter mit translationsinvarianter Nächstnachbar-Wechselwirkung, bei denen die Frage der Spektrallücke unentscheidbar ist. Sie kombinierten [[Komplexitätstheorie]] von Hamiltonoperatoren mit Techniken aperiodischer Parkettierung und übersetzten das Problem in ein Halteproblem einer Turingmaschine. Auch andere Niedrigenergieeigenschaften des Systems sind unentscheidbar.

== Verwandte Begriffe ==
Eine allgemeinere Klasse als die entscheidbaren Mengen sind die [[Semi-entscheidbare Menge|rekursiv aufzählbaren oder semi-entscheidbaren Mengen]], bei denen lediglich für „ja“ 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 ==
* [[Äquivalenzproblem]]
* [[Berechenbarkeit]]
* [[Endlichkeitsproblem]]
* [[Leerheitsproblem]]
* [[Postsches Korrespondenzproblem]]
* [[Semi-entscheidbare Menge]]

== 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)
* {{Literatur | Autor= Hartley Rogers| Titel= Theory of recursive functions and effective computability| Verlag= McGraw-Hill| Jahr=1967 }}
* {{Literatur | Autor= [[Uwe Schöning]] | Titel= Theoretische Informatik – kurzgefasst | Auflage= 4 | Verlag= Spektrum | Jahr= 2000 | ISBN= 3-8274-1099-1 | Seiten= 122ff}}

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Logik]]
[[Kategorie:Berechenbarkeitstheorie]]

Entscheidbarkeit - Versionsgeschichte

imported>Minimalpolynom: /* growthexperiments-addlink-summary-summary:1|1|0 */