L2 Turing machines

Autoren: Beat Trachsler und Paul Miotti

Die TM und ihr Begründer haben nicht nur eine technische, sondern auch eine besondere historische Bedeutung. Das Verständnis der TM ist für grundlegende Beweisführungen der theoretischen Informatik (Komplexität) unverzichtbar. Sie ist auch ein anschauliches Beispiel für die Stärke der Ideen.

1. Ich entwickle ein vertieftes Bewusstsein für ein konkretes und plausibles Maschinenmodell.
2. Ich bereite mich auf anspruchsvolle Argumentationen im Bereich der Berechenbarkeit und Komplexität vor.
3. Ich unterscheide zwischen Problemen, die sich mit Computern bewältigen lassen und anderen.

1. Ich verstehe die Definition einer TM und kann damit umgehen.
2. Ich habe Erfahrungen mit einigen klassischen Anwendungsbeispielen der TM.

• TuringKara

• L4 Complexity: Komplexität
• P0 Basics: EVA-Prinzip, Codierung von Ein- und Ausgabewerten

• Hier ist der Hintergrund klar. Man muss die Bedeutsamkeit dieses Modells und die Unterschiede zum realen Computer gut erklären. In keinem der L-Themen gibt es reale Computer. — Paul Miotti 2008/06/24
  • Ausnahme L6 Regular Expressions: Reguläre Ausdrücke — Vincent Tscherter 2008/06/24 10:37