Bitte warten! Evaluation läuft... |
Prof.Dr.Christian Wagenknecht
Hochschule Zittau/Görlitz
Informatik
2007-07-22
Die globale Fragestellung in der Berechenbarkeitstheorie (theory of computability) lautet: "Was können Computer leisten?" Etwas präziser: Welche Probleme können mit dem Computer, der sich uns über entsprechende Software präsentiert, gelöst werden?Ist die "Berechnungskraft" (computational power) begrenzt?
Was heißt überhaupt "Lösbarkeit" Sind die Algorithmen, die (heute) als mächtigstes Lösungswerkzeug gelten, allmächtig? Oder gibt es algorithmisch unlösbare Probleme? Sollte Letzteres der Fall sein, wäre es sehr interessant zu wissen, wie viele und welche Probleme unlösbar sind?
Ein Problem ist lösbar, wenn es einen Algorithmus gibt, der eine die Problemlösung beschreibende Funktion berechnet. Dabei geht es nicht nur um die Definition der Abbildung von Eingabedaten (Argumente) auf Ausgabedaten (Funktionswerte), sondern darüber hinaus um deren Erzeugung durch Berechnung.
Definition: Eine Funktion $f$ ist berechenbar, wenn es einen Algorithmus gibt, der für jedes $x\in D(f)$ den zugehörigen Wert $f(x)$ (effektiv) ermittelt.
Mit dieser Definition wird der Berechenbarkeitsbegriff auf den Algorithmusbegriff zurückgeführt. Unter einem Algorithmus versteht man gewöhnlich
Nur wenig Erfahrung reicht aus, um einen so definierten Begriff anzuzweifeln: Was bedeutet " eindeutig" Muss ein Algorithmus für einen bestimmten Satz von Eingaben immer das gleiche Resultat liefern? Warum gibt es dann nichtdeterminierte 1 Algorithmen, die dies gerade nicht tun?
Muss ein Algorithmus terminieren? Warum unterscheidet man dann abbrechende und nichtabbrechende Algorithmen?
Fazit: Der Algorithmusbegriff braucht eine Präzisierung. Er entzieht sich in obiger Form jeglichem Versuch, mit mathematischen Methoden Aussagen in Form von Sätzen hervorzubringen.
Da der Algorithmusbegriff vage ist, ist es auch der darauf beruhende Berechenbarkeitsbegriff. Das ist unsere Ausgangssituation für die Behandlung der Theorie der Berechenbarkeit.
Natürlich gibt es Probleme, die sich weitestgehend einer Lösung mit Computerprogrammen entziehen. Meist sind sie auch mit menschlicher Intelligenz nicht zufrieden stellend lösbar, weil entweder die Fragestellung unscharf oder die Regeln zur schrittweisen Ableitung einer Antwort unklar sind. Sehr viele Probleme sind extrem vielschichtig und hängen von sehr vielen, meist selbst abhängigen Parametern ab, sodass das gewünschte Ergebnis nur eine Aussage mit vielen "wenn" und "aber" sein kann.
Beispiele:
In der Tat tragen Ergebnisse aus der Künstlichen Intelligenz und moderne Methoden der Computersimulationen dazu bei, dass diese Klasse unzugänglicher Probleme immer kleiner wird. Eine Reihe von Prognosen, wie etwa die Wettervorhersage, das Verkehrsflussverhalten auf Autobahnen und Wahlhochrechnungen, beeindrucken (teilweise) durch hohe Trefferquoten. Computer dringen also in diese Bereiche vor und können heute sogar menschliches Denken und Gefühlslagen in Grenzen simulieren. Dennoch bleiben Tabus.
Nicht für alle prinzipiell lösbaren Probleme können zugehörige Lösungen auch wirklich ermittelt werden. Es gibt praktische Grenzen für die Computernutzung. Der Berechnungsaufwand für bestimmte Problemklassen kann jede Zeitschranke übersteigen. Dies gilt auch bei Hardware-unabhängiger Betrachtung: Der Zeitbedarf für die Lösung eines solchen Problems wird in Abhängigkeit von der sog. Problemgröße angegeben. Den entsprechenden mathematischen Ausdruck analysiert man für sehr große Werte der darin vorkommenden unabhängigen Variablen (Problemgröße).
Leider sind zahlreiche sehr interessante Probleme aus der Wirtschaft praktisch unlösbar. Beim klassischen Stundenplanungsproblem spielen die Anzahl der jeweiligen Fachlehrer, die der Fachunterrichtsräume, die Schüleranzahl, die Stundenverteilung und die Hohlstundenvermeidung als Parameter bzw. als Nebenbedingungen der Optimierung eine Rolle. Bei Logistikproblemen sind das beispielsweise die Anzahl der LKWs, deren Transportkapazität, die Reihenfolge, in der man die Belieferungsorte anfahren sollte, just-in-time-Zwänge, die Anzahl der zu einem Zeitpunkt verfügbaren LKW-Fahrer - um nur einige zu nennen. Alle diese Parameter haben Einfluss auf die Lösung.
Mit dem oben angedeuteten Ressourcenproblem (Zeit und Speicher) befasst sich die Komplexitätstheorie. Dort geht es um Probleme, deren Lösungsalgorithmen vollständig bekannt sind. Ab einer bestimmten Problemgröße ist jedoch kein Computer in der Lage, mit diesen Algorithmen die Lösung auch wirklich zu erzeugen.
Aufgabe:
Anfang 1996 hat es eine spektakuläre Schachpartie zwischen Herrn Kasparow und einem Hochleistungscomputer deepblue
(mit Parallelarchitektur) gegeben. Wie ging es aus? Wer hat gewonnen? Finden Sie es mit Hilfe einer kleinen Internet-Recherche heraus.
Nach Verbesserungen an Hard- und Software wird es vermutlich eine Neuauflage dieses Wettkampfes geben. Warum ist es eigentlich so schwierig, ein leistungsfähiges Schachprogramm zu entwerfen?
Da wir in der Berechenbarkeitstheorie die Frage nach der absoluten Unlösbarkeit stellen, sind diese praktisch unlösbaren Probleme kein Betrachtungsgegenstand. Praktisch unlösbare Probleme sind prinzipiell lösbar auch wenn es für deren Lösung keine effizienten Algorithmen gibt.
Die Definition des Mengenbegriffs ist einerseits eine sehr fundamentale und andererseits (leider) sehr schwierige Angelegenheit. "Fundamental" deshalb, weil sehr viele andere mathematische Begriffe auf dem Mengenbegriff basieren. Typische Einführungskurse in die Mathematik beginnen deshalb mit der Mengenlehre.
Georg Cantor (1845-1918) legte eine Definition vor, die die Mathematiker in die Lage versetzen sollte, die Arbeit mit endlichen Mengen auf unendliche Mengen auszudehnen. Die Fachwelt war gespaltener Auffassung, was die Bedeutung der Cantorschen Leistung angeht. Auch Cantor selbst war skeptisch bei der Bewertung bestimmter Aussagen, die sich auf der Basis dieser Definition gewinnen ließen.
Definition: Eine Menge ist eine Zusammenfassung bestimmter, wohlunterscheidbarer Objekte unserer Anschauung oder unseres Denkens zu einem einheitlichen Ganzen. Diese Objekte heißen Elemente einer Menge.
Es kommt also nicht auf die Reihenfolge an, die die Elemente einer Menge einnehmen. Niemals kann ein bestimmtes Objekt in einer bestimmten Menge mehrfach vorkommen.
Diese heute in allen Schul- und Fachbüchern verwendete Mengendefinition von Cantor hat allerdings einige Schwächen:
Beispiel: Bekanntlich gibt es Mengen, die selbst Mengen enthalten. Man denke beispielsweise an die Potenzmenge einer Menge als die Menge aller Teilmengen einer Menge. Das ist nichts Besonderes. Etwas seltsam muten Mengen an, die sich selbst als Element enthalten. Das ist bei der Potenzmenge nicht der Fall, wohl aber bei der Menge mathematischer
Begriffe: Dies ist selbst ein mathematischer Begriff.
Wir nennen solche seltsamen Mengen, die selbst unter ihren Elementen sind, außerordentliche im Gegensatz zu ordentlichen Mengen.
Nun bilden wir die Menge
$O$
, die alle ordentlichen Mengen enthält. Ebenso, wie von der "Menge aller natürlichen Zahlen", können wir von der "Menge aller ordentlichen Mengen" sprechen.
Die Frage, ob
$O$
selbst eine ordentliche oder außerordentliche Menge ist, kann nicht beantwortet werden:
Wenn die Menge
$O$
überhaupt existiert, dann enthält sie sich selbst als Element. Schließlich haben wir ja alle ordentlichen Mengen in
$O$
zusammengefasst. Nach Definition ist eine Menge, die sich selbst als Element enthält, eine
außerordentliche Menge. Also ist
$O$
zugleich eine ordentliche und eine außerordentliche, was einen offensichtlichen Widerspruch darstellt.
Wir müssen folglich annehmen, dass
$O$
eine außerordentliche Menge ist. Dann enthält sie sich selbst als Element. Dies ist aber verboten, denn in
$O$
wurden nur ordentliche Mengen aufgenommen. Also ist auch die Annahme,
$O$
sei eine
außerordentliche Menge, falsch.
In beiden möglichen Fällen gibt es einen Widerspruch. Fazit: Eine solche Menge
$O$
gibt es nicht!
Das im Beispiel beschriebene Problem ist als Russellsche Antinomie bekannt geworden (Bertrand Russell: 1872-1970). In Kurzform lautet es: Gilt $B\in B$ oder $B\notin B$ , wobei $B:=\{x\mid x\notin x\}$ ? Zur Vermeidung dieser Widersprüche ersannen Henri Poincaré (1854-1912) einen Stufenkalkül und Ernst Friedrich Ferdinand Zermelo 1871-1953), selbst Schüler von Cantor, ein Axiomsystem (1908). Inzwischen liegen weitere Arbeiten dazu vor.
Aufgabe:
1919 hat Russell sein Paradoxon in populärer Form als Dorfbarbier-Problem formuliert. Es basiert auf der folgenden Definition:
Der Dorfbarbier ist derjenige Mann im Dorf, der alle männlichen Dorfbewohner rasiert, die sich nicht selbst rasieren.
Diskutieren Sie die Frage, ob sich der Dorfbarbier selbst rasiert. Setzen Sie die Fragestellung in eine Sprechweise mit Mengen um.
Die möglichen Antinomien, die sich aus der Cantorschen Mengendefinition ergeben können, sind für die folgenden Betrachtungen ungefährlich. Wir dürfen also die Cantordefinition verwenden und werden das auch tun. Falls ausgewählte indirekte Beweise in den folgenden Kapiteln auf den ersten Blick eine gewisse Ähnlichkeit mit Antinomien aufweisen, so handelt es sich doch um etwas ganz anderes, nämlich um indirekte Beweise, die naturgemäß mit einem Widerspruch enden. Diese beiden Sachverhalte sind also strikt zu unterscheiden!
Die Menge aller Begriffe eines Wissensgebietes und auch die Menge aller männlichen Dorfbewohner sind endlich. Die Menge aller Punkte einer Geraden, einer Strecke und eines Rechtecks dagegen nicht. Viele, der bei endlichen Mengen geläufigen Eigenschaften, können nicht auf unendliche Mengen übertragen werden.
Der Unendlichkeitsbegriff spielt in der Mathematik eine sehr große Rolle. Anfangs sollte er erst gar nicht in den Begriffskatalog aufgenommen werden, weil er nicht so recht in das bestehende Gebäude passte. Selbst Cantor war völlig überrascht, als es ihm gelang, eine eineindeutige Abbildung der Menge der Punkte eines Quadrates auf die Menge der Punkte einer Strecke anzugeben. Immerhin hatte er sich in den Jahren 1871-1874 gerade mit dem Beweis der Unmöglichkeit einer solchen Abbildung befasst. Dem Mathematiker Richard Dedekind (1831-1916) schrieb er: Ich sehe es und kann es doch nicht glauben! Das Ergebnis lautet: Ein Quadrat hat ebenso viele Punkte wie eine Strecke.
Ein Maß für die Größe endlicher Mengen kann man sehr leicht finden: Die Kardinalität einer Menge wird durch die Anzahl der Elemente einer Menge bestimmt. Eine rekursive Definition lautet:
$ card(M) = \left\{ \begin{array}{c l l} 0 & \mbox{, wenn} & M=\emptyset \\ 1+card(\{a_2,a_3,\ldots,a_n\}) & \mbox{, wenn} & M=\{a_1,a_2,a_3,\ldots,a_n\} \end{array} \right. $
Diese Definition lässt sich direkt mit Scheme formulieren:
Die betrachtete Menge wird dabei als Liste repräsentiert.
Man sagt: Die Kardinalität von $\{a,b,c,d,e,f,g\}$ beträgt $7$ , oder: Die Kardinalzahl von $\{a,b,c,d,e,f,g\}$ ist $7$ . So wie eine Kardinalzahl eine Anzahl beschreibt, betrifft eine Ordinalzahl die Ordnung.
Obwohl auch unendliche Mengen eine Kardinalität besitzen, ist deren Definition nach obigem Vorbild, d.h. durch die Elementanzahl, praktisch unbrauchbar: Der Elementarfall der Rekursion, nämlich die leere Menge, würde niemals erreicht werden. Die Elemente einer unendlichen Menge kann man nicht zählen, denn der Zählprozess fände kein Ende.
Aber man kann (unendliche) Mengen miteinander vergleichen. Dazu braucht man eine Bezugsmenge, deren Mächtigkeit man kennt. Schließlich definiert man eine Abbildung zwischen der zu beurteilenden Menge und eben dieser Bezugsmenge. Gelingt es dabei, jedem Element der einen Menge genau ein Element der anderen zuzuordnen und umgekehrt, so sind die beiden Mengen gleichmächtig.
Als Bezugsmenge dient die Menge der natürlichen Zahlen $\mathbb{N}_0$ . Man nennt eine unendliche Menge, die die gleiche Mächtigkeit wie $\mathbb{N}_0$ besitzt, abzählbar unendlich, die anderen überabzählbar unendlich.
Diese Überlegungen führen schließlich zu folgender Definition.
Definition:
Eine Menge
$M$
ist abzählbar unendlich (countably infinite), wenn es eine bijektive Abbildung
$\mathbb{N}_0\mapsto M$
gibt, und abzählbar (countable), wenn sie entweder endlich oder abzählbar unendlich ist.
Eine Menge ist überabzählbar unendlich (uncountably infinite) oder einfach überabzählbar (uncountable), wenn sie nicht abzählbar ist.}
Aufgabe:
Wiederholen Sie die Grundbegriffe für Funktionen, insbesondere Eigenschaften von Abbildungen, wie injektiv, surjektiv und bijektiv.
Die Gleichmächtigkeit von Mengen ist eine Äquivalenzrelation. Als Kardinalzahl für die Klasse der zu $\mathbb{N}_0$ gleichmächtigen Mengen führte Cantor die transfinite Zahl $\aleph_0$ (Aleph-Null) ein. $\aleph$ ist der erste Buchstabe des hebräischen Alphabets.
Zum Nachweis der Abzählbarkeit bzw. Überabzählbarkeit gibt es je ein Verfahren, das als Cantorsches Diagonalverfahren oder Cantorsches Diagonalisierungsverfahren 1. bzw. 2. Art 2 bekannt geworden sind.
Das Verfahren 1. Art ist konstruktiv: Man versucht, ein Ordnungsprinzip für abzählbar unendliche Mengen anzugeben. Dies läuft auf eine Durchnummerierung der Elemente hinaus, die schließlich eine bijektive Abbildung auf die Menge der natürlichen Zahlen beschreibt.
Satz:
Die Menge der ganzen Zahlen
$\mathbb{Z}$
ist abzählbar unendlich.
Beweis:
Man ordnet die Zahlen wie folgt:
$\mathbb{Z}=\{0, 1, -1, 2, -2, 3, -3, \ldots\}$
.
Aufgabe:
Zeigen Sie, dass auch die Menge der rationalen Zahlen abzählbar unendlich ist.
Aufgabe:
Zeigen Sie, dass auch die Wortmenge
$A^*$
über einem beliebigen Alphabet
$A$
eine abzählbar unendliche Menge ist.
Aufgabe:
Zeigen Sie, dass sowohl die geraden Zahlen, die Primzahlen als auch die positiven rationalen Zahlen abzählbar unendliche Mengen sind. Es gibt also nicht mehr natürliche Zahlen als Primzahlen. Dies ist mit unserer Anschauung natürlich unvereinbar.
Beispiel:
Die Menge der reellen Zahlen ist eine überabzählbar unendlichen Menge. Es ist unmöglich, jeder reellen Zahl eine natürliche zuzuordnen. Auf den Beweis, dass es "viel mehr" reelle als natürliche Zahlen gibt, kommen wir noch zu sprechen.
Einem studentischen Vorschlag folgend, versuchen wir zunächst durch Angabe einer Durchnummerierung zu zeigen, dass die reellen Zahlen aus dem Intervall $[0,1]$ eine abzählbar unendliche Menge $M_{[0,1]}$ bilden, was in Wirklichkeit jedoch falsch ist!
Nach Satz \ref{satz:vereinigung-abzaehlbarer-mengen}, wonach die Vereinigungsmenge abzählbarer Mengen selbst wiederum abzählbar ist, gilt: Wenn $M_1=\{0.1, 0.2, 0.3, 0.4,\ldots, 0.9,0.11,0.12,0.13\ldots\}$ , $M_2=\{0.01, 0.02, 0.03, 0.04,\ldots\}$ , $M_3=\{0.001, 0.002, 0.003, 0.004, \ldots\}$ , $\ldots$ Mengen sind, so ist auch $M_{[0,1]}=M_1\cup M_2\cup M_3\cup\ldots$ eine abzählbar unendliche Menge.
Der Student hatte die Vorstellung, dass alle, also auch unendliche nichtperiodische, Dezimalzahlen, wie etwa $\pi-3$ oder $\sqrt 2-1$ , in einer der genannten Mengen $M_i$ vorkommen. Man braucht ja die Reihe nur weit genug fortzusetzen, dann findet man alle Zahlen mit endlicher Ziffernfolge, beispielsweise $0.182735452718293$ , in der Tat in $M_1$ . Jede Zahl mit noch so langer endlicher Ziffernfolge nach $0.$ wird irgendwann in einer der Mengen $M_i$ aufgefunden werden, wenn man die Elemente in der angegebenen Ordnung aufschreibt. Eine natürliche Zahl, wie beispielsweise $182735452718293$ , wird auf $0.182735452718293$ abgebildet.
Für irrationale Zahlen, die nach dem Komma eine unendliche Ziffernfolge aufweisen, gelingt es jedoch nicht, auf diese Weise eine Platznummer zu finden. Wenn die Entwicklung der betreffenden Menge beliebig fortgesetzt wird, kommen zwar immer bessere Näherungen für diese Zahl in der Liste vor, niemals aber die Zahl selbst. Der hier diskutierte studentische Vorschlag muss also verworfen werden.
Aufgabe
:
Zeigen Sie, dass die Wortmenge
$A^*=\bigcup_{i=0}^{\infty}A^i$
für ein beliebiges Alphabet
$A$
eine abzählbar unendliche Menge ist.
Satz
:
Wenn
$M_1, M_2, M_3,\ldots$
abzählbare Mengen sind, dann ist auch die Menge
$\bigcup_{n=1}^{\infty}M_n$
abzählbar.
Beweis:
als Übungsaufgabe
Hier interessieren wir uns besonders für das Verfahren der 2. Art, dessen Erfindung in der Mathematik sehr geschätzt wird. In der Berechenbarkeitstheorie hat es fundamentale Bedeutung. Man spricht vom Cantorschen Diagonalisierungsverfahren schlechthin.
Eine noch so große Zahl erfolgloser Versuche, für eine gegebene Menge $M$ eine Bijektion $\mathbb{N}_0\to M$ zu finden, berechtigt nicht zur Aussage, $M$ sei überabzählbar. Man benötigt eine Beweistechnik, deren Einsatz zeigt, dass eine solche Nummerierung für die Elemente aus $M$ nicht existieren kann.
Das Diagonalisierungsverfahren 2. Art arbeitet indirekt: Es wird also gezeigt, dass eine Menge deshalb überabzählbar ist, weil die Annahme, sie sei abzählbar, falsch ist. Das Verfahren liefert keinen Beitrag zur Konstruktion einer überabzählbaren Menge.
Die Beweisidee beginnt mit der (gedanklichen) Auflistung aller Elemente der Menge $M$ , von der wir annehmen, sie sei abzählbar unendlich. Eine solche Auflistung ist für abzählbar unendliche Mengen - wie wir oben gesehen haben - garantiert möglich.
Gelingt es anschließend für nur ein einziges Element aus $M$ zu zeigen, dass es in dieser Liste aller Mengenelemente nicht vorkommt, ergibt sich ein Widerspruch, so dass die Annahme, $M$ sei abzählbar unendlich, falsch ist.
Wie könnte ein solches Element aussehen?
Es wird so konstruiert, dass es sich von jedem in der Auflistung vorkommenden Element - wenn auch geringfügig - unterscheidet. Die Konstruktion eines nicht in der Auflistung vorkommenden Elements läuft auf die Verfremdung der Diagonalelemente hinaus, wonach das Verfahren seinen Namen erhielt.
Aufgabe:
Beweisen Sie die Überabzählbarkeit der Menge der reellen Zahlen, d.h. es gibt viel mehr reelle Zahlen als natürliche.
Hinweis: Bei der Lösung der Übungsaufgabe beschränkt man sich gewöhnlich auf die Teilmenge der reellen Zahlen im Intervall
$[0,1]$
, also
$M_{[0,1]}$
. Dies sind die Zahlen der Gestalt
$0.a_1a_2a_3\ldots$
, wobei
$a_i$
beliebige Ziffern sind, die ab einer bestimmten Stelle
$i=k$
auch ausbleiben dürfen. Wir weisen darauf hin, dass damit tatsächlich alle Elemente aus
$M_{[0,1]}$
beschrieben werden. Auch die Zahl
$1=0.\bar{9}\ldots$
kommt darin vor, was
sich aus der Anwendung der Formel für unendliche geometrische Reihen ergibt oder einfach wegen
$0.\bar{9}\ldots=9\cdot 0.\bar{1}\ldots=9\cdot\frac{1}{9}=1$
plausibel ist.
Für Wortmengen haben wir in einer Übungsaufgabe weiter oben eine längenlexikografische Ordnungsrelation für Wörter definiert, mit deren Hilfe man die Elemente aufsteigend auflisten kann. Auch die Menge der ganzen und der rationalen Zahlen lassen sich ordnen.
Die Frage, ob man abzählbare Mengen auf verschiedene Arten ordnen kann, ist positiv zu beantworten. Dies wollen wir hier aber nicht weiter vertiefen, da wir zum Nachweis der Abzählbarkeit lediglich an der Existenz einer solchen Ordnung interessiert sind: Durchnummerieren heißt ja, eine bestimmte Reihenfolge zu fixieren.
Bleibt die Frage: Können beliebige unendliche Mengen geordnet werden?
Cantor vermutete schon 1883, dass dies gelingt. Im Jahre 1904 veröffentlichte der Mathematiker Zermelo einen Beweis dafür, dass dies möglich ist. Dieser Beweis stützt sich auf eine Annahme, die heute das Zermelo-Axiom oder Auswahlaxiom genannt wird:
Gegeben sei eine unendliche Menge, deren Elemente selbst unendliche Mengen sind. Dann kann man aus jeder Menge jeweils ein Element auswählen, ohne im voraus eine Auswahlregel geben zu müssen.
Der Grundgedanke des Beweises besteht im Nachweis, dass es keine Menge gibt, die sich nicht ordnen läßt. Einen Hinweis auf die Konstruktion einer solchen Ordnung enthält dieser reine Existenzbeweis jedoch nicht.
Die Mehrheit der Mathematiker versteht die Annahme von Zermelo als Axiom, das man mit den Axiomen der Mengenlehre weder herleiten kann, noch steht es im Widerspruch zu ihnen.
Wie viele Probleme (für Computer) gibt es?
Probleme werden durch einstellige Wortfunktionen in $A^*$ beschrieben. Die Menge, die alle diese Wortfunktionen enthält, ist $F$ mit
$F := \{f\mid f:A^*\rightarrow A^*\}$ .
Man kann zeigen, dass trotz der hier getroffenen Beschränkung auf einstellige Wortfunktionen die Menge aller Probleme voll erfasst wird. Wir nehmen nun an, dass $F$ eine abzählbar unendliche Menge ist. Dann können wir eine Liste aller Funktionen aus $F$ angeben, s. in folgender Tabelle in Spalte 1.
$A^*=\{w_0,w_1,w_2,w_3,\ldots\}$
$F$ | | | $w_0$ | $w_1$ | $w_2$ | $w_3$ | $\ldots$ |
---|---|---|---|---|---|---|
$f_0$ | $f_0(w_0)$ | $f_0(w_1)$ | $f_0(w_2)$ | $f_0(w_3)$ | $\ldots$ | |
$f_1$ | $f_1(w_0)$ | $f_1(w_1)$ | $f_1(w_2)$ | $f_1(w_3)$ | $\ldots$ | |
$f_2$ | $f_2(w_0)$ | $f_2(w_1)$ | $f_2(w_2)$ | $f_2(w_3)$ | $\ldots$ | |
$f_3$ | $f_3(w_0)$ | $f_3(w_1)$ | $f_3(w_2)$ | $f_3(w_3)$ | $\ldots$ | |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ldots$ |
Wir konstruieren eine Funktion $\bar{f}:A^*\mapsto A^*$ , die in $F$ enthalten ist, mit
$\bar{f}(w_i)=f_i(w_i)\circ x,$
wobei $x$ ein beliebiges (aber fest gewähltes) Alphabetzeichen ist, d.h. $x\in A$ .
Da $\bar{f}$ jedoch mit keiner der Funktionen $f_0, f_1, f_2, f_3, \ldots$ aus $F$ übereinstimmt, d.h. $\bar{f}\notin F$ , entsteht ein Widerspruch, denn $\bar{f}\in F$ gilt aufgrund obiger Konstruktion von $\bar{f}$ . Folglich muss die Annahme falsch sein, d.h. es existieren überabzählbar viele Wortfunktionen (Probleme).
Es gibt eine weitere Möglichkeit, um sich klar zu machen, dass $F$ eine überabzählbar unendliche Menge ist. Da die Potenzmenge $\mathcal{P}(A^*)$ für beliebiges Alphabet $A$ eine überabzählbar unendliche Menge ist, s. Übungsaufgabe, ist auch die Menge $E$ aller Funktionen $e$ , mit $e:A^*\mapsto \{0,1\}$ , überabzählbar unendlich. Da sich $1/0$ als $wahr/falsch$ oder $ja/nein$ deuten lässt, handelt es sich gerade um die Menge aller Prädikate. Nicht berechenbare Prädikate entsprechen also Entscheidungsproblemen, die weder mit $ja$ noch mit $nein$ beantwortet werden können. Man nennt sie unentscheidbare Prädikate.
Aus der entsprechenden Übungsaufgabe wissen wir, dass die Wortmenge über einem Alphabet eine abzählbar unendliche Menge ist. Nicht jedes dieser Wörter repräsentiert ein syntaktisch korrektes Programm. Folglich gibt es höchstens abzählbar unendlich viele Programme. Jedes Programm lässt sich auf einen (durch dieses Programm implementierten) Algorithmus abbilden. Dabei kann je ein Algorithmus durch mehrere Programme implementiert werden. Dies bedeutet wiederum, dass es höchstens abzählbar unendlich viele Algorithmen gibt.
Den überabzählbar unendlich vielen Problemen stehen also nur höchstens abzählbar unendlich viele Algorithmen gegenüber. Damit ist klar, dass es überabzählbar unendlich viele unlösbare Probleme geben muss.
Dies verführt sogar zu der spaßig-flappsigen Bemerkung, wonach es eher ein Zufall ist, wenn man auf ein (prinzipiell) lösbares Problem trifft. In dieser Form kann man mit Mengen verschiedenen Unendlichkeitstyps natürlich nicht argumentieren.
Es gibt Probleme, für die wir bis heute keine Lösung kennen, da die Mittel der Wissenschaften dafür noch nicht ausreichen. Beispielsweise im Bereich der Zahlentheorie gibt es eine Reihe derartiger Fragestellungen, auf die man bisher keine Antwort geben kann.
Beispiel:
Die Collatz-Folge ist gegeben durch
$ \begin{eqnarray} a_0 &= & a \\ a_n & = & \left\{ \begin{array}{c l l} 1 & \mbox{, wenn } & a_{n-1}=1\\ \frac{a_{n-1}}{2} & \mbox{, wenn } & a_{n-1} \mbox{ gerade}\\ 3\cdot a_{n-1} + 1 & \mbox{, sonst} \end{array} \right. \end{eqnarray} $
Die Collatz-Folge kann für beliebige natürliche Startwerte $a$ mit $a>1$ berechnet werden.
Ob sie für jede natürliche Startzahl mit $1$ endet, ist bisher unbekannt. Man vermutet es, da bisher noch keine Ausnahme bekannt ist, aber es ist noch nicht bewiesen.
Dennoch ist die folgende Funktion $g$ , mit $g:\mathbb{N}_0\mapsto \{0,1\}$ berechenbar 3 .
$y=g(x)= \left\{ \begin{array}{l l} 1 & \mbox{, wenn die Collatz-Folge für alle nat. Startwerte mit 1 endet.}\\ 0 & \mbox{, sonst} \end{array} \right.$
Es gibt einen Algorithmus für $g$ und nur dessen Existenz ist gefragt. Man sagt auch, dass $g$ effektiv berechenbar ist, denn es kann vollständig und präzise beschrieben werden, wie die Lösung (0 oder 1 für ein beliebiges Argument) zu ermitteln ist.
generated by IMS System v1.0