Computability in Developing Systems
Pavel B. Ivanov
Troitsk Institute for Innovation and Fusion Research (TRINITI)
Email: unism@narod.ru
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 secondorder and
hierarchical models. Considering the modification of the machine's
operation set and environment requires a new mathematics, which would
incorporate selfmodifying (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 humanlike behaviour in ensembles of Turing machines.

1. Introduction
Science of the XX century has been marked with intense interest to the
problem of including the observer into the description of objective
phenomena. It was argued that, in some cases, the act of observation
would interfere with the process observed and the correct description
of reality should account for such perturbations. The boundary between
natural phenomena and their scientific description became vague, and
this seemed to essentially limit human cognition. The famous Gödel
theorem added to the idea of inherent logical insufficiency of the human
mind, inspiring numerous discussions and interpretations. Some
theoreticians still apply to incompleteness of formal systems in their
metaphysical discourse (Penrose 1994, Stapp
1995). However, most scientists do not share these fears and
continue their work fully convinced that science is able to find out
everything people need in their life and activity. They understand that
scientific methods cannot be reduced to formal systems, and even the
development of mathematics follows the laws that have little in common
with mechanical deduction.
Still, the ways science describes the world could be made the subject
of a particular investigation, and nothing prohibits the formation of
new sciences studying it. Actually, every science is aware of the
limits of its applicability; moreover, the attempts to more exactly
specify the applicability conditions often become a source of new
discoveries. Such methodological study may be more obvious in sciences
whose subject is originally related to the description of the observer.
Thus, mathematicians intensely explore the foundations of mathematics,
this activity being sometimes called metamathematics (Engeler
1983). The analogous branch in cybernetics is called
"secondorder" cybernetics (Foerster 1981).
Also, many psychological works include an analysis of possible
observer's involvement.
Mathematical theory of computability is a typical example of
"secondorder" approach. Generally, the subject of the theory
is the operator's ability to achieve some goal that can be specified
in a formal way, which assumes the description of both operation and
goal specification. However, traditional models usually deal with
formal systems with a predefined operation set, so that their
behaviour basically remains the same. This does not exactly match
our conceptions of human creativity, which imply the possibility of
inventing something "new", not contained in the raw
materials or instrumental skills. The most prominent feature of
human activity is that it may change any rules, adopting them only
temporarily, at will. This leads to the necessity of considering
development, which may drastically change the very notion of
computability. As the operation set expands, new goals become
attainable, and a higherorder theory has to describe the rules
governing such expansion.
The description of development may require new formal methods, since
traditional logic demands the identity of the subject in any discourse,
while development seems to repeatedly violate this identity, so that
the basic axioms may become updated in the course of deduction. This
may sound absurd — still, this holds for the development of
mathematics too, which necessarily combines formal and informal elements.
To construct the models of developing problem solvers, one has to
specify the properties of such "machines" related to
development. These general definitions are then to be implemented in
the formal descriptions. Thus, different kinds of development can be
distinguished, including structural, systemic and hierarchical levels.
It can be argued that hierarchical organisation is necessary for
efficient operation in complex environment (Efimov 1982),
and one comes to formulating the general principles of hierarchy.
One of the most important features of hierarchical development is
the interiorisation of any external activity through socialisation,
as well as actualisation of internal processes, creativity.
In this article, I assess the current state of computability studies
from the developmental viewpoint. I do not intend to derive any formal
results, but rather indicate the search directions and explicate the
ideas commonly implied. Section 2 summarises the
traditional approach to computability on the example of the Turing
machine, in a "physical" formulation more suited for further
generalisation. Some directions of generalisation are discussed in
Section 3, including multidimensional, nonlocal and
analogue Turing machines. Secondorder Turing machines are suggested
as a more realistic model of human cognition. Developing Turing
machines are considered in that section, with the stress on evolving
environment, productive activity and abstraction. Formal aspects of
development are discussed in Section 4, demonstrating
the interlay of explicit and implicit definitions in both developing
problem solvers and their mathematical descriptions. Implicit
definitions are of primary importance for development, and I suggest
several universal schemes applicable in developing machines. In
conclusion, Section 5 specifies the general features
of development to be implemented in the future models of human activity
and cognition.
2. Traditional computability
Historically, computability problem assumed many forms. The well known
formulations include Turing machines, RAM machines, recursive functions,
lcalculus, Post systems, Markov algorithms
and others (Cutland 1980). The basic fact is that the
lass of "computable" elements is the same in all these
theories. The wellknown Church thesis postulates that any other
theory of discrete computations would give the same computable class.
This seems quite natural, since, in any case, one deals with finite
sequences of operations from a numerable variety. The details of
enumeration are of minor importance for computability.
Adopting Church thesis, one may consider any model of discrete
calculation as a representative of the same general category. I choose
the Turing machine representation, which stresses the idea of operation
directly associated with certain aspects of human activity. To enhance
the analogy, I will define a Turing machine in a "physical"
manner, different from the mathematical formulations proper:
 The "universe" U = W + M.
 The "world" W:
(a) a linearly ordered discrete set of possible locations X = {x} ("configuration space");
(b) a discrete set of possible states S = {s} observable at any location;
 The "machine" M:
(a) a discrete set of possible "internal" states C;
(b) a finite set of possible "operations" R, represented by a relation R:
X×S×C → X×S×C;
 Current state of the universe U:
(a) function s: X → S, the overall state of the world W as a field of local states s(x);
(b) x ∈ X, the location of M;
(c) c ∈ C, the state of M;
 Operation cycle:
(a) the machine's input: < x, s(x), c >;
(b) the choice of operation
r ∈ R: < x, s, c > → < x', s', c' >;
(c) the machine's action:
x → x' = x + dx,
s(x) → s'(x) = s(x) + ds,
c → c' = c + dc;
(d) the new input < x', s'(x'), c' > initiates the next reaction, and so on.
The machine's operation is local: it may only change the
state s of the world W in the point x where
M is currently located. In the classical definition, Turing
machine may move to the neighbouring locations only, so that
x' = either x, or x+1, or
x–1 (that is,
dx = 0, +1, –1).
Evidently, the operation set R may be thought of as a set of corteges
r = < dx, ds, dc >.
Each operation cycle may be associated with the time increment
dt = 1, so that the kinematics of U can
be described by three functions x(t), c(t)
and s(x,t) representing the external movement of
M, the change of its internal state and the modification of the
overall state of W. Virtually, one might consider the sequence
of operations r(t) (the "computation process"),
and the dynamics of Turing machine could then be described by
the equation set
dx/dt = r_{x}(x,s,c; t)
ds/dt = r_{s}(x,s,c; t)
dc/dt = r_{c}(x,s,c; t)
At any moment, dynamics implies choice between the currently admissible
operations ("decision"). This choice may depend on the current
state of U in a more or less definite way. Thus, one can consider
a stochastic Turing machine, with every state
< x, s, c >
assuming a number of admissible operations
< dx, ds, dc >,
which may be chosen with definite probabilities. In the opposite case,
the behaviour of the machine may be entirely causal, so that the
change of the state would be completely defined by the history of
previous interactions.
In this model, computability means the existence of a process
r(t) transforming an initial state of the world
s_{i}(x) into a final state
s_{f}(x). In the process of computation,
M would pass from the state
< x_{i} , c_{i} >
to the state
< x_{f} , c_{f} >,
with c_{f} occasionally supposed to terminate
(or suspend) the machine's operation (Mendelson 1964; Gorbatov 1986).
The latter requirement agrees with the typical usage of a computer,
while modelling humanlike behaviour does not need such a restriction.
Human activity never stops, and any particular state is transitory
in it. Hence, computability is reduced to the existence of a
trajectory passing through two predefined points. Such trajectory
may be not unique; for stochastic Turing machines, one may associate
every allowed trajectory with a nonzero probability (or a probability
amplitude), whereas the selection of a definite trajectory (method
of computation) in causal machines depends on the initial conditions.
There are two major trends in computability studies. One of them
is primarily concerned with the kinematics of operation, investigating
the possibility of constructing an operation set enough to transform
one state of the world W into another. However, practical
applications require efficient procedures, rather than proofs
of principal solvability (Chang&Lee 1973); this
leads to a closer investigation of dynamics. Accordingly, one might
distinguish two kinds of uncomputability: (a) kinematic uncomputability
due to the essential incompleteness of the operation set, and (b)
dynamic uncomputability due to the violation of time restrictions imposed.
However, the traditional theory of computability does not consider
development, since the sets X, S, C and R
always remain the same in the course of computation.
3. Generalised Turing machines
The Turingmachine model of discrete computation can be generalised
in many ways. Some of them may lead to new classes of computable functions.
The first evident generalisation is multidimensionality: locations
x may be vectors, rather than single numbers. Accordingly, the
change in the machine's location would mean that each coordinate is
either increased by one, or diminished by one, or left the same.
It is rather evident that such generalisation would not change the
computable class, as long as spatial points remain numerable.
Also, one can remove the locality restriction, and consider machines
which may:
(a) observe the state of W in the points other than the current location of M;
(b) change the state of W in several points, rather than a single point;
(c) move to a spatial point not adjacent to the current location.
Again, this would not affect computability, as long as the operation set
R remains finite. The allowance for infinite operation sets would
lead to a wider class of computable functions, since such infinity is
implicitly reflective, as will be discussed in the following sections.
Infinite operation sets may provide a structural (static) description
of development; however, such description is insufficient for
higherorder research.
One more generalisation that may extend the computability class is
analogue Turing machines in continuous spacetime. Continuum requires
a different concept of computability, replacing discrete sequences of
events with smooth trajectories. Depending on the model of system
dynamics, they will be either usual trajectories in the configuration
space X accompanied with some "internal" movement
in M, or evolution of virtual intermediate states in the
stochastic (quantum) case, or any combination of these mechanisms.
As the time increment dt tends to zero, kinematic computability
will be associated with the trajectories of finite length, rather
than with finite sequences of acts. As for the ordinary Turing
machines, dynamic computability differs from kinematic computability,
demanding that the trajectory connecting two spatial points should
be passed in a reasonable time; moreover, in the continuous case,
there can be absolute dynamic uncomputability when a
finitelength trajectory requires infinite time to pass due to the
singularity of machine's velocity distribution along the trajectory
depending on the external force fields. Analogue Turing machines
may provide more realistic models of human reasoning, eliminating
many restrictions of discrete models (Mulhauser 1994).
Still, the behaviour of analogue Turing machines remains, in a sense,
predefined. The focus just shifts from discrete orbits in a set
to the topology of a manifold.
One could consider Turing machines in an evolving environment, so
that s(x,t) would change in time due to some
external process beside the machine's operation. The equations of
motion would then be rewritten as
dx/dt = r_{x}(x,s,c; t)
ds/dt = r_{s}(x,s,c; t) + f_{s}(x,s; t)
dc/dt = r_{c}(x,s,c; t) + f_{c}(c; t)

The last of these equations accounts for the spontaneous evolution of
the internal state of M. Such timedependent formalism requires
a revision of the very notion of computability, since the initial and
final states of the world W are no more stationary. Thus,
one might consider uniform computability, adiabatic computability,
computability in average etc. Still, passive evolution is a rather
restricted sort of development lacking essentially human creativity.
Within the Turingmachine model, development would affect either of:
(a) configuration space X;
(b) the set of possible states S;
(c) the set of internal states C;
(d) operation set R.
The possibility of a change in X and S is most important:
it means that M can produce something new that had never existed
in the world W before. This is one of the distinctive features
of specifically human behaviour, and any other changes can be argued
to originate from that "material" productivity. People do
not merely rearrange the world — they replace it with another one,
more suited for their life and activity. The change in C and
R means that M is apt to internal reorganisation, which
would make it another machine, from the traditional viewpoint. In
human behaviour, such internal development may be relatively independent
of external productivity.
Development drastically changes the notion of computability, since
any state of U becomes accessible, as soon as a special
operation is added to the original set. In common words, if something
can be imagined, it can be done. Sooner or later, someone would find
the way to achieve what has been thought of as unachievable. For a
developing Turing machine, there are no uncomputable functions,
and any proofs of unsolvability may only refer to a definite stage
of development.
However, the development of Turing machines should not be considered
as arbitrary. The very ability of breaking the rules may be governed
by some "secondorder" rules. To specify them, one might
follow the traditional line of mathematical development, specifying
minimal generalisation of the traditional Turing model that would
lead to a kind of selfmodification.
There is an evident possibility which implies one additional operation:
if a state of U has proved to be inaccessible from some initial
state using the current set of operations R, the corresponding transition
r = < dx, ds, dc >
may be added to R. However, this generalisation may be not minimal
when movement obeys the "smoothness" restriction:
dx = +1, 0, –1
(with dc linking the "adjacent" states of M only).
In this case, one will have to modify the "expansion rule":
if an uncomputable state is adjacent to a computable state, the
transition to the former from the latter may be added to the operation
set. In general, consideration of such "minimality" will lead
to discussing the reducibility of computational tasks
(Cutland 1980; Efimov 1982;
Gorbatov 1986).
This mechanism is much like space completion in mathematics, when every
fundamental sequence is identified with a point of the space, thus being
made convergent. The key feature of such development is that M
should be able to somehow "know" about an inaccessible point
before introducing a new operation making it accessible. In other
words, the internal state of the machine should reflect the machine's
operation, including the formation of computational tasks. Hence,
Turing machine must be hierarchical, the higher level forming
the "goals" for the lowerlevel computations. One might
consider such machine as a combination of two different machines:
one machine is to perform "calculations", while another is
to set up computational tasks (Efimov 1982). So,
the principal mechanism of development is integration of functionally
different machines moderating each other's operation. From the
viewpoint of every one of these united machines, a part of the
machine's environment is interiorised, forming a new level of
operation.
The definition of such "secondorder" Turing machine includes:
 The world W = < X, S, s: X → S >,
 Level1 machine M1 operating on W,
 Level2 machine M2 operating on the "internal world" of M1: W1 = < S, C, R >.
The equations of motion for the twolevel machine could be written as
dx/dt = r_{1x}(x,s,c; t)
ds/dt = r_{1s}(x,s,c; t)
dc/dt = r_{1c}(x,s,c; t)
dr_{1x}/dt = r_{2x}(s,c,r_{1}; t)
dr_{1s}/dt = r_{2s}(s,c,r_{1}; t)
dr_{1c}/dt = r_{2c}(s,c,r_{1}; t)

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).
Higherorder 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 "selfobservation" (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 selfmodification 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 (higherorder 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_{1}, x_{2}, ..., 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 nth 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
"feedback" 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 "onshell"
to the "offshell" (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 nplace 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
wellknown examples come from the school mathematics:
–x is such number that
x+(–x) = 0,
i is such number that i^{2} = 1, etc. More academic definitions of these
entities just explicate the implicit definitions introducing more
implications elsewhere. However, the voidposition 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 nplace 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 outofline 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
subexpression. 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 "secondorder" 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 "firstorder" to "secondorder"
science may be treated as a change in the subject producing another
(interdisciplinary) science, which is as "positive" as the
original, "firstorder" research. The "secondorder"
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
nonEuclidean 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 "firstorder"
approach would be completely defined by the "secondorder"
theory, while the "firstorder" science would define the
transition to the synthetic level from the "secondorder"
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 heatingcooling 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 humanlike 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:
Syncretic development. Everything changes, and the machine
changes as a part of the world.
Analytical development. The machine changes its environment
which demands for the new ways of adaptation.
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 higherorder 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:
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.
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.
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
"higherlevel" 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 feedback from another machine. To make development
intelligent, one more condition must be satisfied: the feedback
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, humanlike 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 nonlocal, 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
selfmodification 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, 27, no. 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.
Online: International Philosophy Preprint Exchange,
http://cogsci.l.chibau.ac.jp/IPPE/Phil_of_Mind/Mulhauser.Mind_Out_of_Matter/ (no longer available online)
Penrose, R. (1994) Shadows of the Mind. (New York: Oxford University)
Pospelov, D.A. (1986) SituationDriven Control: Theory and Practice. (Moscow: Nauka)
Stapp, H.P. (1995) Psyche, 2; Online:
http://psyche.cs.monash.edu.au/volume21/psyche95205qm_stapp1stapp.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)
