Turing-Maschinen und Berechenbarkeit

Eine der besonderen Leistungen von Alan Turing war seine im Jahr 1937 veröffentlichte Präzisierung des Begriffes der »Berechenbarkeit«. Wir stellen die nach ihm benannte Turing-Maschine als Konzept einer theoretischen Rechenmaschine vor und zeigen ihre Funktionsweise. Turings universelle Maschinen erlauben bereits eine rudimentäre Programmierung. Grundideen der Turing-Maschinen finden sich auch in heutigen Computern. Ihr eigentlicher Wert liegt aber darin, dass sie einen Maßstab für die Beurteilung der Schwierigkeit von Problemen bereitstellen und damit Grenzen der Berechenbarkeit aufzeigen. Weiter stellen wir reale Modelle universeller Turing-Maschinen vor, wie sie in der Ausstellung zu sehen sind, und zeigen den Einfluss der praktischen Realisierung auf die Theorie.