More specificaly it's what ontology is enough to get open-ended evolution. I have no idea... My best guess is to apply the best available model of computation. That's quantum computing at the moment. This would mean that current computers can only slowly emulate quantum computing that might be essential for open-ended evolution. And this also leads to the question whether we really need continuous (uncountable) ontology of the quantum mechanics to get quantum computer behaviour: Is bounded-error quantum polynomial time (BQP) class can be polynomially solved on machine with discrete ontology? (countable ontology).

This area is out of my expertise so I should first understand quantum computing from the mathematical point of view: PHYS771 Lecture 9: Quantum (by Scott Aaronson). As far as I heard that's the best introduction view of the quantum computing.

P.S. I've just read this post in r/alife.

This post doesn't quite fit here but it might be a curious thing how I wrote a promotional article for a research task “Open-ended natural selection of interacting code-data-dual algorithms as a property analogous to Turing completeness”.

And here is a promotional article:

Buddha-Darwinism on objective meaning of life separated from subjective meaning of life (Cosmogonic myth from Darwinian natural selection, Quasi-immortality, Free will, Buddhism-like illusion of the “Self”) aka Applying Universal Darwinism to evaluation of Terminal values gives “Buddarwinism”.

Hi all,

I write to announce the release of a new research forum on open-endedness. The best introduction is the welcome page.

The new forum may be thought of as a conceptual extension of this reddit, with extra functionalities to enhance the forum as a research and collaboration tool.

Hi all, I just wanted to put the OEE4 workshop on the radar here. Program will soon be posted on the OEE4 site.

Open-ended natural selection of interacting code-data-dual algorithms as a property analogous to Turing completeness

The goal of this article is to promote an unsolved mathematical modelling problem (not a math problem or question). And unlike math questions it still doesn't have a formal definition. But I still find it clear enough and quite interesting. I came to this modelling problem from a philosophy direction but the problem is interesting in itself.

Preamble

The notion of Turing completeness is a formalization of computability and algorithms (that previously were performed by humans and DNA). There are different formalizations (incl. Turing machine, μ-recursive functions and λ-calculus) but they all share the Turing completeness property and can perform equivalent algorithms. Thus they form an equivalence class.

The open-ended evolution is a not very popular research program which goal is to build an artificial life model with natural selection which evolution doesn't stop on some level of complexity but can progress further (ultimately to the intelligent agents after some enormous simulation time). I'm not aware of the state of the progress of open-endedness criteria formulation but I'm almost sure that it's still doesn't exist: as it's either connected to results of a successful simulation or to actually understanding and confirming what is required for open-endedness (I haven't heard of either).

The modelling problem

Just as algorithms performed by humans were formalized and property of Turing completeness was defined: the same formalization presumably can be done to the open-ended evolution observed in nature. It went from precellular organisms to unicellular organisms and finally to Homo sapiens driven by natural selection postulates (reproduction-doubling, heredity, variation-random, selection-death, individuals-and-environment/individuals-are-environment) and the Red Queen hypothesis that resulted in increasing complexity. Open-endedness property here is analogous to Turing completeness property. It could be formalized differently but it still would form an equivalence class.

And the concise formulation of this process would be something like Open-ended natural selection of interacting code-data-dual algorithms.

Code-data duality is needed for algorithms being able to modify each other or even themselves. I can guess that open-endedness may incorporate some weaker "future potency" form of Turing completeness (if to assume discrete ontology with finite space and countable-infinite time then algorithms can became arbitrary complex and access infinite memory only in infinity time limit).

Please consider if it's an interesting mathematical modelling problem for research and share your thoughts.

Further info links

• open-ended evolution subreddit
• article on my (futile) efforts and it's old Reddit discussion
• digital philosophy subreddit (posts by kiwi0fruit)

Below is a predecessor of this promotion article:

Open-endedness as Turing completeness analogue for population of self organizing algorithms

Recently I wrote small article named "Simplest open-ended evolution model as a theory of everything". But right after finishing it I noticed that theory of everything part was just a guide and crutch to a more interesting point of view.

Specifically that property of open-endedness (that is yet to be discovered) can be viewed as Turing completeness analogue for population of self organizing algorithms under natural selection (where each program is also data). And my research program was essentially about finding necessary and sufficient criteria for open ended evolution (OEE). Plus may be some intuitions about directions in which it can be found (most notable is applying simplest OEE model to the beginning of the artificial universe). Hence all philosophical questions that bothered me are now reduced to necessary and sufficient criteria for open ended evolution that is no longer a philosophical question at all (for philosophical part see this acticle).

UPD

If turing completeness is a formalization of algorithms (that previously were performed by humans only). I'm interested in formalization of natural selection open-endedness that is now observed in nature (called OEE). That's what my post is about essentially. That formalization is still not there. It's an open and a hard question.

Text of the original article:

Simplest open-ended evolution model as a theory of everything

Year ago I abandoned the research project (old Reddit discussion, article, subscribe on Reddit). But from now on I hope to spend on it at least a few hours per week. To start with let's remember cornerstones of this research program:

1. Open-ended evolution

Open-ended evolution (OEE) model:

• contains natural selection (NS) postulates (reproduction-doubling, heredity, variation-random, selection-death, individuals-and-environment/individuals-are-environment).
• in which the evolution doesn't stop on some level of complexity but can progress further to the intelligent agents after some great time.
• that should presumably incorporate: turing-completeness (or it's weaker "future potency" form) and Red Queen hypothesis.

2. Theory of everything

By Theory of everything I mean:

• dynamic model of an artificial universe in which after some enormous simulation time properties of our universe is possible (but not necessary highly probable) but existing of intelligent life is highly probable.
• model that is capable of answering all in-model "why these structures exist and processes take place instead of the other?" questions by combination of transition rules postulates application and history of events (including completely random events).
• it may be desirable to have a universal description tool that can be applied to any "level" of the model (where "higher" levels are built upon many smaller modules. But the picture would be more complicated if strange loops are possible). Level hierarchy can be alike to organelles -> cells -> species individuals -> packs/tribes -> populations.

3. Simplest

By simplest I mean:

• As less axioms that govern evolution of the model as possible: Occam's razor (OR) plus extracting necessary and sufficient (NaS) system transition rules that still give OEE (it may even be some equivalence class property like turing-completeness).
• In the model time is discrete and countable infinite (given by random events), there was the first moment of existence, space is discrete and finite. We can try starting thinking about it with a graph-like structure with individuals of NS as nodes - graph is the simplest space possible.
• This raises question: What about quantum computers? Is bounded-error quantum polynomial time (BQP) class can be polynomially solved on machine with discrete ontology? And if yes what should this ontology be?
• Also I guess some may argue for lack of random events and going Everett many world quantum mechanics (QM) interpretation way. Can model

be viewed as a "superposition" of random events happened in different universes? If yes then we may get uncountable infinite space-time (btw: would superposition in QM preserve countable infinity for space-time?).

4. UPD

I dropped seriously investing in my research not long before I discovered connections with OEE and even then I wasn't aware that the only notable part of my research is OEE question part (hence I simply reinvented the wheel question but moved from philosophy side). Since publication of this post I'm aware of that so investing in finding out what is open-endedness is inevitable if I want to progress on this task.

Moved content to https://www.reddit.com/r/compsci/comments/97s8dl/on_natural_selection_of_the_laws_of_nature/

We wrote a blog post summarizing our ideas about complexity barriers and why we think they're useful. This is pretty similar to what I discussed in my talk, but a little more fleshed out (since it doesn't have to squeeze into 8 minutes!). In the interest of encouraging discussions (and to make it cite-able if people think it's a useful concept), we decided to try a little experiment and post it on The Winnower. The Winnower is a somewhat experimental open-access publication venue, which encourages post publication review. So go take a look and let us know what you think! https://thewinnower.com/papers/2309-what-s-holding-artificial-life-back-from-open-ended-evolution

If that's not your thing, you can also view and comment on it on our blog: http://devosoft.org/whats-holding-artificial-life-back-from-open-ended-evolution/. Or you can leave a comment here.

Looking forward to hearing your thoughts!

First, I will summarize the distinction between “open-endedness in a box” and “open-ended box,” as I understood it. Following this, I will provide my reason for siding with “open-endedness in a box,” and will suggest the “open-ended box” should be dropped.

1. The way I understood the distinction is: “open-endedness in a box” means the OEE theorist predefines a model, runs it, and looks for the occurrence of open-ended evolution within this framework. “Open-ended box” means the theorist allows for a model that can be changed throughout a run of a model. This is possible by either adding new dimensions or changing parameters.

2. I can conceive of two possible methods for changing a model partway throughout a run:

a. There must be some operation that defines how these dimensions are added, or parameters changed (For example, an evolutionary algorithm can search a dynamical system’s parameters). If this operation is defined prior to running the model, then the scientist that looks at the changing model is only tricking himself into thinking he is observing an open model. The broader model, which includes the operation that adds dimensions or changes parameters, is itself closed. And this broader model is also the proper object of theoretical study.

b. The other option is that a human experimenter manipulates the model part-way through a run, again by either adding dimensions or changing parameters. This allows for the experimenter to avoid a pre-defined operation for updating the model. But it is also very unscientific. The humans are in this case interacting with the model, and introducing their subjective bias. They are part of the operation that brings about apparent open-endedness in the model.

Because of this, I believe “open-endedness in a box” is the only truly scientific option of these two, and "open-ended box” should be dropped.

If you believe there are other options for “open-ended box” that are scientific, please respond.

A thread to hold "administrative" comments (stay tuned!)

As a first step toward achieving open-ended evolution in an artificial system, we need to come to some agreement about what that goal really means.

At an instinctual level, I think most of us are looking to create an artificial system that evolves more like a natural system, but the specifics of what we're looking for differ. Possibilities include systems that:

• ...keep producing novelty
• ...keep producing organisms that are increasingly complex
• ...keep producing and filling new ecological niches
• ...are capable of undergoing major evolutionary transitions

Many biologists assume that open-ended evolution simply refers to a system where some form of genetic change keeps occurring, even if it doesn't evolve novelty. Clearly we want to go beyond that simple threshold, but what do we (as a group) really mean by open-ended evolution?

Our goal with this subreddit is to encourage active conversation about topics associated with open-ended evolution, initially for the OEE workshop at ECAL 2015. Please submit topics you'd like to discuss or any relevant links.

Note, to encourage moving toward a consensus on OEE topics, if you disagree with someone else's comment please REPLY to it instead of downvoting (minimize downvoting and reserve it more for comments that are off topic). Upvote any topics, questions, or comments you feel to be relevant or that you particularly agree with.