Evolution’s Halting Problem

Reading Time: 8 minutes

Introduction and Overview

This article describes a problem in Evolutionary Theory that arises when we consider why all living beings eventually die. I will compare the death of a living being to a computer program that halts after completing execution. The issue of program halting is problematic in computing theory because current computing models do not incorporate meanings. A similar problem exists for living beings too. If living beings are evolving by random mutation and natural selection, then there is no physical process of selection that will produce finitely lived living beings. In fact, if the selection process is just as Evolutionary Theory describes it, then we must find living beings that live infinitely long. This argument (along with several others) is described in detail in the book Signs of Life.

Semantically Incorrect Programs

Evolutionists frequently compare living beings to machines, arguing that we are not any different from computer programs. A replicating and mutating living being is compared to a self-replicating computer program, and there are active fields of research in digital life and genetic algorithms.

I have no quarrel with this comparison, except that computer programs and machines have no ability to represent and compute meanings today. There are broader issues of semantic understanding in both Artificial Intelligence and Cognitive Science today which have prevented the incorporation of real cognitive abilities commonly found in all living beings into computing machines. However, a profound understanding of why this inability to incorporate meanings in machines is fundamental is still missing.

One of the key features of all meaningful propositions (including meaningful programs) is that they must be finite. That is, if such a proposition (or program) is presented to a machine, and the machine parses the statement from start to end, the machine will indeed come to a halt. A statement that a machine cannot parse correctly because it has grammatical errors or uses letters, words, or phrases that are not permissible in the language (defined by the grammar) is syntactically erroneous. A program compiler—which converts a human-authored program to a machine understood program—will naturally eliminate such statements. However, there can be programs that are syntactically correct (i.e. they pass the compilation test) but are still not semantically valid because they never halt.

The Computational Halting Problem

Before you start executing a computer program, it is worth knowing if the program will indeed halt, because a program that never halts will never solve its intended problem. All programs that halt solve some problem (whether or not it was the intended problem) and can therefore be considered meaningful. In contrast, the programs that don’t halt also don’t solve any definable problem (intended or otherwise) and cannot, therefore, be considered meaningful.

Programs that don’t halt run into infinite loops. These loops can be encoded finitely but they cannot be executed finitely. If the program has no loops, and it is finite in size, then it must also halt. In effect, all meaningful programs that halt must be loop-free. The standard geometrical structure that represents loop-free paths is called a tree—it has a root, which then branches into twigs, which eventually culminates into leaves. A tree is always loop-free, and if a program had a tree structure, it would also be meaningful and would therefore halt. The question for computing theory is to know the geometrical structure of a program: i.e. does the program have loops, or is the program like a tree? If you could know this about any arbitrary program in advance, you would also know if this program would halt. Then, you could also determine whether we must start this program or not, and only programs that are loop-free would be started because it is only these programs that will terminate and solve a meaningful problem.

This problem is called the Halting Problem in computer science and Alan Turing—a famous British computer scientist and a wartime code-breaker—proved in 1936 that the problem is unsolvable. That is, we cannot determine the geometrical structure of a program without executing that program, and if the program is, in fact, loopy then the program execution will take an infinite time, which will effectively mean that we can never know if the program is in fact loopy. Therefore, if the program is finite, then the computer can know that it is finite, but if it is infinite we cannot know that it is infinite. In effect, if the program is meaningful you can know it is meaningful, but if it is meaningless you cannot know it; therefore, you also cannot eliminate meaningless programs.

Randomly Generated Programs

Suppose that we have the set of all possible programs and they have been generated by randomly sequencing syntactically correct elements (and proving that they are syntactically correct through compilation). If we were to run these programs on a computer, what percentage of programs will eventually halt? Cristian S. Calude and Michael A. Stay proved a few years back that given any arbitrary program, the program will either halt very quickly or never halt.

That is, the probability of a program that runs for a very long time and then terminates is vanishingly small, in the set of all programs. Most of the programs are either very short-lived or eternal. This means that if programs were being produced by randomly mutating computing instructions, then the likelihood of a program that never halts is quite high. Obviously, such programs will have one or more loops in them. Since there is no solution to the Halting Problem, it is impossible to eliminate such infinite programs in advance. While we cannot know which specific program is finite or infinite, the proof by Cristian S. Calude and Michael A. Stay statistically show that infinite programs have a much higher likelihood as compared to programs that terminate after running for a long time.

The Relation to Evolutionary Theory

The above facts have an important bearing on the problem of evolution:

  • We can suppose that a living species is like a computer program randomly created through mutations, just as the evolutionary theory postulates.
  • Since these programs will comply with the laws of nature—which we can suppose constitute the grammar of nature—all these byproducts of evolution will be syntactically correct.
  • From the above result about the likelihood of infinite programs, we can suppose that many such programs (living species) will be infinitely lived. We might consider them meaningless in the sense of not fulfilling a purpose and not solving a problem, but they must exist.
  • Turing’s proof of the unsolvability of the Halting Problem means that there is no mechanical procedure by which such infinitely long-lived programs (living beings) can be eliminated. That is, there can never be a natural selection procedure that eliminates infinite beings.
  • Since such programs (living beings) must abound in nature if they are randomly produced, and they can never be eliminated because of Turing’s proof, they must be found commonly.

Now for the fact: we don’t see any infinitely long-lived beings.

In fact, the fundamental premise of evolution is that all living beings must evolve to improve their chances of survival. The nature of all physical systems is that they eventually perish—i.e. that they are like meaningful programs which finish their ‘purpose’ and then halt. This also means that these programs must never have a loop. If nature was randomly producing programs, then many of these programs would be meaningless and they would loop infinitely. These programs would correspond to infinitely lived beings. There is no physical or mechanical procedure—e.g., natural selection—that can prevent such beings, and they must therefore abound. Except that we don’t see them anywhere.

In short, if we grant random mutations and natural selection as physical procedures, we would find that the world is full of living beings that can never die. The evolution of such beings itself would be meaningless; since they are never going to die, they can only replicate and create more such infinite beings. Since such beings must have existed from the beginning of life, there must be living beings that are billions of years old now, further producing other beings which are never going to die. Clearly, we don’t see any of it.

Of course, if an eternal species indeed existed, and was multiplying in numbers, then eventually there would be too many of that species and they would consume so much food, water, and other resources that everyone would eventually run out of resources. That would correspond to a computer shutting down because it ran out of power supply. But until it does actually run out of food, such a species could keep multiplying and growing in numbers. Can there be anything in nature that can somehow ‘know’ that the members of some species will not die until all the resources are actually finished? Indeed, given that some species has lived a long time, is there some way in nature that can predict that the species will actually live forever and not die after living a long lifespan?

Turing’s proof indicates that these questions can never be answered.

The Flaw in Evolutionary Theory

The fact that there can never be a procedure in nature (if nature is physical things) that can know in advance if a random mutation will create a species that lives eternally means that such species cannot be prevented by natural selection, since natural selection is also a certain kind of physical procedure. Since random mutations imply that infinite programs are imminent, it follows that if living beings were viewed as computer programs, some of these randomly created programs must also live forever. There is no mechanical procedure that can determine whether a given program is in fact infinite, so if there were an infinite program, there would be no mechanical procedure to actually terminate it.

That in turn implies the impossibility of natural selection preventing the existence of infinitely long-lived beings. Therefore, if a natural selection procedure to destroy eternal beings cannot exist, and such beings are possible due to random mutations, then they must somehow abound in our ecosystem. Why don’t we see them? Indeed, if we grant natural selection and random mutations in a physical system, the system will resemble a computer in which the meaningful, short-lived programs finish quickly while the infinitely lived programs continuously replicate into programs that will never die. Eventually, when the system runs out of resources, the programs must halt, like a computer running out of power.

Summary and Conclusion

Alan Turing assumed that the Halting Problem can be solved by a mechanical procedure and then arrived at a logical contradiction. His proof entails that unless we can know program semantics, we cannot know if a program will halt. Since there is no way to know program semantics in current computing theory—because a computer does not hold meanings, but only physical states—the Halting Problem implies that in a physical world nature cannot determine which programs are meaningful (and finite) or meaningless (and infinite).

The evolutionary theory supposes that random chance events followed by natural selection can produce meaningful organisms. The meaning here doesn’t have to be a transcendental purpose in the universe. Rather, it can simply be defined by input and output relations to other programs. The facts concerning all programs and physical systems entail that this theory is logically inconsistent. If the premise under evolutionary theory were to be true, then it would also be possible to find meaningless programs. What evolutionary theory supposes is therefore an extra theoretical fact, which can never be instantiated in a physical universe, if that universe is just like a computer program running on today’s computers.

The premises in evolution constitute a logically inconsistent theory. The production of finitely-lived species can only be explained if these species are produced as a process of encoding meaning, which requires the meaning to exist in some form prior to its encoding in matter. If biological forms encode semantic information, and nature understands semantics, then it will only produce meaningful and hence finite programs. That process will explain why all living beings are finite. But it will not involve random mutations or natural selection. Rather, if the meaning encoding process produces programs, then the real question would be whether such programs are good or malicious!

Signs of Life explores the mechanisms by which this new kind of natural process can create life. In this new process, there is evolution, but neither random mutation, nor natural selection has anything to do with it.

Cite this article as:

Ashish Dalela, "Evolution’s Halting Problem," in Shabda Journal, August 10, 2015, https://journal.shabda.co/2015/08/10/evolutions-halting-problem/.