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.

probepruefung-kommentiert.pdf