4. Berechenbarkeit und natürliche Zahlen

Mit den Booleschen Schaltkreisen haben wir ein Modell kennengelernt, dass die Berechnung von Booleschen Funkionen $f:\{0,1{\}}^n\to \{0,1\}$ beschreibt. Wir haben mehrere Beweisen gesehen, dass es für jede Boolesche Funktion einen Schaltkreis gibt. Unsere Zielsetzung war durchweg komplexitätstheoretisch: wir wollten möglichst kleine Schaltkreise von möglichst geringer Tiefe entwerfen. Würden wir tiefer in die Schaltkreiskomplexität einsteigen, so würden wir uns fast ausschließlich mit negativen Zielen beschäftigen: zu zeigen, dass es zu bestimmten Funktionen eben nicht Schaltkreise mit $S$ Gates und in Tiefe $d$ gibt; wir würden uns zum Großteil mit unteren Schranken beschäftigen.

Boolesche Funktionen sind immer endliche Objekte. In der Berechenbarkeitstheorie geht es im Grunde um die Frage: welche unendlichen Funktionen können wir überhaupt berechnen? Und was gilt denn überhaupt als zulässiges Modell für Berechenbarkeit?

Wenn wir nun also über Funktionen $f:X\to Y$ auf unendlichen Mengen sprechen und uns fragen, welche durch eine endliche Rechenvorschrift beschrieben werden können, dann müssen wir erst einmal entscheiden, mit welcher unendlichen Menge wir uns beschäftigen. Eine Bedingung sollte zum Beispiel sein, dass wir Input und Output vollständig hinschreiben können. (Denn wenn der Input bereits unendlich groß wäre, wie sollten wir überhaupt über Berechenbarkeit sprechen?) Für uns als Informatiker wäre doch folgende Menge am naheliegendsten: $$\begin{array}{r}\{0,1{\}}^{\ast },\end{array}$$ also die Menge aller beliebig langen aber endlichen Bit-Strings. Wir können alle möglichen Dinge (Wörter, Programme, Dateien, natürliche Zahlen, rationale Zahlen) als solche Bit-Strings codieren. Die ersten Wissenschaftler, die sich mit Berechenbarkeit beschäftigten, kamen allerdings aus der Mathematik und Logik, und ganz allgemeinen entstand die Berechenbarkeitstheorie bevor die ersten Rechner gebaut wurden. Daher beschäftigten sich die ersten Forscher auch mit einer anderen, uns sehr vertrauten Menge: $$\begin{array}{r}\mathbb{N},\end{array}$$ den natürlichen Zahlen. Im letzten Kapitel haben wir ja unter anderen bewiesen, dass diese gleichmächtig sind: $\{0,1{\}}^{\ast }\cong \mathbb{N}$ und haben auch eine Bijektion kennengelernt, beispielsweise $$\begin{array}{rl}f:\{0,1{\}}^{\ast }& \to \mathbb{N}\\ (x_1,\dots ,x_n)& \mapsto (1x_1\dots x_n{)}_2-1,\end{array}$$ wir stellen also dem Bitstring $x_1,\dots ,x_n$ eine 1 voran und interpretieren das Ergebnis als natürliche Zahl; dann ziehen wir 1 ab. Es ist also für die Entwicklung eines Berechenbarkeitsbegriffs mehr oder weniger egal, ob wir mit $\mathbb{N}$ oder $\{0,1{\}}^{\ast }$ arbeiten - sofern die obige Bijektion $f$ selbst "berechenbar" ist.

Wir werden in diesem Kapitel mehrere Berechenbarkeitsmodelle für Funktionen $f:\mathbb{N}\to \mathbb{N}$ kennenlernen. Die beste Einstellung Ihrerseits ist, diese Modelle als primitive, sehr reduzierte Programmiersprachen zu betrachten.