Vorstellbare Prüfungsfragen

Der Fragenkatalog ist nicht vollständig.

Definieren Sie, was eine Turing-Maschine ist.
Erklären Sie die Begriffe «unäre», «binäre» und «dezimale» Darstellung von Zahlen.
Erklären Sie die Begriffe «Big-Endian» und «Little-Endian». Erwähnen Sie aus dem Alltag bekannte Beispiele.
Wenn man mit Binärzahlen mit einer beschränkten Anzahl Stellen arbeitet, warum kann 111…11 (lauter Einsen) als eine Darstellung von $-1$ aufgefasst werden?

Beschreiben Sie (d.h. liefern Sie eine Zustandsdefinition) eine Turing-Maschine, die
- unär 1 addiert.
- binär 1 addiert.
- unär mit 2 multipliziert.
- unär in binär oder umgekehrt umrechnet.
Definieren Sie, was eine «universelle Turing-Maschine (UTM)» ist.
Beschreiben Sie, wie ein Zustand einer TM für eine UTM codiert werden könnte und geben Sie ein Beispiel an.
Beschreiben Sie, was das «Halting Problem» ist und welche praktische Konsequenzen das hat.
Beweisen Sie das «Halting Problem».
Sei $S(n,m)$ die maximale Anzahl Schritte, die eine TM mit $n$ Zuständen und einem Alphabet von $m$ Zeichen, auf einem leeren Band machen kann und am Schluss noch stoppt. Zeigen Sie, dass $S(n,m)$ eine nicht-berechenbare Funktion ist.