Computability, Self-Reference, and Self-Amendment

George Kampis

Dept. of Ethology, ELTE University, Budapest
Dept. of Theoretical Chemistry, University of Tùbingen, Germany

In: Communication and Cognition - Artificial Intelligence, Vol. 12, Nos. 1-2, pp. 91-109, Special Issue Self-Reference in Biological and Cognitive Systems, Luis Rocha (ed.)


    There exist theories of cognition that assume the importance of self-referentiality and/or self-modification. We argue for the necessity of such considerations. We discuss basic concepts of self-reference and self-amendment, as well as their relationship to each other. Self-modification will be suggested to involve non-algorithmic mechanisms, and it will be developed as a primary concept from which self-reference derives. A biologically motivated mechanism for achieving both phenomena is outlined. Problems of computability are briefly discussed in connection with the definability and describability of self-modifying systems. Finally, the relevance of these problems to applications in semantic problems of cognition is shown.

    We proceed in the following way. The paper starts with an outline of the evolutionary approach to cognition, as that context where the problems of circularity and recursiveness can be raised. Next, complete and incomplete forms of self-references are discussed. The "causal" theory of self-referentiality is reviewed, and a thought experiment is presented, which points out that no computable model for complete self-reference can exist. On the other hand, constructive definitions are shown to offer a framework where "self- defining" and self-modifying systems, if such exist in reality, can be formulated. Studying the realization problem, a general abstract model is given, and a "biological computation" mechanism that corresponds to it is outlined. The underlying phenomenon, called "shifting reading frame", is discussed in relation to how self-referentiality can be achieved through self-modification. The applicability of the approach to the autonomous definition of semantic relations in symbol systems, that may allow for a kind of autonomous "symbol grounding", is discussed.

I. Introduction

     Certain theories of cognition assume that selected aspects of mental activity can be characterized via self-referential or self-modifying constructs. Among them, the most widely known are those expressed in Hofstadter's "Gòdel, Escher, Bach" [1979], and in Maturana and Varela's "autopoiesis" [1980]. The latter was further developed in Varela, Rosch, and Thomson's "The Embodied Mind" [1991].

    Ideas of self-reference (and it self-modification), and their application to cognition have a much longer history, however. In mathematics, the problem of self-reference is more than twothousand years old. An obvious twentieth century example for its use is B. Russell's "barber paradox", that refuted the consistency of the Fregean system of set theory and logic, and led Russell to develop the theory of types. The cognitive and philosophical significance of such issues was first raised by the so-called BCL school, whose members and associates included W. McCulloch, W.R. Ashby, G. Gùnther, L. Lòfgren, H. von Foerster, and H. Maturana. An important work closely related to theirs but developed independently was H.H. Pattee's on "semantic closure" [1973]. Also related and in part motivated by the BCL thinking were theories of "radical constructivism", a school particularly active in the German tradition ([Waczlawick 1984] offers a summary). Radical constructivism maintains that mental events bring forth rather than exploit the observations to which they refer, and that the two can be understood in a circular fashion where knowledge and the knower are considered to be each other's reasons [Maturana and Varela 1987], just as in evolutionary epistemology [Callebaut and Pinxten 1987], only here with an anti-realistic attitude. And there is a vast literature on self-reference proper: the best source known to me, Suber and Bartlett's "Self-reference: reflections on reflexivity" [1987], is a collection of papers with a long bibliography, that brings over 1000 items, and is far from being complete.

    In a tradition of different origin, the idea of self- programming, or self-modification has emerged as a possible remedy to the often noticed stiffness of formal systems. At the root of the idea we find the intuition that a system should sometimes become something else than it was before; in other words, that its defining symbols can be both too vague and too narrow in comparison to processes of interest. Part of what in the seventies were called "goal-seeking systems", "catastrophes", or "dissipative structures" (characterized by a computational bottom-up approach that permits flexibility at a higher level) lived further in the eighties in connectionism and in the subsymbolic paradigm, or in the notion of "swarm intelligence". A good introduction to the flexibility aspect of subsysmbolic computations is A. Clark's Micro Cognition [1989]. Self-programming computers that could directly alter their own codes were already studied by von Neumann [1966], and several authors afterwards. Whether and to what extent self-programming can be carried out algorithmically, was always unclear, however.

We discuss some of the basic problems with notions of self- reference and self-modification in this paper, in particular, the problem of computability, and its relation to these concepts. In a recent book [Kampis 1991a] we have outlined a concept of self-modification beyond ordinary computation. Over and again, the paper will use material from that book.

II. Cognition: From Performance To The Process That Gives Rise To It

We have quoted various predecessors, but there is also a direct form how our problems can be raised. At the outset, a useful distinction between "competence modeling" and something like the "origin of competence" should be made. "Competence modeling" means to focus on the repetition of some cognitive performance in an essentially functionalistic fashion, where all that we want is that a performance similar to that of a human is achieved by some machine at any rate, whereas the "origin of competence" problem would be the opposite, referring to the acquisition of such cognitive faculties that make the achievement of the given performance possible. Learning is one example for such a process, but it is not the only one, as indeed various self-organizing theories of brain and mind function exist the targets of which range from neuralconnectivity to the problems of memory and the semantics of language.

The dynamic studies of cognition often use the metaphor of biological evolution. The parallel between the cognitive and evolutionary domains has been repeatedly noticed by many authors [Holland 1975, Csányi 1989, Dawkins 1975, Lumsden and Wilson 1981, Edelman 1987]. This metaphor proves very useful in many aspects of practical modeling. Yet, at the same time when evolution and its variation-selection mechanisms help illuminate several concepts in cognition, such as directed randomness, the spontaneous accumulation of useful information, or intrinsic parallelism, the metaphor also imports unsolved problems from evolution theory.

For instance, a question that has already bothered Darwin was, where comes the new information from? Or, to translate it to a more general language, why does evolution not stop after the necessary adaptations have taken place? Why are there always new species? The revolution of Darwinism was less about the existence of spontaneous evolution and descent, the concepts of which were already known before Darwin, but about another idea, which we would express today by saying that evolution is a productive process that needs an open universe. To say that evolution is a productive process, is not only to mean that new forms emerge that have not existed before, but also to imply that these new forms can feed back to the system by setting new conditions for subsequent evolution. In this sense, evolution should be seen as a process that is its own product.

In modern terms, biologists who recognized this problem started to speak of co-evolution [Van Valen 1973, Stenseth and Maynard Smith 1984], or recursive evolution [Conrad 1983] instead of simply any evolution. Van Valen's famous "Red Queen" theory says that successful adaptation in one species implies a worsening of the environment for others, so they have to re-adapt, or they have to perish, and in the end it takes all the running to stay where you are. The idea of recursive evolution is very similar, it refers to the fact that selective "tasks" and their "solutions" develop iteratively, the one giving rise to the other, and vice versa, so whenever a solution is achieved a new task is also defined. That is, we end up with a picture where circularity, and some sort of informational "self-sufficiency", or self-reference, of the source of internal change play an important role.

III. Forms of Self-Reference

Let us briefly review the various forms in which circularities exist. Self-reference can be complete or incomplete, that is, full or partial. Most of the cases we know from logic and its related fields like argumentation theory offer partial self-references. Statements like that of the undecidable sentence "This sentence is false" (i.e., the well-known Epimenides paradox, also called the Liar, or the Cretan, and its variants the Gòdelian sentence, or the hypothetical program that demonstrates the unsolvability of the Halting Problem) are by necessity only incompletely self-referential. Partiality enters here because the above sentence needs an external interpreter (like us) to make sense at all; terms like "this", "sentence" and "falsity" must be defined and understood a priori, and refer to classes outside the object under consideration. That is, literally, the sentence refers to something else also, not just to itself.

By analogy it would seem now that complete self-reference should be impossible or unintelligible, as we always need some "seed" to start with. However, that is not the case, as the existence of coherence theories of semantics, self-consistent fields in electrodynamics, and mathematical results like those of Lòfgren [1968] or Varela [1974] indicate. In other words,systems whose every term is internally defined by the very same system are possible. This can be illustrated on a well- known example. For an untrained Martian (or Hungarian, the difference is negligible), English (just as any other natural language) appears as a system of messages perfectly closed to itself. That is, the meanings of English words and sentences are given in the same English, which is of little help, unless you are a native speaker, and then you know English anyhow. This is a trap from which the only escape is through a door of extra-linguistic methods (such as that of pointing to the surrounding objects) -- or, by using dictionaries, but who made the first dictionary, and how?. Then, of course, we recognize that the act of pointing belongs to another language (namely, that of body talk), and so on, and therefore we are left with a hierarchy of languages, each inaccessible on its own, since body talk is no less esoteric than English if you don't happen to speak it (remember, you are a Martian now). If we know any one of these languages, we can probably bootstrap all, but without that, the system remains completely self-referential, and opaque. In other words, there must be an "initial translation", in order to open up the circles of meaning.

This thought experiment shows two points, the one is that complete self-reference is certainly possible, and second, that it does not make any sense at all. In other words, complete self-reference poses a problem for both description and handling.

From a formal point of view, the results of Lòfgren and Varela lead to the same conclusion. Lòfgren [1968] has shown that the axiom of complete self-reference is independent from set theory and logic, and can therefore be added to it as a new primitive. However, it is impossible, by the same result, to explain this (complete) self- reference by decomposing or deriving it in terms of the other axioms. That is to say, a completely self-referential object necessarily looks like something inapproachable, a perfectly closed class, perhaps a Kantian "Ding and sich", or a Leibnizian "Monad". (Let us note for the sake of interest that Lòfgren's work was also related to a biologically motivated mathematical problem, called perfect self-reproduction [Rosen 1959]). Varela's "Calculus for Self-Reference" [1974] reflects the same philosophy: he introduces self-referentiality as a third logical value besides truth and falsity (or, to be more precise, besides indicational and non-indicational states in the non-standard logical calculus of G. Spencer-Brown [1969]).

IV. The Ways of Self-Amendment

So far, we have dealt with self-reference, but the situation is quite similar with the notion of self-modification. Partial self- modification is easy to achieve; the complete form goes beyond ordinary mathematics and anything we can formulate. Consider, for instance, recursive programs. Every recursive program can be said to modify itself in some sense, since (by the definition of recursiveness) the exact operation carried out at time t depends on the result of the operation at t-1, and so on: therefore, the final "shape" of the transformation is getting defined iteratively, in runtime (a fact somewhat obscured by the usual way in which recursion is written down in high-level programming languages like C). At the same time, as we can expect, to every finite recursive program there belongs an equivalent "straight" program, that uses no recursion at all, and is perfectly well defined in advance, so that it does not change in any respect; it is simply a fixed sequence of a priori given elementary operations. Now some advanced structures such as list-processing languages like LISP allow for a direct manipulation of their program texts duringexecution, thus permitting the user to construct programs that actively rewrite themselves. Yet, again, there is a top-down structure associated with these programs, and even if the program list is altered, somewhere in this structure there is at least one level, namely the topmost level (or the bottom-most level, depending on how we think of it) that never changes. In the case of the LISP program, we find this unchanged level when taking into account the LISP interpreter, that translates program instructions to machine code. It is the same interpreter, no matter what we do, it does not get disturbed. But that is of course necessary, for otherwise we could not write and execute any program at all. Therefore, just as in the case of self-reference, and for the same reason, algorithmically derived self-modification can never achieve completeness: there must be a fixed point somewhere or the whole building collapses into nonsense.

The most interesting part of the story comes when we push the previous exercise to the extreme. If now somebody writes a tricky language that goes beyond the capabilities of LISP and changes its own interpreter as well, and then perhaps it changes the operating system, and so on, finally we find ourselves at the level of the processor chip of the computer that carries out the machine code instructions. Now, unlike the earlier levels, this level belongs to a piece of physical hardware, where things will be done the way the machine was once built, and this can no more be a matter of negotiations. Ultimately, this is what serves as that Archimedean starting point (similar to the initial translation that opens up self-reference) that defines a constant framework for the programs.

The importance of this is that we understand: self-modification, and self-reference, are not really just issues of programming (that is, of using the right software), but of designing a whole machine in some sense. Therefore, the impossibility of achieving complete self-modification depends, ultimately, on the separability of machine from program (and the way around): the separability of software from hardware.

V. Nomic, the Ultimate Game of Change

The complications of self-modification can be further studied on a delightful example P. Suber presents in his "The Paradox of Self- Amendment" [1990]. Suber introduces a logical game called Nomic (that has many similarities to the "game" of legislation in the USA).

Nomic formulates what can be called an "ultimate legal system". In a real-life legal system, laws regulate several things, including the way they can be changed. And laws sometimes do get changed.

In Nomic the only function of laws is to change, and of course, to govern, at the same time, how they can be changed. This system is designed as an actually playable game, where a move of a player is the attempted change of one law. The laws are passed or rejected by votes of the players. Just how many votes are needed for a law to pass is regulated by the very rules of the game, that is, by the other laws which also take part in the game, and are possible subjects to such changes. Certain laws are (at least according to the initial rule set of Suber) more difficult to change than others; it is instructive here to think of the first group as "constitutional" rules, and the second group as "normal" laws and statutes. Also, the first set of rules has (at least initially) a logical priority over the second set, and the newer rules over the older ones; but any of these rules can be withdrawn at the players' own discretion, as the game proceeds. Just to make it clear how far this can go, let us take a bizarre example: if the players want, they can transform Nomicinto Monopoly or any other party game, just by democratically introducing "laws" for the board, the dice and the cards, together with rules for how to use them, and then all the players have to do is to completely remove the original set of rules that allowed for the change of the rules at all. And here it is, your Monopoly. (However, Suber's game has such a cleverly chosen initial rule set, that a typical player will not want to turn the game into Monopoly but he or she will rather want to win. The winning conditions, just like anything else, are again part of the initial rule set, so before you changed the game too much, you are better off if you have a new law passed that favors your own moves (whatever they are), than by trying to transform the game into Checker just because you are the world champ.)

The actual game is somewhat more complicated than this (if that is possible), and involves the use of a two-chamber voting system, but these are unnecessary technicalities for the present discussion. The initial rule set consists of 29 different rules, some of which even offer conditions to decide whether a new rule is valid or not (i.e. whether the system is consistent).

It is easy to generate paradoxes in Nomic. A paradox occurs, for instance, when one of the chambers passes a law that regulates the work of the other, but it must be first validated by that chamber. For instance, chamber A decides that decisions of chamber B must be made by a 6-3 majority instead of a prior 5-4, but chamber B, when controlling the legality of this move, rejects it, by a 5-4 decision, of course. What has happened? There are many other questions one could raise about Nomic, as was done by D. Hofstadter in his column in Scientific American [1985].

For instance, can every initial rule be actually changed (remember that the initial rule set favors democracy)? On the other hand, can certain rules of the game be made truly immutable without stopping the change of the others? Can sudden changes (like revolutions) of the rule set occur, without violating the rules? And, finally, can this game be made algorithmic, or computable?

In the present form of Nomic, the changes come from "outside" the system, by the intervention of the players. Is it now possible to achieve the same outcome by the rules themselves? By this we mean: Is it possible to realize every desired transformation of the rule set by means of the same rule set? Can we write an initial rule set that prescribes every transformation of itself in such a way that even the further transformations of the by then already transformed rule set occur according to this original plan, without even the presence of the original rules?

Similarly, can a legal system be designed, or, to proceed now backwards, to evolutionary processes, cognitive models, and like: can self-modifying processes be made equivalent with processes that use fixed rule sets?

VI. Computability and Definability

The notion of computability is often understood in a deliberately narrow sense, as something confined to decidability. According to this simplistic view, a process is computable if there is an effective procedure that decides its outcome. In other words, a process is essentially then computable if there exists a program that computes it and then halts. There is, however, a different way of looking at the issue of computability: we can say, alternatively, that a function is computable if it is definable by some procedure that guarantees its decidability. Mathematical logic has offered already a long time ago something very close to this definition procedure. It is called lambda-definition, a method invented by A. Church in the thirties. Now, intuitively, adefinition is something more fundamental than the subsequent execution of an algorithm, and in this sense it is possible to say that, ultimately, computability boils down to definability. In the everyday context, this contention comes through in popular statements like the "hackers version" of the Church-Turing Hypothesis, according to which, "If you can define it, we can simulate it" [Kampis 1991a].

Put in this way, the crucial problem of complete self-reference can be reformulated as saying that a perfectly self-referential, or perfectly self-modifying system would not be defined at all, in the sense of being self-defining and hence empty.

VII. The Causal Theory of Self-Reference

Despite the many difficulties surrounding the notion of complete self-reference, it is surprisingly easy to show that the concept can be consistent with linear causality and can therefore be realized by some natural processes.

To see this, let us be more specific now as to what causes the self-referentiality of a linguistic expression. We do this in order to show later how this constraint can be relaxed, and hence self-reference eliminated, in a causal framework.

An important distinction of formal systems should be used here: the use/mention dichotomy. According to that, these two types of dealings must be always kept separate. To mention a word, is to quote it -- that is, to "protect" it somehow, such as with embedding quotation marks, that prevent it from exerting any effect in a statement. To use a word is simply to utter it, and hence state and express it. That is, "use" is active, and "mention" is passive. It is obvious that in self-reference the two functions get mixed, we are making statements with words and sentences about the very same words and sentences, as if they were just mentioned: the same thing is active and passive at the same time. So, for instance, when unfolding partial self-reference, it is this double nature that is eliminated first. What a vocabulary does for us when we first start to learn English is to help making sense of words before we start using them. The sentence "This sentence...", however, defines the sentence and uses its meaning at the same time to express something about itself. We understand this sentence intuitively because our psychological understanding is not delimited by this expressed meaning and/or truth of the sentence, so we can decompose the sentence into words with which we are familiar and we understand as passive tokens. In a situation involving complete self-reference, that is no more possible, however.

Yet there is a solution. We can try to think of the expression "this sentence" as a GOTO statement in some computer program, a program statement that refers to another place, to a label that is defined completely separately. It can now happen that this label then turns out to be the label of the very same GOTO statement. But who cares? That makes no difference. And yet it does, for in this way self-reference can be produced; this is precisely what Gòdel did when he constructed his undecidable sentence in two steps instead of one. To illustrate this method, we can say: "The next sentence is KLXPUZ127. KLXPUZ127 is false." No immediate circularity is involved: therefore, the underlying structure can be causally realized. Details of this construction were elaborated by Hart [1987]: Imagine, for instance, two people who pronounce these sentences, one after the other. The corresponding causal process has no unusual property; the summative description does.

The same argument can be used to solve the puzzle of complete self-reproduction, itself alogical impossibility (for a discussion of this problem, see [Lòfgren 1968], [Kampis 1991a]). Instead of the troubled circular form "A produces A" (where we would immediately ask, what is this A, in the first place? and we would have to answer, the definition of A is that it is this thing that produces A), there is now a causal way of representing the process as this: "A produces B" & "We demonstrate that A = B". Notice again the use of the two-step construction, and a presence of a causal precedence relation that opens up an initially closed referential circle.

As a consequence of this method, there is a possibility to unfold every closed self-definition as a temporal sequence of ordinary definitions, free of inconsistency or paradox.

VIII. Constructivism

Causality can imply self-reference, all right, but how can we describe this? What sort of causal processes are those that allow for such phenomena, or can any process be self-referential?

I shall now argue, as I have done elsewhere repeatedly [Kampis 1988, 1989, 1991, 1992], that a philosophy of mathematical constructivism should be adopted when dealing with a causal description of a self-referential or self-modifying situation (the reader will still remember that we have promised to reveal the connection of these two threads). This will mark certain processes are quite natural candidates for entangled phenomena.

The motivations of adopting constructivism in this context are essentially the same as they were in mathematics or in S. Harnad's "neo-constructivism" [1982]. Constructivism was initiated by mathematicians, like Kronecker and, above all, Brouwer, who felt uncomfortable with indirect proofs and implicit definitions, and in general with anything that was not directly accessible or tangible within mathematics. It is characteristic that one of the main objects of the constructivists' wrath was Cantor's set theory, with its notorious use, without any inhibition, of the concept of actual infinity, and its habit of talking about infinite sets as if they were explicitly known to us, compactly defined, with their elements given simultaneously. Brouwer, the leading figure of twentieth century constructivism, went very far in his purificatory enterprise against infinity. Many believe that he threw out the baby with the bathwater, and indeed in his "new" mathematics he did not succeed to prove even the simplest and most obvious theorems, the truth of which was nevertheless clear to him. On the other hand, constructivism is not necessarily related to the issue of infinity and it offers many important contributions within and outside mathematics (see, for instance, [Beeson 1985]). Of these uses of constructivism, we will focus on its tools for dealing with definitions.

Central to the constructivists' thinking is the concept of piecewise definition of mathematical entities (this is a point where an important connection to algorithms, as well as to discrete and "finitistic" mathematics exist). Piecewise definition is just the opposite of definition by "fiat", or "let" (which was dubbed as "definition by intimidation" in [Kampis 1992]). Instead of using a top-down method, it proceeds bottom-up. When carried out, such a constructivist definition requires groundwork and makes a revision of extensional definitions possible, in the form of allowing constructs like growing sets, for instance. Following the constructivistic suggestion, in systems definitions we are not supposed to write "state set X" but "state object xt", then "state object xt+1", and so on, and only at the end should we go and summarize these in an encompassing state definition [Kampis 1989]. What this has to do with our issue of causal definitions should not be difficult to see. The procedure I am going to suggest consists ofreplacing self-reference with a temporal (i.e. causal) "self- definition", then of realizing the latter with the aid of processes that need a self-constructing, that is, temporally growing (in this sense self-modification) constructivist definition. In other words, the processes that bring forth self-reference will be conceived as ones that get defined in the course of their own execution, my means of a growing universe of basic elements.

Let us stop here for a while to note that the unavoidable use of the term "self" can be very misleading at this point. Whereas we are still talking about the same self-referential and self-modifying systems as before, in a growing system there is no more an invariant entity that could be identified with any "self" to which we can refer. Rather, we deal with a temporally extended process the various stages of which together constitute an identity. However, if that is so, and we accept the conceptualization of processes that use a constructivist definition, this global entity nowhere appears on the local time scale of the process.

Let us also note that a constructive definition is "not algorithmic", in the same sense as setting up a formal system or designing an algorithm is never algorithmic. But when we proceed by a usual definition, it involves no temporal elements, that is, the whole definition can be finished prior to execution, and hence the subsequent temporal process can be algorithmically viewed, as a consequence of this definition. In the constructivist conception, however, the definition does not necessarily end when the process begins, so the "non- algorithmic" features extend to the causal process itself.

IX. Causal Systems that Need Constructivist Definition

Of course, that is all hypothetical so far, we spoke of constructively self-extending processes as if they existed, but how do we know that they exist at all? Maybe every process reduces to some sort of finite "fiat". It is difficult to think of any example offhand for the use or necessity of the constructivist definition. Now the next question is whether there are systems in actuality that need it. The answer I am suggesting is positive, and I will now try to show the existence of processes that "extend" or "modify" themselves, therefore they need new concepts exactly as foreseen in the discussion of the previous section.

More than that, my argument is that there is an abstract prototype for such systems, that can be studied independently from any realization. This prototype, which I believe is a generator of a wide class of related systems, is a system characterized by the inherent ability to produce its own components. Accordingly, I have suggested to call these kind of systems component-systems [Kampis 1991a]. A component-system does not have a fixed basic composition but produces new components for itself. An obvious real-world example is a macromolecular system with its chemical reactions.

In other words, the behavior of a component-system is similar to how we have depicted a game session in Nomic, where laws come and go, and after a while the structure of the system may be completely different from its initial one, with perhaps not even a single rule left intact. So, in a component-system the components can be conceived like the rules of Nomic, but there is one very important difference: whereas Nomic, or any other possible game of similar design, requires human players to interact with, in order to perform the moves, a component-system is conceived as an "automatic" causal system that executes the "moves" on its own. In other words, just to continue our metaphor, one could think of the elements of a component-system as "rules"that execute themselves so as to produce new "rules", in a system where the growth law is defined recursively, by itself.

Why we had to put quotation marks when speaking about the "rules" of a causal transformation was of course that these "rules" of component-systems do not have to be algorithmic, that is, they do not have to be finitely definable; that is the entire meaning of the enterprise, for that is what necessites a constructivist, growing definition. The mechanisms for that is what we discuss starting the next section.

But before that, it should be made clear that several other suggestions exist, the basic ideas of which are closely related to those of component-systems. They are reviewed in my book [Kampis 1991a]. Of them, let me mention one, Ròssler's "privileged zero" systems [1984], for their clarity. The expression "privileged zero" refers to the property that of components not yet produced there is not simply a zero amount but there is in fact none; Ròssler used this idea for pointing out that, for instance, to run chemical reactions, you don't have to buy all chemicals that appear in the transition matrix of the system (unlike with electric circuits); this "trick" has an importance for evolution, controlled ontogenesis, and the information theory of biochemical regulation.

X. Biological Computations

So long, we have been moving in the abstract domain, discussing computer programs and their ability (or inability) to express self- reference and self-modifications, and we discussed very general causal mechanisms that acted on essentially undefined primitives. Now we change the domain while keeping the essential features of the discussion. From now on we will speak about biological systems, or, more precisely, about biochemical reaction systems.

It is natural to ask, of course, in what sense can such a consideration help us to understand, ultimately, cognitive functions -- it seems that we are getting farther and farther from the initial goal. However, there is a much studied and deep analogy between computations and biological processes. Not only is it the case that connectionism and other forms of learning theory have greatly benefited from biological metaphors (e.g. in computer science they are now talking about "Parallelism from Nature"), there is also a more direct gateway between the two phenomenal domains. Authors like Bennett and Landauer [1985], Paton [1994], Fontana and Buss [1993], or the entire A-life movement that concentrates on such modelling, have elaborated many details of the transfer. For example, abstract biochemical systems can accommodate Universal Turing Machines, according to the paper-and-pencil proof of Bennett and Landauer [1985]. Or, molecules can be identified with rewriting operators, and molecular reactions conceived as formula substitutions of a formal system. There exist general purpose simulation environments that use this parallel in detail, such as the SPL system developed by us together with M. Vargyas [Kampis and Vargyas 1994]). In particular, then, molecular production systems can be modeled as instances of component-systems. It is this relationship that we elaborate now.

XI. A Biological Mechanism: Shifting Reading Frames

Analyzed in [Kampis 1991b, Kampis 1992, Kampis 1993], we present a molecular example for the biological self-determination (or construction) of information. The example is quiteuniversal in the sense that it can also be used for structure/function studies, or in biological information theory. Here we will restrict ourselves to but one aspect, that of definability.

First, the example. Certain viruses such as the one called %X174 use overlapping codes to represent their genetic information content. That is, in them the same piece of DNA can code for more than one structural proteins. Which of these proteins is produced, depends on how the given piece of DNA is transcribed to mRNA. This transcription, in turn, is controlled biochemically, and, according to the current needs of the viral reproduction process, one of the corresponding pathways will be activated. In this way, the virus (or, more precisely, the cell infected by the virus and taken over by it) can control the information content of one of its molecules. Through this control, the entire definition of the molecule, and that of the whole process using it, can be manipulated. A list of further biological examples that follow a similar pattern is given in [Kampis 1994]; not only DNA but also other molecules or entire organs, even organisms can become subjects of similar "environmental tinkering". The Nobel Laureate F.Jacob has studied many of these mechanisms and their relevance in evolution theory [1981].

What makes this example so significant is the fact that it offers a relational mechanism that transforms production rules by means of their context. This can be generalized far beyond the simple two-protein system, as the same procedure that allowed for a single change of genetic expression (the choice of the starting point of transcription, in this case) can be applied repeatedly, producing an unbounded variety of possible execution routes, each of which can be activated in the presence of a suitable control molecule. In other words, we can never know how many different expressions of a given piece of "genetic material" exist.

By this logic, it is easy to see now that in a component-system any two molecule (or, expressed abstractly, any two elements of the component-system) can have a unique effect on determining what further molecules will be produced. How many things can be done by such a molecule, that only depends on how many different environments exist. This produces a potentially endless variety of causal "rules" for the system, since by this mechanism the newly produced components' interaction with the old components can again amend those things the old components do, and so on, ad infinitum; there is a potentially infinite "depth" of the layers that come into light when evoked by newer and newer contexts, as the production process unfolds.

Somewhat more elegantly, now, we can reconstruct this self-redefinition mechanism with the aid of a concept we introduced in [Kampis 1991b]. Let us go back to the genetic example to fix things, and let us call the "window" of interactions for the information readout a reading frame. This concept is neutral enough, so that it can be equally applicable to any other molecular example, to component-systems, and to very abstract situations such as the information consumption of algorithms, or, for the simplicity of presentation, to Turing Machines. Thereby we obtain a possible tool for discussing the fine structure of the differences between algorithmic definitions and self-modifying systems.

In the Turing Machine case, the reading frame consists of that encoding that connects the read/write head with the machine tape where the information is stored. In the simplest case, this encoding can be formulated as an identity map, which says that the 0-s of the tape will correspond to 0-s of the machine, and the 1-s to the 1-s. The case gets a little more complicated when we start to consider information storage methods other than visual ones and noughts on the tape -- for instance, color codes or elementary magnetized domains.

In any case, what we immediately find to characterize every algorithm is a fixedinterpretation, and, ultimately, a constant reading frame in the Turing Machine that executes the algorithm. We have to realize that the reading frame belongs to the design of the computer and not to the objects it can manipulate, and consequently, that this frame cannot change: again, the same separation of design and operation, or hardware and software, as familiar to us from the earlier discussion.

In the genetic machinery, the role of the "tape" is played by the genome and that of the read/write head by the complex biochemical route connecting the genome to the ribosome, place of the genetic translation. The reading frame, then, is the current expressibility of the genes in terms of their structural products.

The changing transcription method in this case, or, if we talk more liberally about abstract components, the corresponding contextually defined production rules correspond to changing or shifting reading frames. If we can agree that such a contextual element is never finitely definable, because it just slips out of hand, then we end up with a picture of systems that can alter their definitions without allowing us to formulate the rules that govern this growth; in other words, we have an effectively constructed example for a process that leads to self-modification and, through that, according to our earlier train of thought, to causally generated self-reference.

An algorithmically minded person could think at this point of various remedies that would reduce these shifting systems to nonshifting ones. Among these medicines, we will certainly hear of large collections of composite reading frames installed on Turing Machines, in order to grasp the complexity of a shifting-frame based component system. And of course, in line with the previously mentioned most popular form of the Church-Turing Hypothesis, "If you can define it, we can simulate it", whenever we name one new reading frame to which our system has switched, somebody can always come up with a super-Turing-Machine with even more multiple frames so that it can simulate even this switching, and so on. But what cannot be remedied in whatever way is the fundamentally deep difference between a bounded and an unbounded set of reading frames, where the first applies to algorithms, and the second to self-modifying systems, for it is clear, that any fixed set of frames can be always extended by adding a new one, or, in the molecular domain, by adding one more reaction -- and then, everything is mixed up again.

XII. Semantically Closed Systems

To complete the plan we set for ourselves at the beginning of this paper, we have to return to authentically cognitive themes, such as the generation of meaning. Now what is exactly understood by the latter is a question that goes beyond the limits of this writing, nevertheless it is clear how the problem of meaning became popular recently, and that was by J. Searle's Chinese Room argument [1984, 1992].

The argument says that a performance, such as, for example, the translation from English to Chinese, can be achieved by fundamentally different means. There is the human way of it, and there is the machine way of it. More specifically, it says that a translation (or the execution of any other "intelligent" task) is possible without any understanding, entirely on the basis of formal execution manuals that relate non-interpreted typographical symbols to each other; and further, that machine intelligence is bound to this sort of execution, hence it is unrelated to human intelligence, which is not.

The first part of the argument is certainly solid. Indeed every symbolic operation, andtherefore anything computers can do, whether working on formal logical problems or executing connectionist algorithms, can in fact be carried out by entirely syntactic operations where no meaning claims can be done -- a situation known in computer science since Turing's universal simulation result and in philosophy since the Wittgenstein-Russell debate. So far, so good, can we say, for our goal here is not to discuss the Chinese Room any further, but to use one part of it that we have just singled out, and to tie it to our suggestions.

The concept of reading frame lends itself to a comparison with the notion of interpretation of a symbolic system. Properties of symbolic systems can now be reformulated using the physical analog of reading frames. We know, for example, that syntactical systems have fixed semantic interpretations (and hence they have no "meaning" at all, since that interpretation can itself be made part of a syntax). Obviously, this corresponds to the case of a pre-defined reading frame which is initially (that is, "externally") provided for a system, that is just more of the same we have seen already. If we revert the sentence, we obtain that permanent reading frames yield semantically uninteresting systems, subject to the Chinese Room problem.

However, and that may be the gain of all the work we have done, a self-modifying system associated with the presence of shifting reading frames relates, ultimately, to the generation of new meanings, insofar as reading frames can define semantic relations.

If we rethink now the concept of self-modifying system in these loosely conceived semantic terms, we should replace their executions with semantic relations, or meanings. Then we arrive at a "holistic" picture of semantics where the meaning of every component is intelligible only with respect to the system that encompasses it, and the same system is, in turn, a product of the previous changes and productions, determined by the components' "meanings". That results in a heterarchy or entangledness between the system and its components -- in other words, in a certain kind of closure.

XIII. Conclusions

With the last suggested relationship, we have achieved two distinct goals. First we can conclude the train of thought that started with riddles of self-reference and self-modification, the outcome being the characterization of systems with explicit semantic modifications (similar to the ones introduced by H. Pattee [1973], or to P. Cariani's "semantic adaptation" [1989]); second, we succeeded to relate this idea, which is far too specific in itself, to problems of modelling and the philosophy of mind. The core of this was a suggestion of causally realizable circularities that go one step beyond ordinary computations and its perplexing paradoxes.

Let me finally mention a speculative idea to indicate where we can possibly get from this point. An important concept that relates to the above outlined problems of semantics is S. Harnad's "Symbol Grounding Problem" [1990]. It expresses a concern with the origin of semantic relations, a question to which our suggestions may also contribute in some form. It may be a very long way to go from what we have presented now to the point where internally generated semantic relations can be modelled with a self-modifying system, but the very idea is there: to offer an autonomous or dynamic symbol grounding of internal meanings -- perhaps a construction of meanings in the Fregean sense of "Sinn".


This paper was written during the author's stay at the Department of Theoretical Chemistry, University of Tùbingen, Germany. The author wishes to thank Prof. O.E. Ròssler for his hospitality and friendship. The work was partially supported by a German DFG research grant ("New Ideas in Complexity") and two Hungarian research grants (OTKA #2314 and OTKA #T6428). The author would like to thank the grant-giving organizations for this support.


         Bartlett, S.J. and Suber, P. 1987: Self-Reference: Reflections on Reflexivity, M. Nijhoff, Amsterdam.

         Beeson, M.J. 1985: Foundations of Constructive Mathematics: Metamathematical studies, Springer, New York.

         Bennett, C.H. and Landauer, R. 1985: "The Fundamental Physical Limits of Computation", Sci.American 253, July pp. 38-46.

         Callebaut, W. and Pinxten, R. (ed.) 1987: Evolutionary Epistemology: A Multiparadigm Program with a Complete Evolutionary Epistemology Bibliography, Reidel, Boston.

         Cariani, P. 1989: On the Design of Devices with Emergent Semantic Functions, Ph.D. dissertation, Dept. of Systems Sci., SUNY at Binghamton.

         Clark, A 1989: Microcognition: Philosophy, Cognitive Science, and Parallel Distributed Processing, MIT Press, Cambridge, Mass.

         Conrad, M. 1983: Adaptability. The Significance of Variability from Molecule to Ecosystem, Plenum, New York.

         Csányi, V. 1989: Evolutionary Systems and Society: A General Theory of Life, Mind, and Culture, Duke University Press, Durham.

         Dawkins, R. 1976: The Selfish Gene, Oxford University Press, Oxford.

         Edelman, G.M. 1987: Neural Darwinism: The Theory of Neuronal Group Selection, Basic Books, New York.

         Fontana, W. and Buss, L. 1993: "The Arrival of the Fittest", paper presented at the 3rd Artificial Life Conference, Santa Fe, NM.

         Harnad, S. 1982: "Neoconstructivism: A Unifying Theme for the Cognitive Sciences", in: Language, Mind and Brain (T. Simon and R. Scholes, eds.), Erlbaum, Hillsdale, pp 1 - 11.

         Harnad, S. 1990: "The Symbol Grounding Problem". PhysicaD 42, 335-346.

         Hart, W.D. 1987: "Causation and Self-Reference", in: Bartlett and Suber 1987, pp. 179-189.

         Hofstadter, D. 1979: Gòdel, Escher, Bach, Basic Books, New York.

         Hofstadter, D.R. 1985: Metamagical Themas: Questing for the Essence of Mind and Pattern, Basic Books, New York.

         Holland, J.H. 1975: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor.

         Jacob, F. 1981: Le jeu des possibles, Fayard, Paris.

         Kampis, G. 1988: "On the Modelling Relation", Systems Research 5, 131-144.

         Kampis, G. 1989: "Two Approaches for Defining 'Systems'", Int.J.General Systems 15, 75-80.

         Kampis, G. 1991: Self-Modifying Systems: A New Framework for Dynamics, Information, and Complexity, Pergamon, Oxford-New York, pp 543+xix.

         Kampis, G. 1991: "Process, Information Theory, and the Creation of Systems", in: Nature and the Evolution of Information Processing (ed. K. Haefner), Springer, Berlin, pp. 83-103.

         Kampis, G. 1992: "Constructive Systems Theory: Process and Model", in: Cybernetics and Systems '92 (ed. Trappl, R.), World Scientific, Singapore, pp. 11-17.

         Kampis, G. and Vargyas, M. 1994: "Evolving Component-Systems and Other Alife Simulations in the SPL System", paper submitted to the 4th Artificial Life Conference, MIT, Cambridge, Mass.

         Lumdsen, C.J. and Wilosn, E.O. 1981: Genes, Mind, and Culture: The Coevolutionary Process, Harvard University Press, Cambridge, Mass.

         Lòfgren, L. 1968: "An Axiomatic Explanation of Complete Self-Reproduction", Bull. Math. Biophys. 30, 415-425.

         Maturana, H.R. and Varela, F.J. 1980: Autopoiesis and Cognition, D. Reidel, Dordrecht.

         Maturana, H.R. and Varela, F.J. 1987: The Tree of Knowledge: The Biological Roots of Human Understanding, New Science Library, Boston.

         Neumann, J. von 1966: The Theory of Self-Reproducing Automata (ed. Burks, A.W.), Univ. of Illinois Press, Chicago.

         Paton, R. 1994: Computing with Biological Metaphors, Chapman and Hall, London, in press.

         Pattee, H.H. 1973: "Unsolved Problems of Hierarchy Theory", in: Hierarchy Theory (ed. Pattee, H.H.), Braziller, New York.

         Rosen, R. 1959: "On a Logical Paradox Implicit in the Notion of a Self-Reproducing Automaton", Bull.Math.Biophys. 21, 387-394.

         Ròssler, O.E. 1984: "Deductive Prebiology", in: Molecular Evolution and Protobiology (ed. Matsuno, K., Dose, K., Harada, K, and Rohlfing, D.L.), Plenum, New York, pp. 375-385.

         Searle, J.R. 1984: Minds, Brains, and Science, Harvard University Press, Cambridge.

         Searle, J.R.1992: The Rediscovery of the Mind, MIT Press, Cambridge.

         Suber, P. 1990: The Paradox of Self-amendment: a Study of Logic, Law, Omnipotence, and Change, P. Lang, New York.

         Spencer-Brown, G. 1969: Laws of Form, Allen and Unwin, London.

         Stenseth, N.C. and Maynard Smith, J. 1984: "Coevolution in Ecosystems: Red Queen Evolution or Stasis?", Evolution 38, 870-880.

         Van Valen, L. 1983: "A New Evolutionary Law", Evolutionary Theory 1, 1-30.

         Varela, F.J. 1974: "A Calculus for Self-Reference", Int.J.General Systems 2, 5-24.

         Varela, F.J., Thompson, E. and Rosch, E. 1991: The Embodied Mind: Cognitive Science and Human Experience, MIT Press, Cambridge, Mass.

         Watzlawick, P. (ed.) 1984: The Invented Reality: How Do We Know What We Believe We Know?: Contributions to Constructivism, Norton, New York.

Converted by Andrew Scriven