The Halting Problem of Programs and of People

Pablo Nogueira

Updated: 19th July 2013

This is an English rendition of my post in Spanish El Problema de la Parada de los Programas y de las Personas which appeared on 27th June 2013 on the Alan Turing Year Blog of the Spanish national daily El País. A few additions to the Spanish version are enclosed within square brackets in the text.

Alan Turing proved in his celebrated undecidability theorem that it is not possible to write a computer program that can tell [i.e., that can ‘decide’] whether any arbitrary program either halts or hangs. This is the famous ‘halting problem’ for which there is no possible program.

Turing's theorem has important consequences for computer programming. In this post I will try to explain the theorem without using mathematics. Moreover, not to bore those who already know it, I will explain that it also applies to people, and that the famous debate about whether undecidability is what discriminates people from programs is unfounded (more details and references below).

The problem Turing wished to study was whether every mathematical function on numbers can be computed by a program. For that purpose, Turing first had to define what a program is, and thus invented his famous ‘machines’. We shall assume with no further comments that programs are those wonders that we install and use.

Let's begin by explaining what a mathematical function on numbers is. Here is an example:

‘Give me a number, and I return twice that number.’

A function will be for us a sentence that asks us to compute a number from another input number. The programmer's task will be to write a program that realises, i.e., computes, the function.

A program computes the function if the program returns twice the number given as input. For that purpose, the program could, for example, add the input number with itself, or multiply the input number by two, or multiply the input number by six and then divide the result of that multiplication by three, or as complicated as we wish, provided the program returns the correct result.

Functions can be as complicated as we wish:

‘Give me a number, and I return the square root of that number.’

‘Give me a number, and I return the cosine of the integral from that number to its square, of the sine of that number multiplied by three.’

Functions can be silly too, like this one:

‘Give me a number, and I hang.’

This function doesn't seem to be of much use, but we all know there is a program for it. It's used frequently by companies that develop operating systems for personal computers.

Here is a variation on that theme:

‘Give me a number, and if the number is even then I hang, otherwise if the number is odd then I don't hang, I return the number 7.’

It's easy to write a program for that function. First, the program has to divide the input number by two. If the remainder is zero then the input number is even, and so the program hangs, for example, by running the program that always hangs. However, if the remainder is not zero, then the input number is odd and so the program returns 7.

An essential ingredient on which the whole [undecidability] argument depends is that programs can be enumerated. That is, to every program there corresponds a [unique] number. The mathematical trick is typically called ‘Gödelization’ in honour of legendary Kurt Gödel, who also used the trick in his celebrated (and rather similar) theorem on the incompleteness of formal systems. Here we shall explain Gödelization the easy way: programmers write their programs using a text editor, so it's enough for them to click on ‘Save As’ and use a different number as file name for each program. Done.

We're now in a position to make the one-million question:

Do all functions have programs that compute them?

I'm afraid not — said Alan.

How?

Here is a function for which there is no program:

Give me a number, and if the program with that number does not hang then I return number 1, otherwise if the program with that number does hang then I return number 0.

This is the function that decides if another program does or does not hang, where 1 stands for ‘does not hang’ and where 0 stands for ‘does hang’.

However unlikely it may seem, we cannot write a program that computes that function. If we suppose we can, we end up in trouble. Let's see the details.

Let's suppose we can write the program. Then it follows that we can also write this other program:

‘Give me a number, and if the program with that number does hang then I do not hang (I return number 7), otherwise if the program with that number does not hang then I do hang.’

This is the ‘contrarian’ function, a function which doesn't seem to be of much use either. Some four-year-old little marquis I know tries to compute it every so often.

If there were a program for the contrarian function, such program would have a number, whatever it is. Let's suppose for the sake of argument that such number is 42, although any other number would do as well.

What happens if we give to program 42 the number 42 as input? Try it before reading the next paragraph.

It happens that program 42 does hang when program 42 does not hang, and that program 42 does not hang when program 42 does hang.

Impossible nonsense.

How come we've arrived at such nonsense? We have supposed that it's possible to write a program that decides whether another program hangs or does not hang. If we reject its existence, the nonsense's gone.

Let's now make it more interesting. In all the functions above replace ‘hang’ by ‘fall silent’, and replace ‘program’ by ‘person’. As they know in the civil service, every person is a number, an id or a passport number. If we re-read the argument again we have the Person Halting Problem: no person can tell whether an arbitrary person falls silent. Mr. 42 is in trouble. He falls silent while at the same time doesn't fall silent. There's no Mr. 42 capable of realising such feat.

Where's the gist?

In self-reference, which is present in a lot of nonsense, or ‘paradoxes’, some of which have given a lot.

Indeed, the argument is quite malicious: if program 42 exists then we arrive at a nonsense, so program 42 must not exist, and so there are functions without programs that compute them. Or in a different light, it's not possible for Mr. 42 to fall and not fall silent, so Mr. 42 must not exist, and so there are functions without people to realise them. But only because one person would then contradict itself!

The Program Halting Problem complicates the life of poor programs. It's not possible to write a program that decides if another arbitrary program halts or hangs. Therefore, it's also not possible to write a program that decides whether two arbitrary programs compute the same function, for what would the comparing program tell us if the programs it compares both hang? And similarly with people.

The whole matter is not about complicated maths but about logical paradoxes. Another famous paradox is the Liar's Paradox, the one about the Cretan who said ‘all Cretans are liars’. Can the reader decide whether the Cretan lies or not? Another very famous paradox is Bertrand Russell's, who noticed that the club whose members are those clubs with less than two members, is itself a club with more than two members, and therefore does not have itself as a member. However, there are clubs that have themselves as members, as for example the club whose members are those clubs with more than two members. Such a club has more than two members and therefore has itself as a member. Looping the loop, Bertrand asked himself whether the club made up of those clubs that do not have themselves as members, has itself as a member … and at that point he fell silent. This paradox and its resolution has had important consequences on the foundations of mathematics, logic, and computer programming. Another paradox of similar consequences is Kurt Gödel's version of the Liar's Paradox, embodied by his sentence ‘this sentence cannot be proven by a formal system’. A formal system that proves the sentence is proving falsehoods. A formal system that does not prove the sentence is not proving all truths, for it cannot prove that sentence, making the sentence true.

The Program Halting Problem [or more precisely, the ‘diagonal argument’] has been wielded as a case for the distinction between programs and people. I drop a few distinguished names [the ones I know and have read] in case the reader wants to look them up: John R. Lucas, Roger Penrose, C. H. Whiteley, Douglas Hofstadter, Solomon Feferman, Jack Copeland, Ron Chrisley, etc. I first heard about the ‘Person Halting Problem’ from Ron Chrisley, who kindly conceded that it is a variation of Whiteley's reply to Lucas. [Lucas used Gödel's incompleteness theorem to argue for the distinction between formal systems and people.] Whiteley's reply is to me the shortest, most direct, and most effective. [Whiteley showed that a paradoxical sentence can be constructed for whoever tries to realise it, be it a program, a formal system, a machine, or a person. Whiteley told Lucas that the sentence ‘This sentence cannot be consistently asserted by Lucas’ cannot be consistently asserted by Lucas.] I first read about [Lucas's argument and] Whiteley's reply in Douglas Hofstadter's famous book [Gödel Escher Bach, An Eternal Golden Braid]. For what's worth, here are some references: http://users.ox.ac.uk/~jrlucas/Godel/referenc.html.

[An informal generalisation of the Person Halting Problem is the ‘Can-Do-X Problem’. Let X be anything you assume a person can do. In the post I chose X to be ‘fall silent’. Now, there are people that cannot decide if an arbitrary person does X. The decision function without the person is ‘Give me a number, and if the person with that number does X then I return 1, otherwise if the person with that number doesn't do X then I return 0’. The contrarian function would be ‘Give me a number, and if the person with that number does X then I don't do X, otherwise if the person with that number doesn't do X then I do X’. There can be no Mr. 42 which does and doesn't do X at the same time.]

[To hang or not to hang, that is the question.]

[How many functions are susceptible of programs, that is the question, that is the experiment.]