Unberechenbar
Turing war durchaus bewusst, dass menschliches Denken umfassender ist als bloße Berechenbarkeit: Das Halteproblem wurde 1936 von ihm als Beleg dafür konstruiert, samt Beweis seiner Nicht-Berechenbarkeit. Hier schlägt der Gödelsche Unvollständigkeitssatz zu ...
Das Turingsche Halteproblem erhielt viel theoretische Aufmerksamkeit und wurde 1951 im Satz von Rice(öffnet im neuen Fenster) entscheidend verallgemeinert. Die Kernaussage: Turing-mächtige Systeme können im Allgemeinen nicht entscheiden (für alle Fälle berechnen), ob ein Programm eine nicht-triviale semantische Eigenschaft besitzt.
Beispiele für diese Nicht-Entscheidbarkeit sind etwa, ob das Programm eine vorgegebene mathematische Funktion korrekt implementiert oder ob zwei verschiedene Programme denselben Algorithmus implementieren. (Die Einschränkung "im Allgemeinen" rührt daher, dass praktisch wenig relevante Sonderfälle konstruierbar sind, in denen durch entsprechende Einschränkungen der Algorithmen die Entscheidung möglich wäre.)
Kompetente Menschen mit entsprechenden Programmier- und Debug-Fähigkeiten lösen Probleme, die unter den Satz von Rice fallen, dauernd: Programmieren einer Spezifikation sowie Fehlersuche und -korrektur, und zwar jenseits der konstruierbaren Sonderfälle. Das ist – weil es nicht jeder Mensch kann und auch nicht bei jedem Problem – zwar kein strikter, formaler, mathematischer Beweis, aber ein sehr, sehr starkes Argument dafür, dass der Mensch mächtiger ist als Turing-Maschinen und ihre äquivalenten Geschwister.
Jenseits von Turing ...
Das stellt diejenigen, die an eine AGI (Artificial General Intelligenz) – also eine menschenähnliche KI – glauben, vor ein fundamentales Problem. Spätestens nachdem die Emergenz-These wackelt, fällt dann unweigerlich der Begriff Hypercomputation: konkret, dass KNN(öffnet im neuen Fenster) zur Hypercomputation fähig seien – also Dinge berechnen könnten, die durch Turing-Maschinen und ihre Äquivalente nicht berechenbar sind.
Nun muss man aber klar zwischen nützlicher theoretischer Fiktion und realisierbarer Computation, also durchführbarer Berechenbarkeit, unterscheiden. Tatsächlich gibt es eine ganze Reihe theoretischer Fiktionen, die mächtiger sind als Turing-Maschinen und ihre Äquivalente.
Turing selbst hat neben der "a-machine" – dem, was wir heute als Turing-Maschine kennen – eine "o-machine" als Gedankenexperiment untersucht. Das "o" steht dabei für "Orakel". Die "o-machine" ist also eine "a-machine", die dort, wo keine algorithmische Berechnung möglich ist, ein Orakel um Lösung ersucht – beispielsweise jemanden wie Turing, der als Mensch eben nicht durch die Turing-Mächtigkeit gebunden ist.
Letztlich also genau die Vision, die im Rahmen der symbolischen KI später durch die automatischen Beweis-Assistenten realisiert wurde, nachdem die Einsicht dämmerte, dass vollautonome "automatische Beweiser" nicht realistisch sind. Die automatischen Beweis-Assistenten erledigen die mechanistisch durchführbaren Teile der Beweiskette, halten dann an und ersuchen kompetente Menschen um Hilfe ...
Ähnlich die NDTM (nicht-determistische Turing-Maschine): Sie kann verschiedene Berechnungswege gleichzeitig versuchen und so den richtigen wählen. Mit dieser Fähigkeit kann sie das Halteproblem lösen, ist also mehr als Turing-mächtig.
Ein ähnliches, aber einfacheres und intuitiv verständliches Konzept: Die Zeno-Maschine(öffnet im neuen Fenster) ist eine Turing-Maschine, bei der sich die Ausführungszeit für einen Berechnungsschritt bei jedem Schritt halbiert. Dauert der erste Schritt also eine Sekunde, dauert der zweite eine halbe Sekunde, der dritte eine Viertelsekunde und so weiter.
Die Endlosschleife wird in zwei Sekunden erledigt! So können also in endlicher Zeit unendliche viele Berechnungen durchgeführt und damit natürlich auch das Halteproblem der Turing-Maschinen gelöst werden. Aber Gödel schlägt auch hier zu: Die Zeno-Maschine kann das Halteproblem der Zeno-Maschinen nicht lösen!
Natürlich ist klar, dass diese Konzepte und ihre vielen Geschwister rein fiktiv und nicht realisierbar sind. Warum befasst man sich mit solch arkanen Konstrukten?
Genauso, wie es verschiedene Grade von Unendlichkeit gibt, gibt es auch eine Feinstruktur in der Unentscheidbarkeit, der Nicht-Berechenbarkeit und der Berechenbarkeit selbst, die so aufgeklärt werden kann. Diese Art wilder Gedankenexperimente hat also einen Nährwert, der aus den entsprechenden wissenschaftlichen Artikeln auch klar hervorgeht.
Wie Quantenmechanik, Relativitätstheorie und das Besteigen von 8.000ern ohne Sauerstoff ein Extremsport für eine Handvoll Leute – mir ist, ehrlicherweise, die Luft da oben zu dünn ...
- Anzeige Hier geht es zu Künstliche Intelligenz: Wissensverarbeitung bei Amazon Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.