Prof.Dr.Christian Wagenknecht
Hochschule Zittau/Görlitz
Informatik
2007-07-22


Berechenbarkeitstheorie

Inhaltsverzeichnis:

  1. Intuitiver Berechenbarkeitsbegriff



1 Intuitiver Berechenbarkeitsbegriff

1.1 Motivation und Fragestellungen

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?

1.2 Intuitiver Algorithmusbegriff

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.

1.3 Prinzipiell unlösbar

1.3.1 Unzugängliches (wenigstens) für Computer

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.

1.3.2 Praktisch Unmögliches

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.

1.4 Unendliche Mengen

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:

  1. Sie verwendet nämlich vage Begriffe, die sich einem strengen mathematischen Umgang entziehen. Was sind wohlunterscheidbare Objekte? Wie groß ist der kleinste Unterschied? Was ist ein einheitliches Ganzes?
  2. Bestimmte Mengenbildungen können zu logischen Widersprüchen, sog. Antinomien, führen, wie das folgende Beispiel zeigt.

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!

1.5 Mächtigkeit unendlicher Mengen

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: