Die Ausgangsfrage der theoretischen Informatik: Wann ist eine Fragestellung überhaupt so präzise gefasst, dass ein mechanischer Rechner sie lösen kann — und was heißt hier lösen? Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben.
TL;DR
- Ein Computer-Problem wird in der theoretischen Informatik als formale Sprache $L \subseteq \Sigma^*$ über einem endlichen Alphabet dargestellt.
- Wir unterscheiden Instanz (konkreter Eingabestring $w$) und Frage (gilt $w \in L$?).
- Ein Problem gilt als entscheidbar, wenn ein Algorithmus für jede Instanz nach endlich vielen Schritten mit ja oder nein hält.
- Berechenbarkeit fragt, ob es überhaupt einen Algorithmus gibt; Komplexität fragt, wie teuer er ist.
- Automaten und Turingmaschinen sind unsere formalen Modelle, um genau diese Fragen mathematisch beantworten zu können.
- Neu auf dieser Seite: Die Sektion Rechenaufgaben trainiert den Klausur-Modus mit vollständig durchgerechneten Lösungen.
Definitionen und Formalismen
Alphabet und Sprache
Ein Alphabet $\Sigma$ ist eine endliche, nichtleere Menge von Symbolen. $\Sigma^*$ bezeichnet die Menge aller endlichen Wörter über $\Sigma$, einschließlich des leeren Wortes $\varepsilon$. Eine Sprache ist eine Teilmenge $L \subseteq \Sigma^*$.
$$\Sigma^* \;=\; \bigcup_{n \geq 0} \Sigma^n, \qquad \Sigma^0 = \{\varepsilon\}$$Entscheidungsproblem
Ein Entscheidungsproblem über $\Sigma$ ist ein Paar aus einer Sprache $L \subseteq \Sigma^*$ und der Frage: Gilt für ein gegebenes Wort $w \in \Sigma^*$, dass $w \in L$? Die Antwort ist stets ja oder nein.
$$\text{Entscheidungsproblem} \;=\; (\Sigma,\, L) \text{ mit } L \subseteq \Sigma^*.$$Instanz vs. Frage
Die Instanz ist der konkrete Eingabewert (ein Wort $w$, ein Graph $G$, eine Zahl $n$), codiert als Wort in $\Sigma^*$. Die Frage ist die feste Eigenschaft, die geprüft wird — sie definiert die Sprache $L$. Ein Problem ist also nicht ein einzelner Fall, sondern eine Familie gleichartiger Fälle.
Entscheidbarkeit
Eine Sprache $L$ heißt entscheidbar, wenn eine Turingmaschine $M$ existiert, sodass für jedes $w \in \Sigma^*$ gilt: $M$ hält auf $w$ und akzeptiert genau dann, wenn $w \in L$. Andernfalls heißt $L$ unentscheidbar.
$$\forall w \in \Sigma^*:\quad M(w) \text{ hält} \;\land\; \bigl(M \text{ akzeptiert } w \iff w \in L\bigr).$$Berechenbarkeit vs. Komplexität
Berechenbarkeit fragt: existiert überhaupt ein Algorithmus, der $L$ löst? Komplexität fragt: wie viel Zeit oder Speicher benötigt der beste Algorithmus? Berechenbarkeit ist die logisch vorgelagerte Frage — ohne sie ist Komplexität sinnlos.
Kernkonzepte und Vorgehen
Um eine Fragestellung in die formale Welt der theoretischen Informatik zu übertragen, arbeitet man immer in derselben Reihenfolge. Jeder Schritt beantwortet eine konkrete Teilfrage, und in der Klausur werden genau diese Schritte einzeln geprüft.
- Fragestellung isolieren. Was genau soll entschieden werden? Formuliere eine Ja-Nein-Frage, keine Berechnungsvorschrift.
- Alphabet festlegen. Welche Symbole braucht die Codierung? Für Zahlen etwa $\Sigma = \{0,1\}$, für Graphen ein Alphabet mit Trennzeichen.
- Codierung der Instanz. Übersetze das reale Objekt in ein Wort $w \in \Sigma^*$. Die Codierung darf nicht mehrdeutig sein.
- Sprache definieren. $L = \{\, w \in \Sigma^* \mid w \text{ codiert eine Instanz mit Eigenschaft } P \,\}$. Diese Menge ist das eigentliche Problem.
- Modell wählen. Reicht ein endlicher Automat, ein Kellerautomat oder braucht es eine Turingmaschine? Der Sprachtyp bestimmt das Modell.
- Entscheidbarkeit prüfen. Gibt es einen Algorithmus, der bei jeder Eingabe terminiert? Wenn nicht, ist das Problem unentscheidbar.
- Erst dann Komplexität. Wenn entscheidbar: wie teuer ist die beste Lösung in Zeit und Platz?
Beispiel durchgerechnet
Vom Alltagssatz zur formalen Sprache
Ausgangsfrage: Ist eine gegebene natürliche Zahl gerade?
Schritt 1 · Ja-Nein-Frage. Die Frage lautet: Ist die Eingabezahl gerade? Antwort: ja oder nein. Passt zum Entscheidungsproblem.
Schritt 2 · Alphabet. Wir codieren Zahlen binär. $\Sigma = \{0, 1\}$.
Schritt 3 · Codierung. Die Zahl $6$ wird zu dem Wort $110$, die Zahl $13$ zu dem Wort $1101$. Jede natürliche Zahl hat genau eine kürzeste Binärdarstellung ohne führende Nullen.
Schritt 4 · Sprache.
$$L_{\text{gerade}} \;=\; \{\, w \in \{0,1\}^* \mid w \text{ ist Binärcodierung einer geraden Zahl} \,\} \;=\; \{\, w \in \{0,1\}^* \mid w \text{ endet auf } 0 \text{ oder } w = \varepsilon \,\}.$$Die letzte Stelle einer Binärzahl entscheidet über Parität.
Schritt 5 · Modell. Ein deterministischer endlicher Automat mit zwei Zuständen reicht: einer für endet-auf-0, einer für endet-auf-1.
1 1
┌────┐ ┌────┐
▼ │ ▼ │
┌──────┐│ 0 ┌──────┐│
──▶│ q0 * │─────▶│ q1 │
└──────┘◀─────└──────┘
0
q0 = akzeptierend (endet auf 0 → gerade)
q1 = nicht akzept. (endet auf 1 → ungerade)
Schritt 6 · Entscheidbarkeit. Der Automat hält bei jeder Eingabe nach genau $|w|$ Schritten. Das Problem ist entscheidbar.
Schritt 7 · Komplexität. Laufzeit linear in der Eingabelänge, Platz konstant. Ein reguläres Problem, extrem einfach.
Fazit. Die alltägliche Frage nach Parität wurde in vier Bausteine zerlegt: Alphabet, Codierung, Sprache, Modell. Genau diese Zerlegung erwartet die Klausur bei jedem Problem, egal wie einfach oder unentscheidbar.
Rechenaufgaben mit Lösung
Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen und Schritt für Schritt vergleichen.
Gegeben sei $\Sigma = \{a, b\}$ und die Sprache $$L \;=\; \{\, w \in \Sigma^* \mid |w|_a = |w|_b \,\},$$ wobei $|w|_x$ die Anzahl der Vorkommen des Symbols $x$ in $w$ bezeichnet. Entscheide für die folgenden Wörter, ob sie in $L$ liegen: $w_1 = \varepsilon$, $w_2 = ab$, $w_3 = aabb$, $w_4 = abba$, $w_5 = aab$, $w_6 = bbabaa$.
Lösung anzeigen
| Wort $w$ | $|w|_a$ | $|w|_b$ | $w \in L$? |
|---|---|---|---|
| $w_1 = \varepsilon$ | $0$ | $0$ | ja ($0 = 0$) |
| $w_2 = ab$ | $1$ | $1$ | ja |
| $w_3 = aabb$ | $2$ | $2$ | ja |
| $w_4 = abba$ | $2$ | $2$ | ja |
| $w_5 = aab$ | $2$ | $1$ | nein ($2 \neq 1$) |
| $w_6 = bbabaa$ | $3$ | $3$ | ja |
Sei $\Sigma$ ein Alphabet mit $|\Sigma| = k$. Zeige, dass die Anzahl der Wörter über $\Sigma$ mit Länge höchstens $n$ gleich $$\bigl|\{\, w \in \Sigma^* \mid |w| \leq n \,\}\bigr| \;=\; \frac{k^{n+1} - 1}{k - 1} \quad \text{für } k \geq 2$$ ist. Berechne den konkreten Wert für $\Sigma = \{0, 1\}$ und $n = 5$ sowie für $\Sigma = \{a, b, c\}$ und $n = 4$.
Lösung anzeigen
Formalisiere die folgenden Alltagsprobleme als Sprache. Gib jeweils Alphabet $\Sigma$, Codierung und die Sprache $L$ formal als Mengenausdruck an.
- Ist eine gegebene Dezimalzahl durch $3$ teilbar?
- Ist eine gegebene Zeichenkette ein Palindrom?
- Enthält ein gegebener Text mehr Vokale als Konsonanten? (Betrachte nur Buchstaben, keine Zeichensetzung.)
Lösung anzeigen
Klassifiziere die folgenden Sprachen jeweils als entscheidbar, semi-entscheidbar (aber nicht entscheidbar) oder unentscheidbar. Begründe kurz.
- $L_A = \{\, w \in \{0,1\}^* \mid w \text{ ist ein Palindrom} \,\}$.
- $L_B = \{\, w \in \{a,b\}^* \mid w = a^n b^n \text{ für ein } n \geq 0 \,\}$.
- $L_C = \{\, \langle M \rangle \mid M \text{ ist eine Turingmaschine, die auf leerer Eingabe hält} \,\}$ (Halten-auf-leerer-Eingabe).
- $L_D = \{\, \langle M \rangle \mid M \text{ ist eine Turingmaschine mit genau } 5 \text{ Zuständen} \,\}$.
Lösung anzeigen
| Sprache | Klassifikation | Kurzbegründung |
|---|---|---|
| $L_A$ (Palindrome) | entscheidbar | Zwei-Zeiger-Vergleich, terminiert |
| $L_B$ ($a^n b^n$) | entscheidbar | Zählen und vergleichen, terminiert |
| $L_C$ (Halten leer) | semi-entscheidbar | Simulation akzeptiert, Reduktion vom Halteproblem |
| $L_D$ (5 Zustände) | entscheidbar | Syntaktische Eigenschaft, kein Rice |
Sei $\Sigma$ ein beliebiges endliches Alphabet mit $|\Sigma| \geq 1$. Zeige durch ein Diagonalargument, dass es Sprachen $L \subseteq \Sigma^*$ gibt, die nicht entscheidbar sind. Bestimme dazu die Kardinalitäten von $\Sigma^*$, der Menge aller Turingmaschinen $\text{TM}_\Sigma$ und der Menge aller Sprachen $\mathcal{L} = \mathcal{P}(\Sigma^*)$.
Lösung anzeigen
Typische Klausurfragen · Lesen
Aufgabentyp 1 · Ein Alltagsproblem formalisieren
Gegeben ist eine Frage in Prosa, etwa: Enthält ein Text mehr Vokale als Konsonanten? Gefragt sind Alphabet, Sprache und Modelltyp. Falle: die Antwort besteht nicht aus einer Zahl, sondern aus einer Mengendefinition $L = \{\, w \in \Sigma^* \mid \ldots \,\}$. Wer nur ein Beispiel angibt, verliert Punkte.
Aufgabentyp 2 · Instanz von Frage trennen
Ein Text beschreibt ein Problem und mehrere Beispieleingaben. Gefragt ist, welche Teile Instanz sind und welche zur Frage gehören. Falle: Werte, die zwischen den Beispielen variieren, sind Instanz; die feste Eigenschaft ist die Frage. Konstanten im Problem gehören meist zur Frage.
Aufgabentyp 3 · Entscheidbar oder nicht
Eine Sprache ist informell definiert. Gefragt ist, ob sie entscheidbar ist, und Begründung. Falle: Halteproblem-verwandte Sprachen sehen entscheidbar aus, sind es aber nicht. Immer prüfen: hält der beschriebene Algorithmus auf jeder Eingabe?
Aufgabentyp 4 · Berechenbarkeit vs. Komplexität abgrenzen
Eine kurze Aussage wie das Problem ist in $O(n^2)$ lösbar wird kommentiert. Frage: was folgt daraus für die Entscheidbarkeit? Antwort: das Problem ist trivialerweise entscheidbar, denn ein Zeitalgorithmus existiert. Umgekehrt sagt Entscheidbarkeit allein nichts über Effizienz aus.
Fragen zum Selbsttest
1. Was ist der Unterschied zwischen einer Instanz und einem Problem?
Ein Problem ist eine Familie gleichartiger Fragen, formalisiert als Sprache $L \subseteq \Sigma^*$. Eine Instanz ist ein einzelner Eingabewert $w$, für den geprüft wird, ob $w \in L$. Die Instanz variiert von Fall zu Fall, das Problem bleibt gleich.
2. Warum wird ein Computer-Problem als Sprache über einem Alphabet dargestellt?
Weil jeder Rechner nur endliche Symbolfolgen lesen und schreiben kann. Jede Eingabe muss codierbar sein, also als Wort über einem endlichen Alphabet darstellbar. Die Ja-Menge aller akzeptierten Eingaben bildet dann die zugehörige Sprache. Diese Vereinheitlichung erlaubt formale Beweise, die unabhängig vom konkreten Anwendungsfeld gelten.
3. Erkläre den Unterschied zwischen Berechenbarkeit und Komplexität.
Berechenbarkeit fragt, ob überhaupt ein Algorithmus existiert, der ein Problem löst und dabei terminiert. Komplexität setzt Berechenbarkeit voraus und fragt zusätzlich nach dem Aufwand in Zeit oder Platz. Ein unberechenbares Problem hat keine sinnvolle Komplexität, denn es gibt keinen Algorithmus, dessen Kosten man messen könnte.
4. Was bedeutet es, dass eine Sprache entscheidbar ist?
Es existiert eine Turingmaschine, die bei jeder Eingabe $w$ nach endlich vielen Schritten hält und dabei akzeptiert genau dann, wenn $w \in L$. Wichtig ist die Terminierung auf allen Eingaben, nicht nur auf denen aus $L$. Hält die Maschine bei manchen Eingaben nicht, ist die Sprache höchstens semientscheidbar.
5. Warum brauchen wir Automaten und Turingmaschinen als formale Modelle?
Weil sich Aussagen wie es gibt keinen Algorithmus nur beweisen lassen, wenn Algorithmus mathematisch definiert ist. Reale Programmiersprachen sind zu komplex und zu vielgestaltig. Automatenmodelle sind minimal und präzise; die Church-Turing-These sagt, dass sie trotzdem jede intuitiv berechenbare Funktion erfassen. Erst dadurch werden Nichtberechenbarkeitsbeweise überhaupt möglich.
6. Zeige informell, dass es unentscheidbare Probleme geben muss.
Über einem festen Alphabet gibt es abzählbar unendlich viele Turingmaschinen, denn jede lässt sich als endliches Wort codieren. Die Menge aller Sprachen $L \subseteq \Sigma^*$ ist jedoch überabzählbar, da sie die Potenzmenge $\mathcal{P}(\Sigma^*)$ einer abzählbar unendlichen Menge ist. Es gibt also mehr Sprachen als Maschinen, folglich existieren Sprachen, für die keine Turingmaschine existiert. Diese sind unentscheidbar.
7. Welche der folgenden Beschreibungen ist ein Entscheidungsproblem? (a) Gib die kürzeste Route aus. (b) Gibt es eine Route kürzer als 100 km?
Nur (b) ist ein Entscheidungsproblem, denn es hat eine Ja-Nein-Antwort. (a) ist ein Suchproblem beziehungsweise ein Optimierungsproblem, das eine strukturierte Ausgabe verlangt. Optimierungsprobleme lassen sich aber meist in Entscheidungsprobleme umformulieren, indem man eine Schranke einführt. In der Theorie arbeiten wir fast ausschließlich mit der Entscheidungsvariante.
8. Ist die Sprache $L = \{\, w \in \{0,1\}^* \mid w \text{ enthält gleich viele Nullen und Einsen} \,\}$ entscheidbar? Begründe.
Ja. Eine Turingmaschine zählt in einem Durchlauf die Nullen und die Einsen und vergleicht die beiden Werte. Sie hält bei jeder Eingabe nach linear vielen Schritten. Nebenbei: die Sprache ist nicht regulär, da man einen unbeschränkten Zähler benötigt, aber sie ist kontextfrei und damit auch entscheidbar. Entscheidbarkeit und Regularität sind zwei verschiedene Eigenschaften.
9. Ein Kollege sagt, ein Problem sei nicht lösbar, weil sein Algorithmus zu langsam ist. Ist das ein Berechenbarkeitsargument?
Nein. Zu langsam bezieht sich auf Komplexität, nicht auf Berechenbarkeit. Solange irgendein Algorithmus existiert, der auf allen Eingaben terminiert, ist das Problem entscheidbar. Ob dieser Algorithmus in der Praxis brauchbar ist, ist eine separate Frage. In der Klausur sauber trennen: existiert ein Algorithmus versus wie teuer ist er.
10. Warum ist die Codierung der Instanz in $\Sigma^*$ ein eigener Arbeitsschritt und nicht trivial?
Weil unterschiedliche Codierungen zu unterschiedlichen Komplexitäten führen können. Eine Zahl $n$ in Unärcodierung hat Länge $n$, in Binärcodierung nur $\lceil \log_2 n \rceil$. Ein Algorithmus mit Laufzeit polynomiell in der Eingabelänge ist bei Unärcodierung deutlich schneller als bei Binärcodierung. Für Berechenbarkeit ist die Codierung meist egal, für Komplexität aber entscheidend. Deshalb wird die Codierung explizit angegeben.
Dos and Donts in der Klausur
Sprache immer als Mengendefinition $L = \{\, w \in \Sigma^* \mid \ldots \,\}$ aufschreiben, nicht als Aufzählung einzelner Wörter oder als Programmcode.
Alphabet und Codierung explizit benennen, auch wenn sie offensichtlich scheinen. Ohne $\Sigma$ ist die Sprache formal undefiniert.
Bei Entscheidbarkeitsargumenten immer prüfen, ob der Algorithmus auf allen Eingaben terminiert, nicht nur auf den akzeptierten.
Nicht Instanz mit Problem verwechseln. Die Frage ist wird gerade Zahl erkannt und nicht ist $6$ gerade.
Nicht mit Programmcode argumentieren, wenn nach einer formalen Sprache oder einem Modell gefragt ist. Java-Snippets bringen keine Punkte, wenn die Aufgabe nach $L$ oder nach einer Turingmaschine fragt.
Nicht Berechenbarkeit und Effizienz durcheinanderwerfen. Nicht praktikabel und nicht berechenbar sind fundamental verschiedene Aussagen.
Nicht vergessen, dass Sprachen unendlich sein dürfen. Wer nur endliche Beispielmengen aufzählt, hat die Aufgabe nicht verstanden.