Shabda Blog

Ruminations on Vedic Philosophy

Evolution’s Halting Problem

This post 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 my book Signs of Life.


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 shows 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).

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!

My book 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 have anything to do with it.

Related Posts

4 thoughts on “Evolution’s Halting Problem

  1. We do see them! all the time.

    “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.”

    This occurs quite often, but usually kills the organism first. Its called “Cancer”.
    Some of them can even reproduce. There is an infectious Canine Penile cancer. Its tens of thousands of years old. Its not a virus. Its actually an immortal tumor that spreads. It has a different genome than its host.

    Programmed aging and cellular death are tools to kill off cancer cells.

    1. You proved my point. The point being that if the mutations are random, then some living beings will be eternal. Not long lived. Eternal. The fact that living beings are dying due to cancer, or in other ways, itself indicates that they are not eternal, and therefore not randomly created. If you read the theorem posted in the essay, you will find why the eternal programs would abound in nature, if the process was random mutations. Natural selection doesn’t pick out such random programs, and becomes irrelevant. The only way to end such living beings would be to end the entire ecosystem (i.e. power off the computer).

      Of course, the argument above assumes that we are Turing Machines. Whether this model applies to an ecosystem is a separate question — someone can argue that a system of machines behaves differently from an individual machine. When you make points such as virus, or animals killing each other, we are supposing that a program can modify another program, which isn’t allowed in the Turing Machine model: a machine can give an input to another machine but cannot modify the logic of that machine.

      Hence, I wrote a post following this one (Evolution and Mechanism – Are They Compatible?) to show why the modification paradigm fails too. This failure, however, isn’t about eternity, but the inability to predict evolution. In short therefore, if the living beings are independent entities in the sense that their logic cannot be changed, then many of them would be eternal. If however they are not independent, then you cannot predict evolution.

      1. You are the one confused. I will walk you through your mistakes.

        It would be helpful to drop the religious filter entirely , since we are talking about science and natural facts.

        By switching back and forth your are engaging in Categorical errors which don’t apply.

        “You proved my point. ”

        It seemed like a refutation to me since the thing you claimed not to exist does indeed exist.

        “The point being that if the mutations are random,”

        I dont think that matters.

        “then some living beings”

        Stop right there. Thats your first mistake. Open a biology book.

        “Living Beings” are not anywhere in it. Youve just left Biology to venture into theology. Beings do not have mutations. Organisms do. Cells do.

        Organisms only have to be 1 cell.

        “will be eternal. ”

        You are still lost in Theology. There is no such thing as “eternal”

        The word you are looking for is “immortal” . Cancer cells are immortal.

        “Not long lived.Eternal. ”

        You think a random mutation is supposed to grant superpowers to outlast the heat death of the universe?

        “The fact that living beings”

        No such Biology term as “living being”

        “are dying due to cancer” The host dies which are not immortal.

        The cancer only dies because it starves to death. They are immortal and can live forever.

        Cancer isnt just the name of disease which kills, its the name of immortal cells that ARE cancerous.

        If you are posting that a mutation ought make cells immortal and magical and never need energy that isntbiology, its myth.

        “or in other ways, itself indicates that they are not eternal,”

        They are immortal, this is a fact. Look it up.

        “and therefore not randomly created.”

        Are you one of those people with an obsession about randomity. Its really not that important. Natural selection isnt random.

        “If you read the theorem posted in the essay, you will find why
        the eternal programs would abound in nature, if the process was random mutations.”

        Regardless of why, cancer is a common occurrence.

        “Natural selection doesn’t pick out such random programs, and
        becomes irrelevant.”

        Actually It does. You dont understand Natural Selection.

        Selection occurs on the gene level, the cells level, the Phenotype, the Organism, The Population AND its ecosystem as a whole.

        Its not just one thing. You are confusing the forests for the trees and vice-versa. Remove the Human Chauvinism. There are cells and orgamisms. Not beings.

        “The only way to end such living beings would be to end the entire ecosystem (i.e. power off the computer).”

        Thats not exactly what happens. Its called programmed senescence.

        You put a clock in every processor and limit how many cycles it can run before it autodestructs. You whole body works like this.

        Its why your hair turns gray. Your melanin cell took damage so your body turns it off or kills it , to prevent the possibility of cancer.

        You havent thought through all the implications of your own thoughts

        On the level of the cells , YOU are the ecosystem. The vast majority of cells in your body, arent even human.

        Now If a cells was an information processing machine ( it isnt really ) but if it was AND it was caught up in an infinite loop, what would be happening?

        Would that cell be doing all the functions it was phenotype for?
        Or would it just just focus on its infinite loop to the exclusion of all else? If its part of an ecosystem it can parasite off of, it can just focus on growth, division and immortality and its own loop and fuck all the other needs. Thats what cancers do.

        Canine Penile cancer is its own organism.

        The species its from , is extinct. Its gone. The cancer has outlived the organism and species it came from. Its not a modern mutation. Its about to kill off the Tasmanian Devil too.

        “if all HeLa cells ever grown could have been gathered on a scale, their total weight would have measured more than 50 million metric tons.”

        1. Now you are having a semantic issue about the difference between living being and organism, eternal and immortal. You are free to spend your time like this, I’m not going to.

          >> You think a random mutation is supposed to grant superpowers to outlast the heat death of the universe?

          You are putting words in my mouth. That isn’t my claim. It is the claim of Turing’s Halting Problem. You can try to create random programs, and run them. Compilation of those programs doesn’t ensure that they will actually halt. That’s the halting problem. There is no solution to that problem, as it is an instance of Godel’s Incompleteness proof.

          >> You put a clock in every processor and limit how many cycles it can run before it autodestructs. You whole body works like this.

          You have produced an “evil bit” argument. There is an internet joke that all “evil” data packets will set a bit to say that they are evil. Right. An evil program will selfdestruct. Think of a program that never autodestructs, and try to show how you are preventing that. Think of viruses, trojans, autobots, and such “evil” programs. You think every program is going to self-destruct? Happy thoughts.

          >> Actually It does. You dont understand Natural Selection.

          OK, let’s assume that I don’t. Why don’t you provide a mechanism by which every “evil” program will autodestruct? All governments will enforce that mechanism in computers to prevent the creation of evil programs. In fact, since you will figure out in the process when a program is evil, you might also add to the mechanism the step of never compiling that program into an executable. OK?

Comments are closed.