RESAC: eine resolutionsbasierte Künstliche Chemie und deren Anwendungen
Creators: name: Busch, Jens
Publisher: name: Universität Dortmund
Year: 2004
Subjects: subject: Künstliche Chemie
subject: Resolution
subject: Emergentes Rechnen
subject: Molekulares Rechnen
subject: Parallele Berechnung
subject: artificial chemistry
subject: resolution
subject: emergent computation
subject: natural computation
subject: parallel computation
subject: 004

description: Die Dissertation stellt ein konstruktives dynamisches System vor. Kennzeichen eines solchen Systems ist die Bildung neuer Komponenten, die selbst wiederum auf die Systemdynamik einwirken. Die Modellierung, Simulation und Analyse erfolgt im Rahmen einer Künstlichen Chemie (KC). Diese an die Chemie angelehnten, aber abstrakteren Modelle sind sehr gut geeignet, hochgradig parallele Systeme zu simulieren. Das globale Verhalten ergibt sich emergent aus dem Zusammenspiel einer Vielzahl von lokalen Interaktionen (Reaktionen) zwischen wenigen Objekten. Die vorliegende Arbeit führt durch Festlegung der Objektstruktur sowie der Reaktionsvorschrift eine besondere Form der KC ein: die resolutionsbasierte Künstliche Chemie, kurz RESAC. Diese Spezialisierung vereinfacht den Umgang mit KC-Systemen und ermöglicht eine einheitliche Konstruktion und Analyse. Das Reaktionsverhalten ist dabei durch die Anwendung der aus der Logik bekannten Resolutions-Inferenzregel implizit festgelegt. Da die Wirkung prinzipiell bekannt ist, erhält man durch diese Konstruktion eine dynamische Regel, die gleichzeitig vielseitig und vorhersagbar ist (Potenzial und Steuerung). Dem Anwender bleibt so allein die Aufgabe, die Moleküle zu definieren, deren Struktur wiederum vorgegeben ist durch die Syntax der Prädikatenlogik 1. Ordnung. Bei dieser Art der Programmierung ist kein tief gehendes Wissen über die Theorie Künstlicher Chemien nötig. Um vom verteilten Rechnen ohne Steuerinstanz, ferner von der Parallelität und von Emergenzphänomenen zu profitieren, muss allein eine auf der Syntax der Prädikatenlogik aufbauende Problemrepräsentation gefunden werden. Möglicherweise öffnet dies die KC-Forschung für einen größeren Anwenderkreis, vielleicht auch für die Industrie.Die Arbeit zeigt die Konstruktion und Parallelisierung einer resolutionsbasierten KC sowie deren Grenzen und Anwendungsmöglichkeiten auf dem Gebiet der anwendungsorientierten Problemlösung. Da das System mindestens über die gleiche Ausdruckskraft wie herkömmliche Programmiersprachen verfügt, wird gleichsam eine Programmierbarkeit der KC erreicht. Ein besonderer Anwendungsbereich ist das automatische Theorembeweisen, worauf vertiefend eingegangen wird. Neben der Realisierung in großen Rechenclustern wie beim Grid-Computing wird eine Übertragung auf natürliche Prozesse mit inhärentem massiven Parallelismus diskutiert und angedacht. Die hohe Informationsdichte und Reaktionsgeschwindigkeit, ferner ein hoher Grad an Parallelität übertrügen sich auf RESAC. In diesem Fall fungierte RESAC als Bindeglied zwischen traditioneller Problemformulierung (Logik) und neuen Berechnungsparadigmen.
description: Inspired by real chemical processes, artificial chemistries (ACs) follow an intriguing computational paradigm. Abstract molecules (objects) interact in an autonomous, distributed and parallel way. Guided by reaction rules these objects act on one another, thereby proliferating or altering their information content or structure. Modified structure may imply a different function according to the imposed interaction scheme. Consequently, the role of a molecule can change in time, so AC provides a powerful framework to define constructive systems. In this thesis, a resolution-based AC named RESAC is presented, which incorporates the resolution inference rule as the only interaction rule. Being universal and predictable at the same time (thus offering potential and control), this interaction scheme simplifies the AC design and the analysis of the dynamics of the system. In combination with the first-order predicate logic (FOPL) serving as a general and intuitive molecule structure, a programmable AC is gained. Once converted to FOPL, any problem exactly fits this restricted AC model and thereby benefits from parallel and distributed computation driven by non-deterministic emergent processes. This thesis introduces RESAC and shows its construction and parallelization. Furthermore, the system is analyzed and its application area is under examination. Besides programming ACs a traditional application is investigated in detail: automated theorem proving.The presented system can easily be transferred to parallel computing platforms like multi-processor systems or distributed internet agents due to the inherent parallelism. A transfer to natural computing systems is mentioned and considered a challenging future task.