Computability in Developing Systems

Written: 27 June 1996
Revised: 19 December 1996

Abstract Human activity and cognition cannot be modelled without accounting for development. The principal directions of incorporating development in production systems, abstract automata and practical problem solvers are discussed in this paper. A few generalisations of a "physical" definition of Turing machine are described, including second-order and hierarchical models. Considering the modification of the machine's operation set and environment requires a new mathematics, which would incorporate self-modifying (reflective) axiomatic systems. Schemes of explicit and implicit definitions are discussed, and the necessity of a conceptual closure of hierarchical development in science is stressed. Universal features of development are described, distinguishing structural, systemic and hierarchical development. These features are indispensable to insure human-like behaviour in ensembles of Turing machines.

Of course, the structure of the equations may be more complex, the last three equations being functional rather than ordinary differential equations. The internal state of M1 may include the kinematics of M2, the equation of motion being essentially nonlinear (recursive). Higher-order Turing machines can be constructed in the same way.

The machine's ability to change the external world and itself is related to the process of abstraction. The traditional definition of Turing machine implies explicit enumeration of operations from R, which is inappropriate for infinite sets X, S and C. Thus, to specify increment by one as an elementary operation on S = {0,1,2,...}, one has to make R infinite; however, one could introduce the abstract operation INC instead, transforming every s Î S into s+1, which would mean only one operation instead of the infinity of similar acts. Evidently, abstraction is mostly due to machine's "self-observation" (reflectivity), a scheme derived from a number of special cases (Pospelov 1986). Since abstract operations can be generated from any finite number of samples, there may be cases when the result of operation is undefined, because there are no respective elements in X, S or C. In human behaviour, there are two basic reactions to such a situation: the formal result may be treated as ideal, and added to the collection of internal states C, or it may be implemented in external activity producing new elements of S or X (intensive or extensive development of the world). In particular, external activity may become mediated by a series of internal transformations.

4. Development in formal systems

Formal description of developing Turing machines may require new mathematical methods, since the allowance for self-modification leads to apparent contradictions violating the identity of the subject, the axioms being updated during the discourse (Pospelov 1986). Seeking for more rigor, one might suggest that mathematics do not deal with development at all, and that mathematical models refer to a single level of development and work inside it. Any axiom modification will be hence considered as switching to another model that should be treated separately. However, this attitude does not help much since the very specification of the working level implies distinguishing it from the other levels, while considering any other levels would inevitably violate the "purity" of theory. For instance, the mathematical idea of an operation assumes its complete specification: one should exactly define how the operation is performed, and what would be its result for any given "arguments". This cannot be done in real life, where operations are never defined completely. As a rule, the introduction of an operation involves some informal descriptions, which complement the explicit and implicit definitions.

Explicit definition constructs a new operation as a combination of already existing operations, the rules of composition forming a higher level of operation. Several levels may be specified, but the highest level can never be introduced explicitly. Some mathematical theories merge these levels into a single "universe" with rather exotic properties (higher-order logic, Henkin 1950; nonstandard analysis, Davis 1977); hierarchical representation might make the problems more tractable.

A generalisation of the notion of Turing machine may include the rules of explicit definition in the operation set, which can thus be made extendible. However, explicit construction of operations does not give much freedom for development, since one might consider complete (closed) operation sets only, where any composition of operations gives an operation from the same set. However, the transitory processes preceding the formation of such complete sets may be of interest under special circumstances, when the rate of the machine's operation is much higher than the rate of completing the operation set.

In the implicit definition, a new operation is defined "by analogy", using the constructions like: "Act in the same manner as when transforming x into y." The actual ways of performance stay outside the theory, admitted they could be somehow discovered in practice; in other words, implicit definitions are to be further explicitly reduced to some other primary operations, which will have to be unfolded in their turn. Logically, an implicit definition of operation is a tautology: operation g transforming input x_in into output x_out is just the ordered pair < x_in, x_out >. Any set of such pairs may be called a "generic" operation, relation g: X ® X. However, this approach is not applicable to infinite sets, or analogue machines, and the traditional theory of computability generally sticks to finite alphabets and operation sets. Still, implicit definitions model an important feature of real behaviour: it is quite common in animals that reflex formation occurs via a momentary circuit closure, in a single try; even if thus acquired behaviour proves to be inadequate, animals do not completely dismiss the first impression, other reflexes just moderating its action.

Implicit definitions are most popular in mathematics, though they often lead to methodological problems. The definition of a set by its characteristic property is a typical example: "Let A be a set of all a that possess the property p." A cortege of n elements referred to as < x₁, x₂, ..., x_n > is one more instance of implicit definition. Such constructions violate the traditional deductive scheme, but mathematics can never get rid of them. Inductive definitions are employed for more rigor, but the induction rule itself contains a logical loop, since the presumed n-th step of induction is an implicit reference too. So, to proceed with explicit constructions, one has to postulate some notions and rules appealing to "intuitive" abilities presumably shared by other people. Therefore, mathematical reasoning does not produce any "truths", and mathematical deduction is a method of elaborating a hypothesis rather than validating it.

Generally, with the allowance for implicit definitions, the process of completing the operation set via explicit combination of primary operations cannot be considered as transient, since the addition of a new implicit definition (or a new abstraction) will start the process of accumulating explicit constructions employing it. This process may be not finished to the moment when another primary operation appears, the state of the machine thus becoming always "transitory". Of course, one may study adiabatic abstraction, when the operation set becomes complete before every new implicit definition. Such smooth development would model some real cases, though it cannot cope with the revolutionary changes in human knowledge.

Though development through explicit construction is more important in the machines able of implicit definition, it still remains just quantitative, lacking "true" novelty. On the other side, the arbitrariness of implicit definition can only be tolerated to a definite extent, and one would necessarily try to investigate the mechanisms of implicit definition too. There is a danger of an infinite succession of the "levels of implication", when every newly discovered mechanism initiates the search for "deeper" mechanisms underlying it. Modern physics may be an example, with molecules consisting of atoms, atoms constructed of nuclei and electrons, nuclei containing hadrons and mesons, which become reduced to quarks and gluons, and some physicists suggest that quarks might be "made" of still "simpler" particles (or fields).

To avoid this "bad" infinity one might to arrange a "feed-back" from explicit to implicit definitions, so that accumulation of new combinations would result in a qualitative "jump" to a new kind of operation. This effect is quite common in human activity. Usually, single act is not enough to become aware of it as a representative of a new mode of action. It is its reproduction in different circumstances that would stress the universality. What looks like "instantaneous" solution, "insight", is rather people's communication folded in mental activity.

In general, implicit definitions admit many possible explications, since the transition from x to y can be performed in many different ways. This fact is quite obvious with mathematical functions defined as the sets of pairs < x, f(x) >: there are many functions that assume value y in the point x. In physics, such situations often arise in quantum theory, when a Hermitian operator is to be continued from the "on-shell" to the "off-shell" (unphysical) energies. As a rule, the selection of the "true" branch requires considering asymptotic conditions imposed by the macroscopic measurement procedure.

An implicit definition can be treated as a void position in a formal scheme. Thus, if there is an n-place formula assumed to be valid in all the cases under consideration, every one of n positions can be empty, which would define the entity completing the formula when substituted to the void position. For example, the dyad (a,b) assumes two forms of implicit definition, (?,b) and (a,?); the triad (a,b,c) leads to implicit definitions of the form (?,b,c), (a,?,c) and (a,b,?), etc. In a sense, implicit definition is opposite to the statement of existence: instead of "There is a such that (a,b)", one says: "Let a be such that (a,b)". The well-known examples come from the school mathematics: -x is such number that x+(-x) = 0, i is such number that i² = -1, etc. More academic definitions of these entities just explicate the implicit definitions introducing more implications elsewhere. However, the void-position form of implicit definition is transparent and convenient for implementation in artificial problem solvers.

Of course, the above schemes do not exhaust the possible forms of implicit definition. Two more classes of importance are folding and unfolding schemes. Thus, a new entity can be introduced as a "shortcut" for a n-place formula: for example, let y stand for (a,b). In programming, such folding may be illustrated by macro definitions, or inline functions. However, inline functions may become out-of-line in some circumstances (for example, in the debugging environment), or even grow into separate program modules, as the whole project develops. The opposite case of unfolding scheme expands an element of a formula into a sub-expression. For example, in the triad (a,b,c) the link b can be represented as (b(a),b',b(c)), distinguishing the sides of b relating to its connections with a and c, as well as the way b' of linking b(a) to b(c) "inside" b. In particular, designation and substitution are special cases of folding/unfolding which are the basic operations of mathematical reasoning, though these operations are never explicitly defined in mathematics.

In modern mathematics, some classes of problems become substituted with alternative "linguistic" formulations, when one does not prove a theorem, but rather proves that the proof can be formulated using a specially designed formal language. Thus, the formulation of Gödel theorems by Mendelson 1964 and Cutland 1980 replaces arithmetic with one of its formal descriptions, and thus the result obtained is the incompleteness of this type of description, rather than of arithmetic itself. Another example is provided by nonstandard analysis, where all the theorems concern a formal description of the universe introduced rather than this universe proper (Davis 1977). This is a "second-order" tendency in mathematics, since the focus of investigation shifts from the observable world to the observer.

However, observer belongs to the same world, and one can notice that the transition from the "first-order" to "second-order" science may be treated as a change in the subject producing another (interdisciplinary) science, which is as "positive" as the original, "first-order" research. The "second-order" version of this new science can be built in its turn — and so on to infinity. An infinite sequence of levels can thus be unfolded starting from any science, either "positive" or not. Accordingly, there is a hierarchy of computability (solvability, verification etc.), since the formalism of any level may be found incomplete judging from the higher level only, which might be just an evidence of its own incompleteness. Inversely, the very existence of the higher level assumes that some problems cannot be resolved at the lower levels, which means that they are essentially incomplete.

From this viewpoint, it seems quite natural that, in seeking for the foundations of mathematics, any attempt to build a rigorous theory leads to the construction of many alternative theories, which are as acceptable, or as arbitrary. The commonly known history of non-Euclidean geometry finds its continuation in the diversity of the definitions of fractal dimension (Fractals 1985), alternative set theories (Zadeh 1973, Vopenka 1979), the categorial formulation of mathematics (Goldblatt 1979).

The infinite chain of incomplete theories can be folded in the abstraction of a new science describing the very method of generating the higher levels. Such science would be completely characterised by any two adjacent levels, thus being a hierarchical synthesis of them. On the other side, its distinction from the "first-order" approach would be completely defined by the "second-order" theory, while the "first-order" science would define the transition to the synthetic level from the "second-order" approach. No infinite regression occurs in this way.

An analogous triad of the levels of activity is well known in general psychology (Leontiev 1978); recently, Leontiev's theory has been revised within hierarchical approach and applied to aesthetic perception (Ivanov 1994, 1995). The conceptual cycle described would provide a kind of basic model for hierarchical mathematics, like the heating-cooling cycle of the ideal heat machine was a germ of modern thermodynamics. The logic of this article demands that the same triadic organisation should be inherent in Turing machines if they are expected to exhibit human-like behaviour.

5. Phenomenology of Development

A detailed investigation of developing Turing machines is yet to be performed. Still, some general directions of research and features to describe may be predicted beforehand. In this concluding section, I will give a brief summary of the hierarchical approach to the problem.

Changing environment

Individual development is only possible when an individual is placed in a developing environment. If the world W remains qualitatively the same, one may only speak about transitory development, which is bound to stop when all of the world becomes "comprehended" by the machine. The assumption of infinite W does not alter this conclusion, as far as this infinity is merely quantitative. Thus, one cannot enumerate all the integer numbers in a finite time — still, their "idea" is readily comprehended in the operation of enumeration. Actually, one does not need to further count integers after this basic operation has been formed.

Three ways of the involvement of machine's development in the development of the world can be considered:

1. Syncretic development. Everything changes, and the machine changes as a part of the world.

2. Analytical development. The machine changes its environment which demands for the new ways of adaptation.

3. Synthetic development. Each action implies changes in both the environment and the organisation of the machine.

It may be readily seen that the first way corresponds to the level of physical existence, while the second and third levels could be associated with biological and conscious development respectively. Of course, the latter case attracts much more interest since it has to do with modelling human cognition.

Levels of coherence

As it has been noted for higher-order Turing machines, the basic mechanism of development is the synthesis of different objects into a kind of integrity. Such synthesis may proceed in different ways:

1. Structural development. New elements or new relations between elements are added. Every element is principally equivalent to any other element, and all the relation are of generally the same kind.

2. Systemic development. The components of the compound are functionally different. Thus, systemic synthesis of two independent structures may assume that one of them becomes "input" while the other becomes "output", the relation between them within the system differing from the uniformity of elements and relations within structure.

3. Hierarchical development. This is the synthesis of structural and systemic development assuming that systemic development is reflected in the structures, and structural development leads to the distinctions in functionality. Here, the integration of several objects into the whole means that they become the different levels of hierarchy, so that the structures and behaviour at the lower levels depends on the "control parameters" prescribed by the higher levels.

Actually, development cycles through these stages, structures and systems becoming hierarchical. The hierarchical structure differs from the "plain" structure in that the elements become grouped into several distinct classes, so that the relations between the classes are distinguished from the relations inside each class. Naturally, the classes may be further grouped into "higher-level" categories, forming a multilevel hierarchical structure. Hierarchical systems may be described in much the same way, their input and output structures becoming hierarchical.

Reflectivity

To insure that the synthesis of a few machines be more "powerful" than every one of the original machines, the machines to be combined should be different enough, possessing complementary sets of operations. That is, different machines should be able to compare themselves, so that any one of them could borrow lacking operations from its neighbours. In particular, a machine should be able to analyse its own operation set.

Such an ability implies advanced communication between the machines. Of course, the first premise is interaction. However, it is not enough. To serve for development, interaction must be reflexive, that is, the behaviour of one machine must influence its state through the feed-back from another machine. To make development intelligent, one more condition must be satisfied: the feed-back must involve the internal image of the machines in any one of them, and the internal image of their interaction. It should not be mere dependence on the environmental changes caused by the agent, in which case only "biological" development is possible.

Two implications are then to be considered. First, the comparison of different machines should be performed on a common basis, which is provided by cultural integrity in the case of human activity. In other words, human-like development implies the existence of a "collective" level uniting many individual machines in a kind of society. The interaction of any two individuals (and individual reflection in particular) is therefore never direct, but rather mediated by social organisation. It means that either interaction of the machine with the world should be non-local, or (which is more likely) the immediate environment of the machine is "subjectively" perceived as the topmost level of a hierarchy, any physical event being just an indication of a global process.

Furthermore, such socially mediated reflection becomes interiorised into a special operation of relating different individuals to each other. That is, the individual operation set R should contain the operations of reflection, along with the traditional "productive" operations and the operations of self-modification discussed above. Hence, the internal hierarchy of the machine tends to reflect the hierarchy of the world. In particular, every act of communication involves an internal image of the partner, actual behaviour being dependent on many folded communications with this internal model.

References

Chang, Ch., and Lee, R. (1973) Symbolic Logic and Mechanical Theorem Prooving. (New York, San Francisco, London: Academic)

Cutland, N. (1980) Computability: An introduction to recursive function theory. (Cambridge: Cambridge Univ.)

Davis, M. (1977) Applied nonstandard analysis. (New York: Wiley)

Efimov, E.I. (1982) Intellectual Problem Solvers. (Moscow: Nauka)

Engeler, E. (1983) Metamathematik der Elementarmathematik. (Berlin: Springer)

Foerster, H. von. (1981) Observing Systems. Selected Papers of Heinz von Foerster (Seaside, CA: Intersystems)

Fractals in Physics. Proc. of the VI Int. Symp. on Fractals in Physics (Trieste, Italy, 1985) (L.Pietronero and E.Tosatti, eds.) (Amsterdam, Oxford, New York, Toronto: North Holland, 1986)

Goldblatt, R. (1979) Topoi: The categorial analysis of logic. (Amsterdam, New York, Oxford: North Holland)

Gorbatov, V.A. (1986) Foundations of Discrete Mathematics. (Moscow: Vysshaya Shkola)

Henkin, L. (1950) J. Symbolic Logic, 15, 81

Ivanov, P.B. (1994) Leonardo, 5, 417

Ivanov, P.B. (1995) Leonardo Music Journal, 5, 49

Leontiev, A.N. (1978) Activity, Consciousness and Personality. (Englewood Cliffs, NJ: Prentice Hall)

Mendelson, E. (1964) Introduction to mathematical logic. (Princeton, NJ: D. van Nostrand)

Mulhauser, G.R. (1994) Mind Out of Matter: Topics in the Physical Foundations of Consciousness and Cognition. On-line: International Philosophy Preprint Exchange, http://cogsci.l.chiba-u.ac.jp/IPPE/Phil_of_Mind/Mulhauser.Mind_Out_of_Matter/

Penrose, R. (1994) Shadows of the Mind. (New York: Oxford University)

Pospelov, D.A. (1986) Situation-Driven Control: Theory and Practice. (Moscow: Nauka)

Stapp, H.P. (1995) Psyche, 2; On-line: http://psyche.cs.monash.edu.au/volume2-1/psyche-95-2-05-qm_stapp-1-stapp.html

Vopenka, P. (1979) Mathematics in the alternative set theory. (Leipzig: Teubner)

Zadeh, L.A. (1973) The concept of a linguistic variable and its application to approximate reasoning. (New York: Elsevier)