Essays, Posts & Presentations

Adaptive Evolution for Turing Machines

Brian A. Mboya, Eric James Parfitt

Author

Brian A. Mboya, Eric James Parfitt

Title

Adaptive Evolution for Turing Machines

Description

A minimal model for adaptive, biological evolution using Turing machines.

Adaptive Evolution for Turing Machines

BRIAN A. MBOYA AND ERIC JAMES PARFITT

When we think of biological systems, all the time we don’t actually have a way of describing them, therefore lack an understanding of what’s going on underneath these systems as they undergo evolution. This project tries to ignore some of the constraints that we may encounter in biological systems namely “we don’t know what’s going on” and essentially think of biological organisms as computational systems with certain sets of rules they follow to develop. These rules are equivalent to the genotype of the organism and the result of executing them as its phenotype. We take a minimal model for biology that has this setup, Turing machines, and study their adaptive evolution.

The main idea is to have a Turing machine with configurations of n-colors, s-states, and a rule . We then run the machine for a number of steps, changing the rule each step to find a pattern that lives the longest.

A Minimal Model for Biological Evolution and Adaptive processes

A question one could potentially ask is how does biological evolution work or for that matter, why does it work? Here, we explore this question and more using a minimal model for biological evolution and some adaptive processes.

Introduction to The Model

Notes for this notebook:

◼

2-state, 2-color machines 4096 rules

◼

s-state, k-color machines (2 s k)^(s k) rules

◼

A single rule {state, color} -> {newState, newColor, direction}

◼

List of rules {singlerule1, singlerule2, singlerule3, ..., }

◼

ParallelMutation Refers to a mutation done on a single rule but all the values for“newState, newColor and direction” are change at the same time.

◼

NumberOfMutations Refers to the number of mutations to perform if MultipleRuleMutation is set to true

◼

MultipleRuleMutation Performing mutation to more than 1 rule in a set/list of rules

For our project, we will focus on all the above.

The 3-state, 3-color, using the above, we have rules totalling to:

In[28]:=

(233)^(33)

Out[28]=

198359290368

Let us consider a simple example of what we will be discussing in this project.

Given the example rule below:

In[29]:=

rule={{1,0}->{2,1,-1},{1,1}->{2,0,1},{2,1}->{1,0,-1},{2,0}->{1,1,1}};

Here’s the evolution of a Turing machine based on the rule with only 10 steps.

In[30]:=

RulePlot[TM[rule],{1,{{},0}},10,MeshAll,ImageSize150]

Out[30]=

Now, let’s think about how we can evolve a system from a single point like the one below to a system like the one above without setting any explicit rule like we did above but mutating a certain rule, which in this project we call a null rule, then after a certain number of evolution steps we observe what happens.

In[31]:=

nullEvolution=TuringMachine[{{1,0}->{1,0,0}},{1,{{},0}},0];RulePlot[TM[#->{1,0,0}&/@Tuples[{Range[3],Range[0,2]}]],nullEvolution,ImageSize120]

Out[32]=

The expected behaviour for a system with null rule, of course, is that it immediately dies out for a program like a cellular automata. But since we are going to use a different program; Turing machine, the expected behaviour is for this machine to run forever or up to a finite number that you have set the program to run without changing any state. So if we run the above machine again for steps = 10, the following should be expected.

In[115]:=

testrule=#->{1,0,0}&/@Tuples[{Range[3],Range[0,2]}];nullEvolutionTenSteps=TuringMachine[testrule,{1,{{},0}},10];RulePlot[TM[testrule],nullEvolutionTenSteps,ImageSize50]

Out[117]=

As you can see the system just keeps going without doing anything. This is good for us because we can use this realization to check the evolution of our system later on when we actually start doing changes to the state of the system or for our case; do random “point mutations” to the system.

How will that work? Well, we will evolve the system by changing it, then detect the point the system starts repeating itself or gets stuck in an infinite loop. After we find where the system gets in a loop, we can then use that as a halt state so that whenever we get to that state, we halt the evolution of the system and make judgements(usually based on performance of the system) in regards to what we want to do to the system.

We set the halt state to something like below; this is for the example. Later on we will see how to set for all the rest of the rule.

In[36]:=

haltRule={1,0}->{1,0,0};

If we look at the test rule below, we can see the halt state as the first rule.

In[37]:=

testrule//Column

Out[37]=

{1,0}{1,0,0}

{1,1}{1,0,0}

{1,2}{1,0,0}

{2,0}{1,0,0}

{2,1}{1,0,0}

{2,2}{1,0,0}

{3,0}{1,0,0}

{3,1}{1,0,0}

{3,2}{1,0,0}

Let us plot the rules and see how it looks like:

In[38]:=

RulePlot[TM[testrule],ImageSize->Large]

Out[38]=

With this, whenever our system gets to the first state in the plot above, it halts its evolution.

How can we make use of the halt state? In the following section we perform random “point mutations” to our system and observe how it behaves.

Turing Machine Random Point Mutations

We refer to random point mutations here’s as picking a single rule at random and changing one outcome in the rule then adaptively evolving the system. To perform mutations, let us consider a 3-state, 3-color Turing machine. Later on we can demonstrate how other Turing machines can be changed and evolved.

First, we want to make sure our null rule reflects our definition of halt state. Essentially, we want all the rules in our null rule to be halt states, that way the system halts immediately at the start of the evolution and before mutations.

Let’s define our null rule:

In[39]:=

nullRule=GetNullRule[3,3];RulePlot[TM[nullRule],ImageSize->Large]

Out[40]=

With a beginning of our evolution setup, let’s now do changes to our system and adaptively evolve it.

Perform random point mutations on null rule

We can now randomly mutate each point in the null rule one at a time with probability of

= 1.0 so that at least a mutation happens. You can as well mutate in parallel i.e, all the values in a rule are changed at once. We will see that later on.

To show how this will work, we will run this manually but later on we will run our null rule through an algorithm that does the mutations a number of steps and observe how the system evolves.

In[41]:=

randomlyMutatedRule=nullRule;(*Resetmutation*)

Before mutation:

In[42]:=

RulePlot[TM[randomlyMutatedRule],ImageSize->Large]

Out[42]=

In[43]:=

randomlyMutatedRule=MapAt[(MutateRule[#,1.0,3,3][[2]])&,nullRule,RandomInteger[{1,Length[nullRule]}]];(*Mutatethenullrule*)

After mutation:

In[44]:=

RulePlot[TM[randomlyMutatedRule],ImageSize->Large]

Out[44]=

If you observe closely through the rule above, you will notice a small change compared to what we had initially. This suggests a change in the system.

We can visualize the evolution:

In[322]:=

mutatedEvolution=TuringMachine[randomlyMutatedRule,{1,{{},0}},10];RulePlot[TM[randomlyMutatedRule],mutatedEvolution,ImageSize50]

Out[323]=

The system goes on forever, not exactly what we want. Well, this is expected because the system hit the halt state immediately even after mutation. To see a change, we need to run it multiple times as we do changes to it.

But one thing we can do to this system when we detect that it has hit a halt state is to know how long it lived before it got there. We can perform fixed point to the system to only get the part that we are interested in, in this case, the life time of the system before halting. This is called fixed point but in this project we refer to it as lifetime of the machine. (We subtract 1 because the fixed point algorithm we are using returns 2 similar values appended to the end of the result)

In[47]:=

afixedPoint=Subtract[FixedPointList[TM[randomlyMutatedRule],{1,{{},0}},Infinity]//Length,1];afixedPoint

Out[48]=

Running it through the FixedPointList algorithm, it tells us that the system lived for as long as 2 generations.

Let us visualize this system’s evolution after the mutation:

In[49]:=

afixedPointEvolution=Take[mutatedEvolution,afixedPoint];RulePlot[TM[randomlyMutatedRule],afixedPointEvolution,ImageSize50]

Out[50]=

From the above, after the initial run, the system immediately goes to halt state. We can also see that it has lived for a lifetime of 2. In the next section, we will see how to determine lifetime of a system. For this first system, 2 is the lifetime we have found.

The next section we’ll run the system through an algorithm that does the evolution process described above.

Turing Machine Lifetime Selection

I described here how the lifetime selection is done.

First, confirm our null rule has not changed to test the new evolution.

In[108]:=

RulePlot[TM[nullRule],ImageSizeLarge]

Out[108]=

The goal, here, is to run as many Turing machines as possible to get the one that lives the longest lifetime. In each step, we will also keep track of all possible generations that our winner came from but only those that evolved more than the previous generations of the machines. At the end we expect a list of all the machines that made progress or were accepted to move on to the next generation. Below is a procedure we will follow;

◼

We perform random point mutation above on the null rule

◼

Check if the machine made a step in the process by checking its lifetime against the previous machine.

◼

If the lifetime found is greater or equals to the previous machine, we accept it to move of to the next generation

◼

Otherwise, we reject the machine and eliminate it from the evolution process

◼

We repeat the steps above, keeping track of all accepted machines

◼

We then filter out all the machines that made it

It turns out with this procedure, as we will see shortly, we can adaptively evolve to new patterns.

To test this process, let’s run our algorithm to perform evolution for 500 steps and a cut off of 50; cut off is the maximum number of evolution we want to have. Here, we just set to a minimum number as possible for demonstration. You can play around with larger values. Note: SeedValue changes the state of the random generator algorithm.

In[172]:=

PlotFiniteEvolution[nullRule,{3,3},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"->False,"ChangeHead"->False,"MultipleRuleMutation"False,"NumberOfMutations"->2]

Out[172]=





As you can see above, a simple form emerges, then as the adaptive process goes on, the system starts to develop large forms. Its interesting to just think about it because you can imagine what sort of patterns we might get if we ran the system for a long but finite number of steps or even infinite time steps.

You might wonder how much time did a system in the above pattern take to evolve to the next generation. The following plot shows a trace of the whole adaptive evolution process.

In[53]:=

EvolutionTracePlot[nullRule,{3,3},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"->False,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[53]=

...

To see what’s going on, let’s make a plot for the maximum lifetime achieved so far against the total number of mutation steps made. We will include rejected just to see all the activities happening in our evolutionary process.

In[54]:=

With[{},Block[{life,evolved,l},SeedRandom[672113];life=Reap[Sow[1];evolved=GetShowEvolution[nullRule,20,1000,{3,3},False]][[2,1]];ShowGraphics[evolved,life,Large]]]

Out[54]=

The red dots in the plot above show those machines that never make it to the next step while the blue line represents the trajectory the evolution process takes at every step.

Let us now try out different mutations strategy.

Mutation happening in parallel

As I mentioned in the notes section at the top, parallel mutation changes everything in a rule. For example, instead of mutating one at a time in {newState, newColor, direction}, we mutate all at once.

In[173]:=

PlotFiniteEvolution[nullRule,{3,3},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"True,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[173]=





From the output above, we can see a big different in the evolution with this mutation strategy used. With the same value as before but mutating randomly, we only get a generation of 5.

Let’s see how long it took for a new generation to emerge by tracing the previous generations.

In[56]:=

EvolutionTracePlot[nullRule,{3,3},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"True,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[56]=

...

265

...

As you can see the margin is pretty high when the mutation is done in parallel. This suggests that the system makes larger jumps in rule space which makes the system’s evolution happen quickly at the beginning and when lots of mutation is done in this sense, we end up with all the halt states filled out. Therefore, the system never halts as much in the end until it mutates to the desired halt state, which may not happen as soon or never at all.

Comparison to Other Turing machines

2-state, 2-color Turing machine

All possible rules for (2 2)TM:

In[57]:=

(222)^(22)

Out[57]=

4096

Set the null rule for (2 2)TM:

In[58]:=

twoTMNullRule=GetNullRule[2,2];

In[104]:=

RulePlot[TM[twoTMNullRule],ImageSizeMedium]

Out[104]=

Evolution plot:

◼

Mutation happening one at a time.

In[178]:=

PlotFiniteEvolution[twoTMNullRule,{2,2},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"False,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[178]=





In[179]:=

EvolutionTracePlot[twoTMNullRule,{2,2},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"False,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[179]=

...

◼

To see mutation happening in parallel, change the option “ParallelMutation” to True.

3-state, 2-color Turing machine

All possible rules for (3 2)TM:

In[62]:=

(232)^(32)

Out[62]=

2985984

Set the null rule for (3 2)TM:

In[63]:=

threeTwoNullRule=GetNullRule[3,2];

In[105]:=

RulePlot[TM[threeTwoNullRule],ImageSizeMedium]

Out[105]=

Evolution plot:

◼

Mutation happening one at a time.

In[290]:=

PlotFiniteEvolution[threeTwoNullRule,{3,2},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"->False,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[290]=





In[66]:=

EvolutionTracePlot[threeTwoNullRule,{3,2},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"->False,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[66]=

...

◼

To see mutation happening in parallel, change the option “ParallelMutation” to True.

4-state, 3-color Turing machine

All possible rules for (4 3)TM:

In[67]:=

(243)^(43)

Out[67]=

36520347436056576

Set the null rule for (4 3)TM:

In[68]:=

fourThreeNullRule=GetNullRule[4,3];

Evolution plot:

◼

Mutation happening one at a time.

In[291]:=

PlotFiniteEvolution[fourThreeNullRule,{4,3},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"False,"ChangeHead"->False,"MultipleRuleMutation"False,"NumberOfMutations"->2]

Out[291]=





In[70]:=

EvolutionTracePlot[fourThreeNullRule,{4,3},"Cutoff"->50,"Steps"->500,"SeedValue"->672113,"ParallelMutation"->False,"ChangeHead"->False,"MultipleRuleMutation"->False,"NumberOfMutations"->2]

Out[70]=

...

◼

To see mutation happening in parallel, change the option “ParallelMutation” to True.

Evolution growth for all Turing machines

Change steps from 2000 to a lower number for faster execution.

In[71]:=

Module[{twoevo,fourthrevo,threvo,threetwoevo},SeedRandom[672113];twoevo=GetShowEvolution[twoTMNullRule,50,2000,{2,2},False];fourthrevo=GetShowEvolution[fourThreeNullRule,50,2000,{4,3},False];threvo=GetShowEvolution[nullRule,50,2000,{3,3},False];threetwoevo=GetShowEvolution[threeTwoNullRule,50,2000,{3,2},False];Show[ListLinePlot[{Last/@twoevo,Last/@fourthrevo,Last/@threvo,Last/@threetwoevo},PlotRange->All,AspectRatio->1/4,Frame->True,PlotLegends{"(2 2) Turing machine","(4 3) Turing machine","(3 3) Turing machine","(3 2) Turing machine"}],ImageSize->Large]]

Out[71]=

(2 2) Turing machine

(4 3) Turing machine

(3 3) Turing machine

(3 2) Turing machine

From the above, it seems to suggests TMs with larger states starts to evolve much later in time. For example, TM (2 2) evolves fast at the beginning but stops almost immediately for the number of steps used here. And if you look at TM (4 3), evolution start much later after like 430 steps in its evolution process. But the interesting fact about it is its evolution starts later than all other machines with less states.

The Multiway Graph of All Possible Mutations Histories

Let’s look at it using multiway graph. The multiway graph will help us understand what’s actually going on in the evolution process, we can create a map of all relationship between previous generation of machines to the current. Here, we will focus only on (3 2) Turing machine but you can try them all out for yourself by changing the argument for {state, color} in the MultiwayGraph function.

Please note that the results here are preliminary as we are picking a random point and mutating it by considering only one possibility. For example, this rule, {1, 1} -> {2, 1, 0}, for TM(3 2), has 3 possibilities, i.e, {1, 1} -> {2, 1, 1}, {1, 1} -> {2, 2, 0}, {1, 1} -> {3, 1, 0} but we are only considering one of these possibilities. Also, the algorithm does not handle cases where the previous machine immediately hits a halt state, in which case they are the same.

(3 2) Turing machine:

Let’s start with our null rule as the root/parent node.

In[72]:=

parent=GetNullRule[3,2];

In[106]:=

RulePlot[TM[parent],ImageSizeMedium]

Out[106]=

We then enumerate each machine child by performing a single point mutations. Below is a plot to show all the mutations done on each machine child and the result of the child evolution after mutation. The result is selected as in lifetime selection above where we take those “children” that make progress.

Here, we determine progress by comparing the evolution of a machine child to the parent machine, if child lifetime is greater than or equal to the parent, we move the child to the next generation.

Let’s look at the parent tree on a multiway graph: Note: Setting “MultipleRuleMutation” to True and “NumberOfMutations” to n, where n > 0, will mutate n + k times, k being number of mutations happening somewhere in the code (This is a bug that will be fixed in future updates).

In[321]:=

MultiwayGraph[parent,GreaterEqual,{50,50},{3,2},"MaxLayers"->1,"ParallelMutation"->False,"MultipleRuleMutation"False,"NumberOfMutations"->0]

Out[321]=

We can then run the above enumeration through a multiway graph to see clearly what is happening and how the relationship are created from a null rule or parent to all the children machines that make progress. The multiway graph below shows all the possible paths to take from the parent machine (parent machine being the null rule) to the last child machine. The graph displayed is for (3 2) Turing machine with “NumberOfMutations” point mutation performed in parallel: (state, color, direction) changed all at once. Here, with only 50 steps for each evolution, we manage to get a number of rules appearing. As you can see, plenty of these mutations seems to go one way which means if they went both ways, they could reduce their chances of survival or be rejected.

Evaluating for 3 layers of the tree:
If MultipleRuleMutation is True, NumberOfMutations takes effect.
Also note: The loop you see in the graph is a bug in the code that is being investigated.

In[75]:=

MultiwayGraph[parent,GreaterEqual,{50,50},{3,2},"MaxLayers"->2,"MultipleRuleMutation"True,"ShowRule"->False,"ParallelMutation"True,"NumberOfMutations"5,"Embedding""LayeredDigraphEmbedding"]

Out[75]=

In the previous evolution process, we have been taking machines whose evolution produced a lifetime of greater or equal to the parent machine they came from. That is evident with a lot of repetition in the previous multiway graph. We can restrict the process so that we only allow machines that evolve with greater lifetime than the parent machine. And below, we can see a multiway graph with only those machines that made progress. The number is reduced and we do not have a lot of repetition as before. You may also notice that many of these systems seem to go one way suggesting that there would be greater chances of them being rejected if they went both ways.

In[76]:=

MultiwayGraph[parent,Greater,{50,50},{3,2},"MaxLayers"->2,"MultipleRuleMutation"True,"ShowRule"->False,"ParallelMutation"True,"NumberOfMutations"5,"Embedding""LayeredDigraphEmbedding"]

Out[76]=

Future Work

◼

Fix the algorithm to handle cases where the previous machine immediately hits a halt state; should consider them the same.

◼

Handle all possibilities for a rule. For example, this rule, {1, 1} -> {2, 1, 0}, for TM(3 2), has 3 possibilities, i.e, {1, 1} -> {2, 1, 1}, {1, 1} -> {2, 2, 0}, {1, 1} -> {3, 1, 0}.

◼

Fix loops in the multiway graph. The loops are as a result of the above bug where we don’t check for similarities

◼

Fix when setting “MultipleRuleMutation” to True and “NumberOfMutations” to n, the algorithm performs some additional mutations, n + k to the rule. Should just be n mutations.

◼

Sexual Reproduction

Concluding Remarks

The result found here seems to suggest that adaptive evolution can happen in a system provided the system changes. This is true as well for biological systems where the entire system depends on genes to evolve, and any edits to these genes can significantly affect the system’s evolution. The only real question is how should the changes/edits happen for better results? Because as far as evolution is concerned, good is not desirable.

Acknowledgments

I would like to thank my mentor Eric James Parfitt for guiding me through the project, Stephen Wolfram for the initial project idea and to all the Wolfram staff who helped organize the 2024 Wolfram Summer School.

References

◼

Stephen Wolfram, A New Kind Of Science, Wolfram Media (2002). ISBN: 1-57955-008-8

◼

Stephen Wolfram, Why Does Biological Evolution Work? A Minimal Model for Biological Evolution and Other Adaptive Processes, May 3, 2024

◼

Geometry of Program Synthesis

◼

Mutation-selection dynamics and error threshold in an evolutionary model for Turing Machines

Initialization Code


Cite This Notebook

Adaptive Evolution for Turing Machines
by Brian A. Mboya
Wolfram Community Post Link, July 10, 2024

Cite this as: Brian A. Mboya, Eric James Parfitt, "Adaptive Evolution for Turing Machines" from the Notebook Archive (2024), https://notebookarchive.org/2024-07-524ty6z

Adaptive Evolution for Turing Machines

A Minimal Model for Biological Evolution and Adaptive processes

Introduction to The Model

Notes for this notebook:

Turing Machine Random Point Mutations

Perform random point mutations on null rule

Turing Machine Lifetime Selection

Mutation happening in parallel

Comparison to Other Turing machines

2-state, 2-color Turing machine

3-state, 2-color Turing machine

4-state, 3-color Turing machine

Evolution growth for all Turing machines

The Multiway Graph of All Possible Mutations Histories

Future Work

Concluding Remarks

Acknowledgments

References

Initialization Code

Cite This Notebook

Initialization Code
