A Turing-Framework for Evolutionary Processes

Figure 2.8: First Sketch of a Set-up with Turing Machines

To implement an evolutionary process with computers we will use as principal guideline the concept of computability as it has been defined by A.M.Turing [384] with his concept of a 'Turing Machine' [TM]. Until today this is the most general concept of a computational process and nobody could find a formalism, which demonstrates 'computability' and which is 'stronger' than the TM.

The figure 2.8 shows a first sketch of such a computational framework for evolutionary processes.

One way to write this in formulas could be as follows:

$\displaystyle env$ $\displaystyle :$ $\displaystyle ENV \longmapsto ENV$ (2.5)
$\displaystyle sys$ $\displaystyle :$ $\displaystyle ENVSYSIN \longmapsto ENVSYSOUT$ (2.6)

In this model(2.5) the environment is assumed as a set of possible 'facts' given as $ ENV$. These facts can be changed by the environment function $ env$. The individual systems within this environment usually can only use a subset $ ENVSYSIN \subseteq ENV$ from all these environmental states and they produce states which are only subsets of these $ ENVSYSOUT \subseteq ENV$ ($ ENVSYSIN$ and $ ENVSYSOU$ have to be written on a tape).

But this simple model(2.5) is lacking the main property which characterizes the dynamics of our world as well as the dynamics of biological life. The functions $ env$ and $ sys$ in this model are fixed. From history we know that the function $ sys$ has changed all the time, and - depending from the point of view of modeling - as well the function $ env$. The other point is, that the start ('birth') and the end ('death') of a biological system - in this case the 'existence' of the function $ sys$! - is managed by the environment $ env$ too.

To allow the start and end of a system function $ sys$ by an environment function $ env$ we have to assume that the system function is given as a description on the tape of the environment. That means a system is from the point of view of the environment a 'fact' which can be manipulated. In technical terms we would say that the environment function $ env$ simulates the system function $ sys$. Thus we wouldget:

$\displaystyle env$ $\displaystyle :$ $\displaystyle ENV \longmapsto ENV$ (2.7)
$\displaystyle sys$ $\displaystyle :$ $\displaystyle ENVSYSIN \longmapsto ENVSYSOUT$ (2.8)
$\displaystyle ENVSYSIN$ $\displaystyle \subseteq$ $\displaystyle ENV$ (2.9)
$\displaystyle ENVSYSOUT$ $\displaystyle \subseteq$ $\displaystyle ENV$ (2.10)
$\displaystyle sys$ $\displaystyle \subseteq$ $\displaystyle ENV$ (2.11)

This model(2.7) tells you that the 'laws' of the environment regulate the appearance of a system. In the next step it opens the possibility that the environment is also responsible for possible changes of the system function $ sys$. Like in the real world where the 'matter' consisting of atoms and molecules behaving according the laws of chemistry (based on physics) and within this 'field of laws' are 'directed' into 'typical' patterns of molecules' shaping self-reproducing units, we have here the environment function $ env$ determining how a system function shall be 'look alike' and 'when' it will start and end their 'work'.

This model is still incomplete because we know that the environment function $ env$ itself does change because the structure of the world is changing according to 'general laws' and according to the availability of different kinds of 'matter' under the 'circumstances' of a certain area of the universe. In this perspective the environment function $ env$ itself has to be assumed as a 'fact' with regard to a 'meta function' which we call here universe $ univ$ which is operating on 'facts' called $ UNIV$. Extending our previous model we have the following formulas:

$\displaystyle univ$ $\displaystyle :$ $\displaystyle UNIV \longmapsto UNIV$ (2.12)
$\displaystyle env$ $\displaystyle :$ $\displaystyle ENV \longmapsto ENV$ (2.13)
$\displaystyle sys$ $\displaystyle :$ $\displaystyle ENVSYSIN \longmapsto ENVSYSOUT$ (2.14)
$\displaystyle ENV$ $\displaystyle \subseteq$ $\displaystyle UNIV$ (2.15)
$\displaystyle env \subseteq$   $\displaystyle UNIV$ (2.16)
$\displaystyle ENVSYSIN$ $\displaystyle \subseteq$ $\displaystyle ENV$ (2.17)
$\displaystyle ENVSYSOUT$ $\displaystyle \subseteq$ $\displaystyle ENV$ (2.18)
$\displaystyle sys$ $\displaystyle \subseteq$ $\displaystyle ENV$ (2.19)

Thus, from the point of computability we have different levels of computation where functions of a lower level are 'facts' ('data') for functions of a higher level (cf. figure 2.9). The functions of the higher level always are simulating the functions of a lower level which are - seen from the higher level - 'data'. This schema can be extended infinitely often. But, clearly, it becomes more and more complex and the 'amount' of the 'computational work' is growing2.11.

Figure 2.9: Final Sketch of a Set-up with Turing Machines

For the following engineering process it follows that we have always to be clear to which extend we want to 'model' systems within environments. If we want more and more 'dynamics' in the model we have to model these dynamics with the aid of higher-level functions manipulating the dynamics.

Remarks: One should explain a bit more, whether those kinds of problems, which one wants to solve, are related either to those problems, which are 'computable' or not. The fact, that there exist mathematical concepts which can not be 'computed' alerts for the possibility, that some problems cannot be 'computed'. But because many mathematical problems have no counterpart in reality this 'being not computable' must therefore not inevitably be a problem for the problem at hand.

The other point is that to recognize a problem as 'not being computable' must also not be a counterargument against the use of a turing machine as benchmark. The turing machine can still compute 'non-computable problems', but there will eventually be no solution. But in this case no other device can do either. Besides this it is often the case that most 'non-computable' problems can be analyzed as 'hierarchies of functions' where every single function of the hierarchy can be computed, but the whole hierarchy as such not. To give up the concept of a turing machine would destroy any possibility to continue talking about any kind of computation.

Gerd Doeben-Henisch 2013-01-14