Zeitung Heute : Turing-Maschinen

MARKUS VON RIMSCHA

Schon bevor die ersten real existierenden Computer gebaut wurden, machten sich Mathematiker Gedanken über theoretische Fragen wie die der Berechenbarkeit.Dieser Begriff scheint intuitiv einfach erfaßbar zu sein.Es scheint klar zu sein, wann eine Funktion im mathematischen Sinne berechenbar ist.In diesem Zusammenhang scheint auch die intuitive Vorstellung dessen, was unter Berechenbarkeit zu verstehen ist, ausreichend zu sein.

Im Laufe der Zeit hat sich jedoch auch die inverse Fragestellung herauskristallisiert: "Wann ist etwas nicht berechenbar?".Dieses Problem ist insofern interessant, als daß man gar nicht zu versuchen braucht, ein Computerprogramm zur Lösung einer bestimmten Fragestellung zu entwickeln, wenn diese gar nicht berechnet werden kann.Eine intuitive Vorstellung dessen, was nicht berechnet werden kann, hat der Mensch aber kaum.Deswegen haben die Mathematiker zu Beginn dieses Jahrhunderts versucht, eine formale Beschreibung für den Begriff der Berechenbarkeit zu finden.

Alan M.Turing (1912-1954), ein englischer Mathematiker, hat 1937, 25jährig, die nach ihm benannte Turing-Maschine vorgestellt.Mit dieser gedanklich konstruierten Maschine sollte jede Berechnung, die überhaupt möglich ist, durchführbar sein.Bildlich gesprochen besteht dieses formal exakt beschriebene Werkzeug aus einem Schreib-Lese-Kopf, der sich auf einem Papierstreifen hin- und herbewegen kann.Dieser Streifen ist mit einer Eingabe beschriftet und kann verändert werden.

Mittlerweile gilt es als akzeptiert, daß mit dieser relativ einfachen Maschine tatsächlich alle diejenigen Funktionen berechnet werden können, für die das auch nach unserer intuitiven Vorstellung möglich ist.Turing hatte sein Ziel also erreicht.Die heute noch große Bedeutung dieser Entdeckung liegt im erwähnten Umkehrschluß.Wenn es nicht möglich ist, zu einer gegebenen Problemstellung eine Turing-Maschine zu konstruieren, die diese mit geeigneter Eingabe und entsprechenden Arbeitsschritten löst, so ist das betrachtete Problem überhaupt nicht durch einen Computer zu bearbeiten.

So ist es den Theoretikern mittlerweile bei vielen Problemen gelungen, deren Unlösbarkeit zu beweisen.Ist dies einmal geschafft, braucht keine Energie mehr in hoffnungslose Lösungsversuche investiert zu werden.Interessanterweise ist dies durchaus nicht nur für hochtrabende theoretische Überlegungen relevant, grau und wirklichkeitsfern gewissermaßen.Viele Probleme der Praxis haben sich leider als unlösbar erwiesen, obwohl sie auf den ersten Blick gar nicht so außergewöhnlich erscheinen.Dies gilt für eine Reihe von durchaus wichtigen Fragen, die sich der Informatiker nach der Entwicklung eines Programmes stellt.

Eine dieser Fragen ist beispielsweise, ob ein vorliegendes Programm bei jeder beliebigen Eingabe mit seiner Berechnung fertig wird oder ob es sich nicht vielleicht in einer Endlosschleife verrennt.Dieses Problem kann zwar für jedes einzelne Programm untersucht werden, es wäre aber viel komfortabler, ein übergeordnetes Verfahren zu entwickeln, welches diese Frage für jedes vorliegende Programm beantwortet.Man würde diesem "Überprogramm" nur noch die gerade entwickelte Anwendung vorsetzen und wüßte, ob diese wirklich nie in eine Endlosschleife gerät.Das ist leider unmöglich.

Ebenso wäre es interessant, ein solches Überprogramm zu entwickeln, das bei zwei vorliegenden Anwendungen die Frage beantwortet, ob diese identisch sind, also bei gleicher Eingabe die gleiche Ausgabe produzieren.Auch das ist unmöglich.So hat die vor über 60 Jahren vorgestellte Turing-Maschine heute noch in vielen Fragen große Relevanz.Die grobe Unterteilung eines Computers in den Rechenkern und den Speicher findet sich auch heute noch in real existierenden Maschinen.

Tagesspiegel - Debatten


Hintergründe und Expertisen zu aktuellen Diskussionen: Tagesspiegel Causa, das Debattenmagazin des Tagesspiegels.

Hier geht es zu Tagesspiegel Causa!

0 Kommentare

Neuester Kommentar