| |
|
|
|
Levin´s Abstract Model of Computing
Eine äusserst allgemeine Rahmenbestimmung des Berechenbaren gibt Leonid A. Levin. Seine Konzeption lässt durch sukzessive Präzisierung und Spezifikation die verschiedenen Modelle des Berechenbaren, wie die des Zellulären Automaten, der Turing Maschine und der Pointer Maschine definieren und unter komplexitätstheoretischen Fragestellungen untersuchen. Meine Einführung beschränkt sich auf die fundamentalen Definitionen der Modelle, lässt die elaborierten Teile zur Komplexitätstheorie aus, und versucht Levins Model of Computation zum Ausgangspunkt der Dekonstruktion und zur Instruktion einer transklassischen Konzeption des Berechenbaren zu machen.
We start with terminology common to all models, gradually making it more specific to the models we actually study."
Dieser rechnende Raum wird sukzessive (gradually") durch Zeit- und Raumbestimmungen definiert. Dies geschieht durch die Operation der Spezifikation. Die sehr allgemeinen Bestimmungen von logisch-strukturellem Raum und Zeit werden nach Massgabe der vorausgesetzten Intuition des Computing sukzessive spezifiziert zu einem konkreten Modell des Berechenbaren. Was allen Modellen gemeinsam ist, ist vorerst noch generell und der Intuition zugehörig und wird spezifiziert gradually making it more specific". Vom Gesichtspunkt des Prozesses der Spezifikation ist es allerdings irreführend die Abstraktheit des Abstract Models" zu thematisieren, denn diese gehört zum Bereich der formalen Systeme im Sinne eines Formalismus und nicht zum Bereich eines Systemismus. Die Spezifikation bezieht sich auf das Generelle (Husserl) und nicht auf das Abstrakte. Das Generelle wird durch Spezifikationsregeln spezialisiert und in ein Model of Computing" einer jeweiligen Situation überführt.
Der Zeit im logischen Sinne scheint eine ausgezeichnete Rolle zuzukommen. Sie hat lineare und unitäre Struktur. M.a.W., es gibt eine und nur eine Zeit, es gibt also keine Mehrzeitigkeit, keine Zeitzyklen und zeitliche Rhythmen (wichtig etwa für lebende Systeme). Die Zeit wird absolut, unabhängig von einem Standpunkt der Thematisierung eingeführt bzw. in Anspruch genommen.
Eine Dekonstruktion des Begriffs der Zeit wie sie von Heidegger und Derrida in Gang gesetzt wurde, hat hier keinen Eingang gefunden.
L. A. Levin, Fundamentals of Computing,
http://www.cs.bu.edu/fac/lnd/toc
Zur Stabilisierung des akademischen Vorwissens, sei auf die Literatur verwiesen, insb. auf:
Michael Sipser, Introduction to the Theory of Computation, PWS 1997
Melvin Fitting, Computability Theory, Semantics, and Logic Programming, Oxford Logic Guides: 13, Oxford 1987
Richard L. Epstein & Walter A. Carnielli, Computability, Wadsworth 2000
Rolf Herken (Ed), The Universal Turing Machine, Oxford University Press 1988
Einen vorwegnehmenden Überblick bietet der Conceptual Graph wie ich ihn aus dem Text Levins heraus destilliert habe. Ein Conceptual Graph gibt die konzeptionelle Abhängigkeit der Terme untereinander an (Cartwell).
Computations consists of events and can be represented as graphs, where edges between events reflect various relations."
Nodes and edges will have attributes called labels, states, values, colors, parameters, etc."
Die Modellierungssprache ist der Graphentheorie entlehnt. Diese kann hier sowohl in mathematischer wie in metaphorischer Bedeutung verstanden werden. Die ontologische Domäne, der Bereich der Objekte, des Seienden, der Etwase, um die es sich hier handelt sind die Events, Ereignisse. Ereignisse sind hier gänzlich klassisch zu verstehen, physikalisch, informatisch, logisch, semiotisch auf mit sich identisch Seiendes bzw. Semiotisches bezogen. Sie haben nichts zu tun mit den Ereignissen im Sinne Heideggers oder kenomischer Übergänge wie sie in den vorangehenden Kapiteln eingeführt wurden.
When a machine is in a given state and reads the next input symbol, we know what the next state will be-it is determined. We call this deterministic computation. In an nondeterministic machine, several choices may exist for the next state at any point." Sipser, p. 47
We require different labels for any two edges with the same source."
Damit wird der logisch-ontologischen Identitätsforderung genüge getan und garantiert, dass keine Widersprüche logischer oder ontologischer, bzw. event-bezogener Art zwischen den Attributen auftreten können.
Eine weitere graphentheoretische Bedingung die für das Modell erfüllt sein muss, ist naheliegendermassen, dass der Graph zusammenhängend ist und dass zwischen Wurzel (root) und Knoten (nodes) keine Lücken, Deadlooks und Deadloops oder Obstakel bestehen dürfen.
Edges of one type, called causal, run from each event x to all events essential for the occurance or attribute of x.They form an acyclic graph."
Die Ereignisstruktur, abgebildet auf Graphen, ist hierarchisch und hat einen Anfang, von dem aus die anderen Ereignisse erreichbar sind. Alle Ereignisse sind erreichbar innerhalb dieser Struktur. Es gibt keine Ereignisse ausserhalb des Systems.
Die Einzigkeit der Kontextur der Berechenbarkeit wird im Conceptual Graph durch die Abbildung des computation" auf die 1" symbolisiert.
Desweiteren wird bei Levin das Computing" mit dem deterministischen Computing gleichgesetzt und behauptet, dass die Konzeption des non-determisnistic computing später, relativ leicht einzuführen sei. Daher wird im Conceptual Graph das Computing ohne Unterscheidung in deterministic/non-deterministic notiert.
Damit wird in grosser Allgemeinheit der rechnende Raum, Area of Computation, eingeführt. Eine solche Domäne erfüllt die Bedingungen einer Kontextur. Da hier nur eine Kontextur eingeführt wird, ist dieser rechnende Raum mono-kontextural bestimmt. Die Grenzen dieser mono-kontexturalen Bestimmung des rechnenden Raumes zeigen sich in negativer Form in den Limitationstheoremen.
We will study only synchonous computations.
Their nodes have a time parameter. It reflects logical steps, not necessarily a precise value of any physical clock."
The subgraph of events at a particular value of time (with pointers and attributes) is an instant memory configuration of the model." (s. Ealgebras, Gurevich)
Strukturierung der rechenaktiven Umgebung: sequentiell v. parallel.
The models with only a single active area at any step of computation are sequential. Others are called parallel."
Es scheint mir nahe zu liegen, Levins area of computation" mit dem Rechnenden Raum" von Konrad Zuse in Verbindung zu bringen.
Die Darstellungsmethode bzw. das Darstellungsmodell, oder auch die Metapher der Inskription und der Notation ist der Graph, mit seiner Terminologie der Graphentheorie: Kanten, Knoten, Wege, Bäume. Im dekonstruktiven Gegensatz dazu ist die Metapher des polykontexturalen Modells des Computing das Gewebe mit seinen Fäden, Verknotungen, Netzen, Rissen, Texturen, Netzen.
Wichtig ist auch Levins Strategie.
Non-determinist aspects of computations (inputs, interaction, error, randomization, etc.) are crucial and challenging in advanced theory and practice. Defining them as an extension of determinist computations is simple."
The simplest models are most useful for proving negative results and the strongest ones for positive results"
The latter, however, while simpler conceptionally, require elaborate models of definition."
Ich setze daher an bei den basalen Bestimmungen der einfachen Modelle des Berechenbaren bzw. Machinalen, d.h. bei den deterministic computations und lasse den Aspekt der non-deterministic computations ausgeblendet. Auch weil es sich im nachhinein zeigen wird, dass sich die komplexeren bzw. komplizierteren Konstrukte im Sprachrahmen der einfacheren modellieren bzw. simulieren lassen. Der wohl wichtigste Anknüpfungspunkt ist die sehr allgemeine Aussage Computations consists of events and can be represented as graphs, where edges between events reflect various relations." Aufgrund dieser Grundbestimmung des Berechenbaren mit ihren Termini computations, events und graphs, lassen sich entsprechende Dekonstruktionen der klassischen Begrifflichkeit und eine polykontexturale Erweiterung des Berechenbaren angehen.
In diesem Teil der Arbeit geht es vorerst darum, vom Conceptual Graph des klassischen Computing einen Übergang bzw. eine Konstruktion zu einem Conceptual Graph des TransComputing als Basis der polykontexturalen Theorie des Berechenbaren und Machinalen zu finden.
In einem weiteren Schritt, dargestellt im Paragraphen zur Polykontexturalen Theorie des Berechenbaren, werde ich versuchen, auf eine noch basalere Ebene zuzugehen, in der weder logisch-strukturelle Zeit noch Raum vorausgesetzt werden müssen, und die somit jenseits" der Unterscheidung von deterministischen bzw. non-deterministischen Konzepten angesiedelt ist.Rigid deterministic computations
Wird die area of computation" weiter präzisiert, dann entstehen die rigiden Modelle des Berechenbaren, wie wir sie aus der Literatur kennen.
Bis dahin war diese topologische" Bestimmung offen und das Modell des Berechenbaren einzig durch die (sequentielle) Zeitstruktur bestimmt. Verbunden nun mit der Zeitstruktur ist das lokalisierbare Ereignis eindeutig bestimmt. Es erhält die Eigenschaften eines klassischen Objekts: Bestimmung in Raum und Zeit.
Combined with time, it designates the event uniquely."
Jegliche Ambiguität, Antinomie, Unbestimmbarkeit, Überdetermination oder Nebenbestimmbarkeit ist ab ovo ausgeschlossen aufgrund dieser raum-zeitlichen Bestimmung der Events in einem hierarchischen und azyklischen Graphen. Ein durch location" bestimmtes Objekt ist Element einer topologischen Struktur. Je nach der Topologie der Struktur des Ereignisraumes lassen sich verschiedene Modelle des Berechenbaren definieren.
Locations have a structure or proximity edges between them."
Je nach der Bestimmung der Struktur der Locations lassen sich verschiedene Maschinentypen unterscheiden. Die Strukturen können mehrdimensional für Zelluläre Automaten, eindimensional für Turing Maschinen und mit gerichteter Topologie für Pointer Maschinen definiert werden. Entsprechend lassen sich auch alle Sonderformen wie Turing Maschinen mit mehreren Bändern, Köpfen usw. auf der Basis der Bestimmung der Locations einführen. Ebenso kann die Topologie der Pointer, d.h. der Regeln stabil oder varierend, etwa für lernende oder evolvierende Maschinentypen definiert werden. Alle diese Bestimmungen, die das Reich des Machinalen charakterisieren, sind intra-kontextural bezogen auf time und locations restringiert.
CA are parallel rigid deterministic models. The configuration of CA is a (possibly multi-dimensional) grid with fixed (independent of the grid size) number of states to label the events. The states include, among other values, pointers to the grid neighbors. At each step of the computation, the state of each cell can change as prescribed by a transition function of the previous states of the cell and its pointed-to neighbors. The initial state of the cells is the input for the CA. All subsequent states are determined by the transition function (also called program)."
TM are sequential restricted CA.
In anderen Worten geben Dina Goldin und David Keil in Interaction, Evolution, and Intelligence eine knappe Kennzeichnung der Turing Machine in Abgrenzung zu ihrem Konzept der Interaktion. Das Wesentliche der TM wird dadurch nicht nur kurz beschrieben, sondern erfährt auch eine Situierung in einem allgemeineren Framework, das zusätzlich zum algorithmischen auch das interaktionistische Modell des Computing umfasst.
TMs model computations from strings to strings (S* -- >S*), or equivalently from natural numbers to natural numbers (N --> N). Any computation of a TM is a sequence of state transitions that always starts in the TM's initial state and may end in a halting state. The transitions are specified by a transition function, which is fixed for a given TM. Given the same input string, two computations of the same (deterministic) TM will be identical.
TM computation is algorithmic, where the values of all inputs are predeterminted at the start. It cannot be affected by subsequent changes to the environment; therefore, TMs compute as closed systems. Even though it is commonly thought that the TM computations are "what computers do", they actually model only individual input-processing-output steps of a computer, i.e., batch computing, or, in a GUI environment, a single event and the system's response.
Whereas a Turing machine stores no record of, and has no use for, previous input/output, this is not the case for adaptive agents. Both they and their environment can change as a result of interaction; the agent's behavior is shaped by this interaction history. History dependent behavior is characteristic of interactive computation, but absent from algorithmic computation."
The memory configuration of a Pointer Machine (PM), called pointer graph, is a finite directed labeled graph. One node is marked as root and has directed paths to all nodes."
Edges (pointers) are labeled with colors from a finite alphabet common to all graphs handeled by a given program. The pointers coming out of a node must have different colors. Some colors are designated as working and not used in input/outputs. One of them is called active. Active pointers must have inverses and form a tree to the root: they can be dropped only inleaves."
All active nodes each step execute an identical program."
PPM (parallel PM) is the most powerful model we consider: it can simulate the others in the same space/time."
Die klare Trennung von Raum und Zeit, time und space, bei der Definition des rechnenden Raumes, ermöglicht eine natürliche Einführung komplexitätstheoretischer Begriffsbildungen. Komplexitätstheorie steht hier schon im Anfang der Konstruktion. Die Theorie der Berechenbarkeit kann gewissermassen als Gebiet der Komplexitätstheorie aufgefasst werden. Nach Y. Gurevich, dessen Evolving Algebras (EA) eine gewisse Nähe zu dem Modell Levins hat, bildet die EA eine Verbindung zwischen Komplexitätstheorie und der Theorie der Berechenbarkeit.
...that this computation model bridges between complexity theory and formal methods." Gurevich, Evolving Algebras, p.1
"The greatest depth DA(x) of a causal chain is the number of computation steps. The volume VA(x) is the combined number of active edges during all steps. Time TA(x) is used (depending on context) as either depth or volume, which coincide for sequential models.
SA(x) of a synchronous computation is the greatest (over time) size of its configurations."
Evolving and emergent cellular atomata.
Non-determinist aspects of computations (inputs, interaction, error, randomization, etc.) are crucial and challenging in advanced theory and practice. Defining them as an extension of determinist computations is simple."
Church-Turing Thesis: TM s can compute every function computable in any thinkable physical model of computation.
This is not a mathematical result because the notion of model is not formally specified.
We can see now that all these machines can be simulated by the simplest of them: the Turing Machine."
Die TM wurde definiert als eine deterministische rigide sequentielle Maschine mit einer potentiell infiniten linearen Topologie, d.h. Band.
If any model computes a function in polynomial time, TM can do the same.
Eine Präzisierung der Intuition der Berechenbarkeit durch ein formales Modell, etwa als Turing Maschine, ist noch nicht ausreichend für eine Theorie der Berechenbarkeit. Weiter hilft ein universelles Maschinen Modell, das alle Teilmodelle und deren Verkettung zu simulieren imstande ist. (Normalformentheorem von Kleene)
Was nun für alle Maschinen gilt, muss notwendigerweise auch für eine spezielle Maschine gelten. Insb. auch für die Universelle Maschine selbst. Kann die Universelle Maschine sich selbst simulieren? Das Diagonalverfahren zeigt, dass dies logisch nicht möglich ist. (Unentscheidbarkeitstheoreme)
Die Einführung des Models of Computation zeigt sich bis dahin als geschlossener Bereich, der keine Interaktion mit einem Aussen kennt. D.h. die area of computation" ist intra-kontextural strukturell geschlossen definiert über dem Bereich der internalen Funktionen. Auch hier gelten die Hülleneigenschaften der Funktionen: Die Applikation internaler Funktionen auf sich selbst, ihre Superposition, führt nicht aus dem durch die internalen Funktionen definierten Bereich.
In einem ähnlichen Zusammenhang unterscheidet Y. Gurevich in seinem Modell der Berechenbarkeit, d.h. in seiner Evolving Algebra, zwischen internalen und externalen Funktionen. Die internalen Funktionen werden in statische und dynamische unterschieden. Die externale Funktion wird mit der schon von Turing bekannten Funktion eines Orakels in Verbindung gebracht.
External Functions cannot be changed by rules of A, but they may be different in different states of A. From the point of view of A, an external function is an oracle, an unpredictible black box that is used but not controlled by A."
Damit ist ein Wink gegeben, dass ausserhalb eines Models of Computation anderes Symbolisches sein kann. Ebenso wird ein point of view" eingeführt. Vom Standort der Polykontexturalitätstheorie sind jedoch Bestimmungen wie Innen/Aussen als chiastisch vermittelt zu verstehen und nicht Produkt einer Perspektivierung. Polykontexturale Standort- bzw. Standpunktwechsel sind logisch-strukturell fundiert und damit noch vor einem in der Wahrnehmung verankerten Wechsel der Perspektiven zu denken.
Die klassische Theorie der Berechenbarkeit identifiziert das Aussen mit dem Irrationalen, Unberechenbaren, das positiv betrachtet zum Orakel erhoben wird. Was nun, wenn von Standort einer anderen Kontextur das Orakel seine eigene Regularität hat und das Berechenbare im klassischen Sinne sich als irrational verkürztes Modell des allgemein Berechenbaren zeigt?
Hier ist somit ein Interface zur polykontexturalen Theorie der Berechenbarkeit gegeben, insofern als dieses Scharnier der Differenz von Innen/Aussen den Ort der Einführung transkontexturaler Übergänge markiert. Ein struktural geschlossener Zusammenhang ist eine Kontextur, zwischen Kontexturen bestehen diskontexturale Abbrüche, eine Vermittlung verschiedener Kontexturen zu Verbundkontexturen leistet einen trans-kontexturalen Übergang. Zwischen Elementarkontexturen und Verbundkontexturen gilt ein chiastisches Wechselspiel. Keine der polykontexturalen Begriffsbildungen ist stabil und statisch, doch auch keine ist willkürlich, chaotisch oder sonstwie relativistisch konzipiert.
Das skizzierte Abstract Model of Computation mit all seiner Begrifflichkeit ist in dieser Polykontexturalität zu distribuieren und zu vermitteln, d.h. zu disseminieren. Damit entsteht ein Gewebe rechnender Räume mit spezifisch transklassischen Strukturen und Operatoren mit einem Wirkungsbereich innerhalb und zwischen den rechnenden Räumen.
Any classisc system of logic or mathematics refer to a given ontological locus; it will describe the contextural structure of such a locus more or less adequately. But its statement -valid for the locus in question-will be invalid for a different locus."
What is infinite per se in the first universe may be treated as finite in the second."
The philosophical theory on which cybernetics may rest in the future may well be called an inter-ontology." G. Günther
 |
| |
|
|
|