Informatik
Webdesign
Lösungen
über uns
Kontakt
Home
|
||||||
|
Informatik |
Webdesign |
Lösungen |
über uns |
Kontakt |
Home |
|
||||||
|
||||||
|
In der Mathematik ist es immer als eine besonders interessante und wichtige Aufgabe angesehen worden, Algorithmen zur Lösung von Problemen zu entwickeln. Dabei ist ein Algorithmus normalerweise nur auf einen eng umschriebenen Problemkreis anwendbar, wie etwa der Euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen oder das bekannte Verfahren, mit dessen Hilfe die Quadratwurzeln aus natürlichen Zahlen in Dezimaldarstellung gewonnen werden können. So wichtig derartige spezielle Algorithmen auch sein mögen - so wäre es dennoch wünschenswert, über Algorithmen mit großer Tragweite zu verfügen. Um solche Algorithmen, die sich möglichst vielfältig anwenden lassen, hat man sich jahrhundertelang ohne rechten Erfolg bemüht. Erst in der zweiten Hälfte des letzten Jahrhunderts wurde ein bemerkenswerter Fortschritt erzielt, als es gelang, mit der Prädikatenlogik einen wichtigen Teil der logischen Schlußprozesse in die Gestalt eines Kalküls zu bringen. (Dabei spielte die Boolesche Algebra eine wesentliche Pionierrolle.) Man hätte nun vielleicht vermuten können, daß alle mathematischen Probleme algorithmisch lösbar seien. Doch mahnten wohlbekannte noch ungelöste Probleme (etwa das Wortproblem der Gruppentheorie, oder das zehnte Hilbertsche Problem, das die Frage nach der Lösbarkeit von diophantischen Gleichungen betrifft) zur Vorsicht. Immerhin war nun der Anstoß gegeben, die Frage nach dem Wesen des Algorithmus aufzuwerfen. Diese Frage hatte schon Leiniz gestellt, aber nicht zu lösen vermocht. Den Mathematikern unseres Jahrhunderts, geschult in der Behandlung abstrakter Probleme, vor allem auch in der Handhabung formaler Sprachen, war dagegen ein Erfolg beschieden: Um das Jahr 1936 wurden fast gleichzeitig verschiedene Vorschläge zur Präzisierung des Begriffs des Algorithmus bzw. verwandter Begriffe gemacht (Churchsche These). Obwohl diese Vorschläge, zu denen heute weitere getreten sind, von oft ganz verschiedenen Ausgangspunkten herrührten, haben sie sich als äquivalent erwiesen. Die Motivierungen für diese Präzisierungen, die Tatsache ihrer Äquivalenz und schließlich die Erfahrungstatsache, daß alle bisher in der Mathematik aufgetretenen Algorithmen, wenn man sich auf ihren wesentlichen Kern konzentriert, unter die präzisierten Begriffe fallen, haben die weitaus meisten Forscher auf diesem Gebiet dazu geführt, diese Präzisierungen als eine adäquate Fassung des zunächst intuitiv gegebenen Begriffs des Algorithmus anzusehen. Nachdem man einmal eine Präzisierung des Begriffs des Algorithmus angenommen hat, wird es möglich, die Frage anzugreifen, ob es wohldefinierte Problemkomplexe gibt, die einer algorithmischen Behandlung unzugänglich sind, und gegebenenfalls konkrete Probleme dieser Art anzugeben. Viele solche Untersuchungen sind in den letzten Jahrzehnten durchgeführt worden. Man hat so die Unentscheidbarkeit der Arithmetik und anderer mathematischer Theorien zeigen können, ferner die Unlösbarkeit des Wortproblems der Gruppentheorie und des zehnten Hilbertschen Problems. Manche Mathematiker halten diese Ergebnisse und die ihnen zugrunde liegende Theorie für die am meisten charakteristische Leistung der Mathematik der ersten Hälfte des zwanzigsten Jahrhunderts. Konzediert man die Legitimität der vorgeschlagenen Präzisierungen des Begriffs des Algorithmus und verwandter Begriffe, so kann man sagen, daß die Mathematiker mit rein mathematischen Methoden gezeigt haben, daß es mathematische Probleme gibt, welche nicht mit dem Rüstzeug der rechnenden Mathematik behandelt werden können. Diese Tatsache ist im Hinblick auf die große Rolle, welche die Mathematik in unserem heutigen Weltbild spielt, von erheblichem philosophischen Interesse. Post spricht von einem Naturgesetz über die "limitations of the mathematicizing power of Homo Sapiens". Hier findet man auch einen Ansatzpunkt zur Diskussion der Frage, worin die eigentliche schöpferische Leistung des Mathematikers besteht. In diesem Buch soll eine Einführung in die Theorie der Algorithmen gegeben werden. Es wird besondere Mühe darauf verwandt, den Leser davon zu überzeugen, daß die vorgeschlagenen Präzisierungen die intuitiven Begriffe adäquat wiedergeben. Die Präzisierung, bei der man das wohl am besten einsehen kann, ist der Begriff der Turingmaschine, der hier als Ausgangspunkt gewählt wird. Auf dieser Basis werden die wichtigsten konstruktiven Begriffe behandelt, wie die Begriffe der berechenbaren Funktion, der entscheidbaren Eigenschaft, und der durch ein Regelsystem erzeugbaren Menge. Es werden verschiedene andere Präzisierungen des Begriffs des Algorithmus besprochen (z. B. die μ-Rekursivität, die Rekursivität) und ihre Äquivalenz bewiesen. Als Anwendungen der Theorie werden unter anderem die Unentscheidbarkeit der Prädikatenlogik und die Unvollständigkeit der Arithmetik bebandelt; ferner wird als wichtigste Vorstufe für den Beweis der Unlösbarkeit des Wortproblems der Gruppentheorie die Unlösbarkeit des Wortproblems für Thue-Systeme gezeigt. Die Theorie wird dargestellt vom Standpunkt der klassischen Logik. Das macht sich besonders bemerkbar durch die Verwendung des klassischen Existenzoperators, z.B. in der Definition der Berechenbarkeit: Man nennt eine Funktion berechenbar, wenn es einen Algorithmus zur Auffindung der Werte für beliebige vorgegehene Argumente gibt. - Es wird jedoch überall dort, wo Beweise konstruktiv durchgeführt werden, und das ist überwiegend der Fall, diese Tatsache besonders hervorgehoben. ... Hermes, H., Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit; |
|
||||
|
(c) 2004-2011 computerfeld robert grübel |
||||||