The Halting Problem and Human Behavior

The "halting problem" considers whether or not it is possible to write a function that takes as input a function Pn and the inputs to Pn, Pin, and provides as output whether or not Pn will halt.

It is obvious that the function
(defun P1 ()
"Hello, World!")
will return the string "Hello, World!" and halt.

It is also obvious that the function
(defun P2 ()
never halts. Or is it obvious? Depending on how the program is translated, it might eventually run out of stack space and crash. But, for ease of exposition, we'll ignore this kind of detail, and put
P2 in the "won't halt" column.

What about this function?
(defun P3 (n)
(when (> n 1)
(if (evenp n)
(P3 (/ n 2))
(P3 (+ (* 3 n) 1)))))
Whether or not, for all N greater than 1, this sequence converges to 1 is an unsolved problem in mathematics (see
The Collatz Conjecture). It's trivial to test the sequence for many values of N. We know that it converges to 1 for N up to 1,000,000,000 (actually, higher, but one billion is a nice number). So part of the test for whether or not P3 halts might be:
(defun halt? (Pn Pin)

(if (and (is-program Pn collatz-function) (<= 1 Pin 1000000000))
But what about values greater than one billion? We can't run a test case because it might not stop and so
halt? would never return.

We can show that a general algorithm to determine whether or not any arbitrary function halts does not exist using an easy proof.

Suppose that
halt? exists. Now create this function:
(defun snafu ()
(if (halt? snafu nil)
halt? says that snafu halts, then snafu will loop forever. If halt? says that snafu will loop, snafu will halt. This shows that the function halt? can't exist when knowledge is symmetrical.

As discussed
here, Douglas Hofstadter, in Gödel, Escher, Bach, wrote:

It is an inherent property of intelligence that it can jump out of the task which it is performing, and survey what it is done; it is always looking for, and often finding, patterns. (pg. 37)

Over 400 pages later, he repeats this idea:

This drive to jump out of the system is a pervasive one, and lies behind all progress and art, music, and other human endeavors. It also lies behind such trivial undertakings as the making of radio and television commercials. (pg. 478).

This behavior can be seen in looking at the halting problem. After all, one is tempted to say, "Wait a minute. What if I take the environment in which
halt? is called into account? halt? could say, 'when I'm analyzing a program and I see it trying to use me to change the outcome of my prediction, I'll return that the program will halt, but when I'm running as a part of snafu, I'll return true. That way, when snafu is running, it will then halt and so the analysis will agree with the execution.' We have "jumped out of the system" and made use of information not available to snafu, and solved the problem.

Except that we haven't. The moment we formally extend the definition of
halt? to include the environment, then snafu can make use of it to thwart halt?
(defun snafu-extended ()
(if (halt? snafu-extended nil 'running)
We can say that our brains view
halt? and snafu as two systems that compete against each other: halt? to determine the behavior of snafu and snafu to thwart halt?. If halt? can gain information about snafu, that snafu does not know, then halt? can get the upper hand. But if snafu knows what halt? knows, snafu can get the upper hand. At what point do we say, "this is madness?" and attempt to cooperate with each other?

I am reminded of the words of St. Paul:

Knowledge puffs up, but love builds up. — 1 Cor 8:1b


The No Free Will Theorem

In one sense, I'm not ready to write this post; my subconscious mental machinery is still working to sort out all of the ideas in my head. But after not having done any reading for the past few weeks, before bed I picked up where I left off reading Pierce's An Introduction to Information Theory. But I had stopped in the middle of a paragraph, decided I needed to go back to the beginning of the chapter, tried to make progress, and gave up. So I switched to where I had set aside The Best of Gene Wolfe and resumed with the story The Death of Dr. Island. A passage that I will quote later caused a cascade of, if not pieces falling into place, a clarity of what questions to think about.

Earlier this week, over at
Vox Popoli, Vox took issue with a particular scientific study that concluded on the basis of experimental data that free will does not exist. While I think I agree that this study does not show what it claims to show, I nevertheless took the approach the free will doesn't exist. The outline of a proof goes like this.

Either thought follows the laws of physics, or it does not. X or ~X. I hold the law of non-contradiction to be true. Now, someone might quibble about percentages: most of the time our thoughts follow the laws of physics, but sometimes they do not. But that misses the point.

Why would anyone suppose that our thoughts don't follow the laws of physics? Perhaps because of an idea that thought is "mystical" stuff; that there is a bit of "god stuff" in our heads that gives us the capabilities that we have. If this were so, since the Christian God transcends nature, our thoughts would transcend nature. It's how we would avoid non-existence upon physical death: the "soul" which is made of "god stuff" returns to God. Perhaps it's due to not knowing how thinking is accomplished in the brain. What I'm about to say certainly isn't taught in any sunday school I've ever attended, or been discussed in any theological book I've ever read. While that may be because I don't get out enough, I suspect my experience isn't atypical. Another, more general reason, is because that's the way our brains perceive how they operate. It's the "default setting," as it were. Most people, regardless of upbringing, think they have free will. I think I can explain why it's that way, but that's for another post.

How does one prove that thoughts follow the laws of physics? The ultimate test would be to build a human level artificial intelligence. I can't do that. The technology isn't there. Yet. The best I can do is offer a proof of concept. I maintain that this is better than what the proponent of mystical thought can do. I know of no way to build something that doesn't obey the laws of physics. By definition, we can't do it. So any proof would have to come form some source from outside nature held to be authoritative. In my world, that's typically the Bible. There is no end of Bible scholars who hold that Scripture teaches that man has free will. It doesn't, but my intent here is to make may case, not refute their arguments. Although I acknowledge that it certainly wouldn't hurt to do so elsewhere.

What is thought? Thought is matter in motion in certain patterns. This is a key insight which must be grasped. The matter could be photons, it could be water; in our brain it is electrons. The pattern of the flow of electrons is controlled by the neurons in our brain, just like the pattern of the flow of electrons is controlled by NAND gates in a computer. While neurons and NAND gates are different in practice, they are not different in principle. NAND gates can simulate neurons (there are, after all, computer programs that do this) and neurons can simulate NAND gates (cf.
here). Another way to view this is that every time a programmer writes computer software, they are embedding thought into matter. I've been programming professionally for almost 40 years and it wasn't until recently that I understood this obvious truth. But if this is so, why aren't there intelligent computers? As I understand it, there are some 100 billion neurons in the brain with some 5 trillion connections. Computers have not yet achieved that level of complexity. Can they? How many NAND gates will it take to achieve the equivalent functionality of 5 trillion neuron connections? I don't know. But the principle is sound, even if the engineering escapes us.

Humans are governed by the laws of quantum mechanics, just as computers are. Having just re-watched all four seasons of
Battlestar Galactica on Netflix, it was fascinating to watch the denial of some humans that machines could be their equal, and the denial of some machines that they could be human. In the season 4 episode No Exit, the machine's complaint to his creator "why did you make me like this," is straight out of Romans 9. Art, great art, imitating life.

However one cares to define the concept of "free will," that definition must apply to computers as equally as it does to man. The same principles govern both. As long as it meets that criteria, I can live with silly notions of what "free" means. "You are free to wander around inside this fenced area, but you can't go outside" is usually how the definitions end up. I think limited freedom is an oxymoron, but people want to cling to their illusions.

There is so much more to cover. If our thoughts are the movement of electrons in certain patterns, then how is that motion influenced? What are the feedback loops in the brain? What is the effect of internal stimuli and external stimuli? Is one greater than the other? The Bible exhorts the Christian to place themselves where external stimuli promotes the faith. The dances of their electrons can influence the dance of our electrons. Can we make Christians (or Democrats, or Atheists, or…) through internal modification of brain structures through drugs or surgery? How does God change the path of electrons in those who believe versus those who don't? Would God save an intelligent machine? Could they be "born again"? Does God hide behind quantum indeterminacy? So many questions.

In April 2009, I wrote the post
Ecclesiastes and the Sovereignty of God, which gave excepts from the book A Time to Be Born - A Time to Die, by Robert L. Short. Using the Bible, in particular the book of Ecclesiastes, Short reaches the same conclusion I do arguing from basic physics.

The universe controls us. We do not control the universe.

This brings me to the Gene Wolfe quote mentioned at the beginning of this post:

This is what mankind has always wanted. … That the environment should respond to human thought. That is the core of magic and the oldest dream of mankind…. when humankind has dreamed of magic, the wish behind the dream has been the omnipotence of thought.

[to be continued]

Atheism: It isn't about evidence

[Updated 5/7/2011, 10:49:05 PM; then 5/13/2011, 8:03:53PM]

On the first of the year I wrote "
Cybertheology" to begin the long process of using science, particularly computer science, evolutionary biology, and game theory to give evidence for and provide understanding of God. After all, I believe that the God who reveals Himself in the spoken and written Word also speaks through nature -- and that the message must be the same in both. In 2009 I wrote "Evidence for God" which gave my reaction to one atheist's claim of the lack of evidence for God. Over at John Wright's blog, another atheist commenter recently claimed again that there is no convincing evidence for God.

I have now come to the conclusion that a consistent rational atheist cannot claim that evidence, or the lack thereof, is the issue at all. The proof is really very simple and builds upon ideas in the earlier post "
Bad Arguments Against Materialism."

Every argument should have well-defined terms. Defining "God" is surprisingly hard. Traditionally, Christianity has said that God is immutable and omniscient; however, an
Open Theist would disagree with these characteristics. Some argue that God is inherently good; otherwise would say that the existence of evil disproves this notion (and this latter group is wrong, but that's not the topic of this post). The notion of "creator" is sufficient for now. Materialism has to conclude that matter in motion is the source of the idea of God -- "god" is an emergent property -- just like the number i is an emergent property (to the best of my limited knowledge of physics, one can't point to the square root of -1 apples or protons). Theism holds that matter is an emergent property of God and, therefore, God must be immaterial. One side holds that God is the product of man's imagination; the other says that man's imagination is the product of God.

Tangentially related to this is the question of how to recognize the existence of and the reason for singular events, such as Creation or the Resurrection. As will be shown, this reduces to differences in brain wiring.

If a creator God does not exist, then nature must consist solely of matter in motion. In particular, our thoughts arise from the movement of matter in certain patterns and our thoughts must obey the laws of physics. The laws of physics themselves are simply descriptions of how matter moves in relation to other matter. A description is just matter in a different dynamic relationship to other matter. Some theists may reject this idea and state that there is a supernatural aspect to thought, but the atheist has no such recourse. Computers, goldfish, and human minds work via electrons in a silicon, or carbon, matrix. The complexity of thought depends on the arrangement of atoms in the brain (or CPU).

The key insight is that evidence is simply atoms that are external to the brain; different brains process the same data differently. There is a reason why we don't discuss theology with goldfish, golden retrievers, or computers: their brains don't have enough particles in the right configuration. The same principle applies to the atheist and the agnostic. When they say, "the evidence isn't convincing," what they really mean is "the atoms in my brain don't process the external data the way yours does."

The observation that brain states can be changed due to external factors (memory is "simply" state changes in the brain) doesn't help. Either the brain actively causes brain states to change based on how the brain processes the data, or there is some effect where the brain is passively changed. In the first case, the brain's wiring affects the brain's wiring, so the data is irrelevant, because different brains process the same data differently. The external data just shows how the brain is wired. In the second case, the external data changes the brain. The brain isn't evaluating evidence in the sense of the claim that the "evidence isn't convincing." Instead, the correct view is "my brain is/is not capable of being changed by the external world in the same way as other brains."

Since the external evidence is the same for both theist and atheist, the difference is in the way brains process that data. Given the way most human brains work (cf.
The Mechanism of Morality), we ask "which arrangement of atoms is better?"

The rational atheist must answer, "that which results in reproductive advantage." The problem for the atheist at this point is that theists have more children than atheists. Even though atheism appears to be on the rise, population in general is on the rise. In relative numbers, the atheists are losing ground. Writing in "
The Source of Evangelism" (atheist evangelism), Vox Day said, "... their own children are converting to religion faster than religious children are converting out of it."

We have evolved to think in teleological terms. As
this study showed, people with Asperger's typically don't ascribe intention or purpose behind the events in their lives. Atheists, on the other hand, can reason teleologically, but they reject those explanations. It isn't evidence -- it's wiring. The atheist can't come out and say that their brains are wired better than the theists, for at least two reasons. First, it isn't supported by the demographics. Again quoting Vox Day, "But the demographic disadvantage means that the atheist community has to keep all of their children within the godless fold and de-convert one out of every three religious children just to keep pace with the growth of the religious community." Second, it isn't supported by reason. After all, materialism is a strict subset of theism. The theist can think everything the atheist can -- and more. The theist has a bigger "universe" in which to think.

One explanation for this demographic disparity may be found in the difference between brains wired to recognize the existence of a creator God and those that are not. In the Abrahamic religions, the creator God is strongly identified with life. For example, the Jews were told by God, "Choose life so that you and your descendants may live..." [De 30:19]; Jesus said, "... have you not read what was said to you by God, ‘I am the God of Abraham, the God of Isaac, and the God of Jacob’? He is God not of the dead, but of the living.” Christianity asserts that death is an "enemy" -- the last enemy to be overcome [1 Cor 15:26]. Certainly, one doesn't have to reject the idea of a Creator God to reject life; but in my limited experience it sure seems that social battles of abortion, homosexuality, and euthanasia, are drawn with a line generally between secular and religious. The side that places a premium on reproduction will outproduce those that do not.

If the atheist can't say that their brains are wired better than theists, they also won't say that their wiring is worse. That would totally defeat their arguments. Therefore, they adapt a form of protective coloration wherein they deflect the issue to be external to themselves -- the evidence -- when it clearly isn't. Adopting protective coloration against one's own species may be another reason for the reproductive disadvantage of atheists. After all, this is a form of defection against the larger group and, as Axelrod has shown, an evolutionary strategy to maximize reproductive success is to defect in turn.

It appears that the atheist cannot win. If God does exist, they are wrong. If God exists only in man's imagination, evolution has wired man so that the idea of God gives a direction toward reproductive success. The attempt to remove God from society will result in demographic weakness.
Shiny secular utopias simply don't exist.2

[1] After posting this in the morning, in the evening I started re-reading
Gödel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter. Via seemingly different paths we have come to similar conclusions. On P-4 he writes:
  As I see it, the only way of overcoming this magical view of what "I" and consciousness are is to keep reminding oneself, unpleasant though it may seem, that the "teetering bulb of dread and dream" that nestles safely inside one's own cranium is a purely physical object made up of completely sterile and an inanimate components, all of which obey exactly the same laws as those that govern all the rest of the universe, such as pieces of text, or CD-ROMs, or computers. Only if one keeps on bashing up against this disturbing fact can one slowly begin to develop a feel for the way out of the mystery of consciousness: that the key is not the stuff out of which brains are made, but the patterns that can come to exist inside the stuff of a brain.
  This is a liberating shift, because it allows one to move to a different level of considering what brains are: as
media that support complex patterns that mirror, albeit far from perfectly, the world...
[2] On 5/12, posted the article "Religious belief is human nature, huge new study claims". In this article, Oxford University professor Roger Trigg, is quoted as saying "The secularization thesis of the 1960s - I think that was hopeless."

Christian Doctrine, Ancient Egypt, Game Theory

I am slowly making my way through the book Old Testament Parallels by Matthews and Benjamin.

The story “The Farmer and the Courts of Egypt” tells the story of a farmer who is unfairly accused by an official who tries to steal the farmer’s goods. The farmer pleads his case and demands justice. Somewhat reminiscent of the much longer book of Job, it was written around 2134-2040 BCE.

Two passages stand out. The first reads:

Good example is remembered forever. Follow this teaching: “Do unto others, as you would have others do unto you.”

This is the golden rule, over two thousand years before Christ.

The second passage says:

Do not return evil for good...

Proverbs 17:13 says, “Evil will not depart from the house of one who returns evil for good.” Proverbs was likely written after 400 BCE. I find this link to Egyptian thought to be extremely interesting and wonder why I haven’t seen more recognition of this in “mainstream” Christianity. A subsequent post, which has been a very long time in coming, will explore the influence of Egyptian thought on Genesis, the story of Noah, and the Exodus.

In terms of game theory and the Prisoner’s Dilemma, “do not return evil for good” translates to “don’t defect after cooperation.”

Both St. Paul and St. Peter write, “Do not repay anyone evil for evil...” [Rom 12:17, 1 Peter 3:19], which becomes “don’t defect at all.”

A future blog post will have to examine the implications of the Christian response to the Prisoner’s Dilemma versus the evolutionarily robust “tit-for-tat” strategy in



I had wanted to title this post “A New Word for a New Year”, but cybertheology is already being used. A very superficial survey shows that it is typically used to describe how people use the internet in relation to theology. I want to use the term to describe a scientific discipline with the focus of discovering and understanding God. As a Christian, I hold that God has spoken to us through His prophets and, ultimately, His Son (Heb 1:1-2). But the God who reveals Himself through the written and spoken Word, has also revealed Himself in nature (Rom 1:20). I contend that there will be no conflict between Nature and Theology, but that the scientific study of Nature can be used to inform theology, and theology can be used to inform science. I propose that cybertheology be where these two disciplines meet.

I use the “cyber” prefix because of its relation to computer science. Theology and computer science are related because both deal, in part, with intelligence. Christianity asserts that, whatever else God is, God is intelligence/λογος. The study of artificial intelligence is concerned with detecting and duplicating intelligence. Evidence for God would then deal with evidence for intelligence in nature. I don’t believe it is a coincidence that Jesus said, “My sheep hear my voice” [John 10:27] and the Turing test is the primary test for human level AI.

Beyond this, the Turing test seems to say that the representation of intelligence is itself intelligent. This may have implications with the Christian doctrine of the Trinity, which holds that “what God says” is, in some manner, “what God is.”

I also think that science can inform morality. At a minimum, as I’ve tried to show
here, morality can be explained as goal-seeking behavior, which is also a familiar topic in artificial intelligence. Furthermore, using this notion of morality as being goal seeking behavior, combined with John McCarthy’s five design requirements for a human level AI, explains the Genesis account of the Fall in Eden. This also gives clues to the Christian doctrine of “original sin,” a post I hope to write one of these days.

If morality is goal-seeking behavior, then the behavior prescribed by God would be consistent with any goal, or goals, that can be found in nature. Biology tells us that the goal of life is to survive and reproduce. God said “be fruitful and multiply.” [Gen 1:22, 28; 8:17, 9:1...] This is a point of intersection that I think will provide surprising results, especially if Axelrod’s “Evolution of Cooperation” turns out like I think it will.

I also think that game theory can be used to analyze Christianity. Game theory is based on analyzing how selfish entities can maximize their own payoffs when interacting with other selfish agents. I think that Christianity tells us to act selflessly -- that we are to maximize the payoffs of those we interact with. This should be an interesting area to explore. One topic will be bridging the gap between the selfish agents of game theory to the selfless agents of Christianity. I believe that this, too, can be solved.

This may be wishful thinking on the part of a lunatic (or maybe I’m just a simpleton), but I also think that we can go from what we see in nature to the doctrine of justification by faith.

Finally, we look to nature to incorporate its designs into our own technology. If a scientific case can be made for the truth of Christianity, especially as an evolutionary survival strategy, what implications ought that have on public policy?