Free Will, Determinism and Turing’s Halting Problem


Home / Free Will, Determinism and Turing’s Halting Problem

Free Will: Do we have it, or do we not? Can math and computer science prove either way? Image by Marbleshoes

Do humans have free will, or do our brains generate our thoughts and decisions in a deterministic way? One MIT professor suggests that Alan Turing’s proof of the Halting Problem resolves this dilemma.

Free Will versus Determinism

Most of us feel that we have free will, or the ability to make choices. Part of that feeling comes from sometimes changing one’s mind while making a decision.

On the other hand, some scientists suggest that the human mind is an emergent phenomenon the brain generates in a deterministic way, acting according to the laws of physics. No matter to what degree physics may depend on stochastic processes in quantum mechanics, a “random” choice differs from a “free will” choice. If you make decisions by flipping a coin and heads always means “yes,” then that’s a deterministic process that includes a random input.

Philosophers may disagree on the topic of compatibilism by asking if free will and a deterministic universe are compatible. This article avoids that philosophical question.

MIT professor Seth Lloyd’s approach also avoids the philosophical argument; instead he asks why people feel that they have free choice.

Lloyd’s Indicator for Free Will versus Determinism

Lloyd proposes that we believe that we have free choice because other people do not predict our decisions. At least some of our decisions surprise some people, including ourselves, from time to time.

Let’s consider the opposite situation: Whose behaviour can we accurately predict? Perhaps those who have undergone hypnosis, and those with some psychological maladaptions such as obsessive-compulsive disorder. We label people who make predictable decisions as having specific problems. Likewise, when a stage magician’s mentalist trick of predicting a person’s answer creates a sense of awe and surprise, does that person lack free will?

Lloyd therefore suggests that a test for free will versus determinism involves predicting a person’s decisions accurately every time.

Lloyd: Suppose the Mind is Deterministic…

In brief, Lloyd suggests we assume, for this discussion, that determinism is correct. Therefore the brain follows a deterministic process to make a decision.

One may construct an algorithm, or set of rules, to describe this deterministic process. Even if modern science cannot know all the inputs and processes in the brain, future advancements make it theoretically possible.

Therefore, if humans make deterministic decisions, one might someday be able to replicate that process and predict a person’s every decision.

What is a Turing Machine?

Alan Turing defined several types of Turing Machine, or TM, which we now recognize as computers. These Turing Machines could solve precisely the same problems as some of the most sophisticated mathematical systems, including Kurt Gödel’s recursion theory and Alonzo Church’s lambda-calculus. TMs compute deterministic decision-making processes.

The Impossible Halting Problem

Turing programmed a Universal Turing Machine that could read any other TM program, and then follow those instructions to produce the same result as the target TM. Both would produce the same result, whether by reporting a final answer or by going into an endless loop.

Turing’s real goal was to program a Turing Machine to solve the Halting Problem: to predict accurately whether any target TM would halt or continue processing endlessly. This predictive Turing Machine must produce an accurate prediction and then halt. Unlike the Universal Turing Machine, it would be a failure if it simply computed endlessly. Turing proved the impossibility of programming such a predictive TM.

Suppose that one claims to program such a predictive Turing Machine. Then someone could program an “enemy” TM which incorporates the same capabilities. This enemy would determine what the predictive TM would predict about the enemy, and then do the opposite.

Leave a Comment