kurse:ef05a-2021:turingmaschinen:pruefungsfragen [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== 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?
{{kurse:ef05a-2021:turingmaschinen:img_20210909_091721574.jpg?333}}
  * 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.

{{kurse:ef05a-2021:turingmaschinen:probepruefung-kommentiert.pdf}}