What is it that computers CAN’T do? A simple introduction to Turing’s Halting Problem

(This is the first in a series about computationally insolvable problems, with a focus on Turing machines and the halting problem)

As a modern society, we rely on faster and more powerful computers in greater and more diverse areas of our life with every successive generation. In fact, some people believe in (and are working hard towards) the possibility of a technological “Singularity” by the 2030’s, when artificial intelligence will have surpassed human intelligence sufficiently to recursively self-improve (eg. A slightly smarter-than-human AI will make an AI slightly smarter than itself, which will in turn improve its own design, etc) and when the future will become extremely difficult to predict.

But surely machines could never be intelligent and creative, you might say. Lady Ada Lovelace, who was history’s first “computer programmer” back in the 1840’s, did believe that “The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform.” This is a view commonly held by the public. On the other hand, there isn’t any kind of “magic” that we know of that takes place in the human brain. It’s just “the latest” that evolution has to offer. Being able to replicate human intelligence is, theoretically speaking, fully possible, with sufficient knowledge of neuroscience and lots of processing power. John von Neumann once gave what I consider the “paradox of AI skepticism”:

“You insist that there is something a machine cannot do. If you will tell me precisely what it is that a machine cannot do, then I can always make a machine which will do just that!”

(There are counter-arguments to this, based mainly on Godel’s incompleteness theorem and quantum physics. See links below).

The problem lies mainly in characterizing an adequate “solution space.” Put another way; consider the problem of finding the first 100 digits of pi, with pi being defined as the irrational number representing the ratio of a circle’s circumference to its diameter. At first glance, the problem obviously looks unsolvable. We have been given an extremely vague solution space about which we know little more than “the correct string of 100 numbers between 0 and 9.” Phrased that way, the problem does indeed seem impossible, until we begin to exploit the specificity of what pi is. Similarly, when we try to characterize human creativity, we list the solution space as “writing poetry and composing sonatas and painting.” It’s impossible until we know more information.

Of course, making that statement might imply ignoring the fact that we have somewhere around 100 billion neurons in the brain, each of which performs extremely specialized and diverse functions. And that’s just ignoring the countless levels of organization of our human brain.

But moving on.

Alan Turing, a brilliant British mathematician, and widely considered the father of artificial intelligence and in fact computer science in general, also believed in the possibility of reducing the brain to a description of a computer. And before proper computers actually existed, he was already working on what computers could never do. He came up with the halting problem, which reads:

Is there an algorithm which allows us to determine whether or not a given program will keep running forever, or whether it will terminate after a finite number of steps?

The answer is a resounding NO! That is unfortunate, since such an algorithm would allow us to mechanically solve a number of unproven statements in number theory.

The next post will introduce the concept of a “Turing machine,” an abstract construct which underlies today’s computers and provides a context for the discussion.

Further Reading:


“Computing Machinery and Intelligence” – Alan Turing

“Minds, Machines, and Godel” – J.R. Lucas


Godel, Escher, Bach by Douglas Hofstadter

The Emperor’s New Mind by Sir Roger Penrose


One Response to What is it that computers CAN’T do? A simple introduction to Turing’s Halting Problem

  1. Ian Hoke says:

    Also read Galatea 2.2 by Richard Powers. And then read everything else he’s written, starting with Three Farmers on Their Way to a Dance and working your way forward. I’m thinking he’s right up your alley. At any rate, Galatea takes an incredible look at a Turing test-style bet between AI folks, and it just delivers the goods by leaning heavily on Greek mythology and computer science – two great tastes that taste great together, believe it or not.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: