Non-computable computations

In der Vorbereitung auf eine Seminararbeit von “Great Principles of Information Technology” bin ich gerade dabei, mich ein bisschen in Debatten über Berechenbarkeitstheorien zu vertiefen. Was mir dabei begegnet ist, dürfte auch philosophisch relevant sein:

Die Grundthese eines Artikels von “Jan van Leuuwen und “Jiri Widermann” (2000) ist, dass sich unsere Vorstellungen von dem Begriff der Berechenbarkeit verschoben haben. Berechenung ist nicht mehr nur ein mechanischer Prozess, den eine Maschine für sich alleine mit fixem Anfang und Ende ausführt, das Ergebnis ausspuckt und dann anhält, sondern unterliegt interaktiven und evolutionären, nicht-berechenbaren Elementen, die aus der Erfahrung, aus unvorhergesehenen Ereignissen kommen und die potentiell unendlich lange weiterlaufen:

The intuition that computing corresponds to formal computability by Turing machines … breaks down when the notion of what is computable is broadened to include interaction. Though Church’s thesis is valid in the narrow sense that Turing machines express the behavior of algorithms, the broader assertion that algorithms precisely capture what can be comptued is invalid.

In einer Zeit des Global Computing ist es fast ein Einzelfall, wenn ein Computer nicht mit anderen vernetzt ist. Das Verhalten des Computers verändert sich unvorhergesehen durch Viren, Software-Updates und Hardware-Updates. Diese Veränderung kann selbst nicht berechnet, sondern nur als evolutionärer Prozess beschrieben werden. Durch automatische Software-Updates und Viren können selbst Systemadministratoren nicht alle Eventualitäten dieser Veränderung überschauen.

Turing hat sein Maschinen-Modell dem Menschen, der isoliert am Fließband arbeitet oder der im Stillen mathematische Beweise führt, abgeschaut. Unsere Erfahrung zeigt, dass gerade durch die Realisierung dieses Maschinen-Modells Interaktion und Kooperation ins Zentrum unseres Interesses rücken und zu einer Erweiterung dieses Modells nötigen. Durch die Vernetzung entsteht neue Komplexität, die mit neuen Maschinenmodellen überschaut werden muss: “Interaktive Turing-Maschinen mit Beratungs-Funktion” ist die Antwort, die neue Art der Berechnung zu formalisieren. Die wesentlichen Unterschiede sind:

  • Berechnung ist verstanden als eine potentiell unendliche Transformation von Zeichenketten nach bestimmten (dynamisch änderbaren) Regeln
  • die Maschine kann mit anderen Maschinen oder mit der Umgebung Zeichenketten (d.h. Zwischenergebnisse der Transformation) austauschen
  • die Maschine kann eventuelle Ereignisse, die Auswirkung auf die Berechnungsmethode haben (SW-Updates,…), durch Abfragen der Beratungs-Funktion zur Veränderung der Berechnungsmethode heranziehen (a posterio-Anpassung des Berechnungsverfahrens)

Ein interessanter Schritt, der am Ende der Arbeit angedeutet wird ist, dass man dieses Berechnungsmodell zurückbeziehen kann auf die Phänomene in der sozialen Welt. Jeder Akteur kann als eine “interaktive Turing-Maschine mit Beratungs-Funktion” verstanden werden. Sie handeln aufgrund eines bestimmten Schemas, jedoch kann sich das Schema aufgrund von Ereignissen und Erfahrugnen ändern, sich sozusagen selbst korrigieren. Die “Beratungs-Funktion” ist das Fenster zwischen der a-priori Welt des “eingebrannten” Regelwerks und der a-posteriori-Welt der unvorhergesehenen Ereignisse und Erfahrungen:

Consider the case of a finite system of intelligent autonomous mobile agents that move around in some environment and exchange messages by whatever formalisable means: spoken language, via mobile phones, via the Internet, by ordinary mail, and so on. Occasionally, new agents appear and start to interact with their environment. Some agents may be killed by accident, some will not work properly, but all will die after some time. For some unpredictable reasons some agents may even behave better than any other previous ones. In general all agents are intelligent, which means that they are able to learn. In the course of their education new agents will successively become skilled, start to cooperate with other agents and perhaps invent new knowledge. The wohle society will develop.

Under suitable assumptions behaviours like this can be seen as ‘computations’ of a dynamic system of interactive Turing machines with advice. The assumptions are that all agents behave as interactive algorithms and that their evolutionary upgrades and moving around in the environment as well as their interaction as well as the times of their birth and death are captured in the respective advice. The similarty with the internet machine is obvious.[…] In the virtual world modeled in a computer a virtual society could develop as envisioned above. One could monitor the respective development and could make non-computable interventions into the underlying process.

Gottes Wege sind unergründlich, genauso wie für die virtuelle Bevölkerung jene Interventionen, die wir machen könnten, wenn wir die soziale Welt im Computer simulierten. Ist der aktuelle Crash der Finanzwelt genauso unergründlich? In gewisser Weise ist er ein Ereignis, der unsere Operationsweisen verändern kann, soviel kann man zugeben.

Ein kleiner technischer Hinweis: Die Beratungs-Funktion (advice-function) ist eine schwächere Form von dem, was Turing “Orakel” genannt hat. Die Turing-Maschine braucht nur eine Anfrage an das Orakel zu stellen und erhält im nächsten Schritt die gewünschte Antwort. Bei der Beratungs-Funktion werden die möglichen Anfragen eingeschränkt, sodass die Turingmaschine trotzdem noch die Notwendigkeit hat, selbst jene Berechnungen durchzuführen, die sie durchführen kann oder um zu verhindern, dass sie “cheatet” indem sie zu komplexe Fragen stellt.

Was auch immer von dem Vorhaben – die soziale Welt zu simulieren – zu halten ist, es ist bezeichnend, dass ein neues Paradigma der Berechenbarkeit diskutiert wird, das den Fokus auf Interaktion und Kooperation legt.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.