3. Unendliche Mengen

Mit den Boolesche Schaltkreise haben wir bereits ein Modell für Berechnung kennengelernt. Es ist abstrakt genug, um mathematisch rigorose Aussagen darüber zu treffen und über obere und untere Schranken zu sprechen. Gleichzeitig ist es sehr konkret und nah an seiner physikalischen Realisierung. Ein entscheidender Nachteil Boolescher Schaltkreise jedoch: Sie müssen von Anfang an wissen, wie groß Ihr Input ist; also wie vielen Input-Variablen $x_{1}, \dots, x_{n}$ Sie begegnen werden. Für ein allgemeines Modell der Berechnung ist dies ungeeignet. Wir wollen ja ein Computerprogramm, das beliebig große Eingaben verkraften kann. Ein Computerprogramm soll also endlich sein, aber für eine unendliche Menge potentieller Eingaben funktionieren. In diesem Kapitel werden wir daher unendliche Mengen besser kennenlernen.

Beispiel 3.1 Die Mengen $N, Z, Q, R$ sind unendlich. Die Mengen ${a, e, i, o, u}$ und ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ sind endlich.

3.2 Die Menge $\begin{array}{r} {0, 1}^{*} := {ϵ} \cup {0, 1} \cup {00, 01, 10, 11} \cup \dots \cup {0, 1}^{n} \cup \dots, \end{array}$ also die Menge aller endlichen Bit-Strings ist unendlich. Mit $ϵ$ bezeichnen wir hier den leeren String. Ganz generell: wenn $Σ$ eine nichtleere Menge ist, dann ist $Σ^{*}$ , die Menge aller endlichen Strings über $Σ$ , unendlich.