Bachelorthesis: Theoretische Konzepte und Entwicklung einer Software für eine mechanische Turingmaschine

Download PDF

Abstract

Das Modell der Turingmaschine (TM) ist die Grundlage für viele Beschreibungen und Beispiele innerhalb der theoretischen Informatik. Im Vergleich zum Lebenszyklus einer Programmiersprache hat sich an dieser theoretischen Basis nur wenig geändert. In der Lehre der Automatentheorie ist es ein essentieller Bestandteil. Im Wintersemester 08/09 haben Studenten der Århus Universität eine mechanische Turingmaschine aus Lego Mindstorms Produkten realisiert. Die Grundidee besteht darin, die TM als Roboter, der sich auf Schienen (Turing-Band) bewegt, darzustellen. In einem gemeinsamen Projekt mit meinem Kommilitonen Sebastian Flothow (B.Sc.) haben wir dieses Modell in der Bestrebung übernommen, es konzeptionell und technisch zu verbessern. Zu Beginn dieser Thesis liegt eine mechanische Turingmaschine als Prototyp vor. Auf dessen Basis wird diese Arbeit das Exponat softwareseitig komplettieren. Zum Abschluss des Projekts steht ein Exponat für die Hochschule RheinMain, mit dem das Modell Alan Turings von einem breiten Publikum nachvollzogen werden kann.

Ziel dieser Arbeit

Aufgabe und Thema der vorliegenden Abschlussarbeit ist die Entwicklung einer geeigneten Software für eine Lego Mindstorms Turingmaschine sowie einer Applikation auf einem separaten System, mit der Turingmaschinen modelliert und auf die Lego-Turingmaschine (LTM) überspielt werden können. Dabei werden die Anforderungen zur Verbesserung des Vorgängermodells aus Århus sowie der Anspruch an ein möglichst authentisches Modell in Ausstellungsreife berücksichtigt. Es werden außerdem ausgewählte theoretische Konzepte und deren Relevanz für die Entwicklung der LTM vorgestellt.