What is the result of X(X,X)?

Question

A friend who studies pure mathematics ask me to think about the following problem.

Suppose that there is an algorithm named X that has 2 inputs: A and a_1...a_n, where 'A' stands for an arbitary algorithm and 'a_1..a_n' are inputs of A. X receives A and its inputs and returns true if A with a_1..a_n could be terminated, and false if A with a_1..a_n inputs fall into an infinite loop (never ends). Like this:

A(n):
   while(n<5):
      write "I'm immortal!"

and the result of X(A,6) is true and X(A,2) is false.

So what is the result of X(X,X)?

Also, do you know who was the first to introduce this problem?

edited after one hour thinking in depth : could you see something equivalent to Russel paradox here?

Answer 1

If it exists, it returns true. Proof: Suppose it returns false. Then it falls into an infinite loop and never ends. This is a contradiction.

But rather more interesting is the program Y which can be derived from X, and which halts if and only if its parameters don't halt. Then Y(Y,Y) yields a contradiction: either it halts (meaning that it doesn't halt), or else it doesn't (in which case it does). Hence X doesn't exist. Details omitted, for example we've waved our hands a bit as to whether X and Y take one parameter or two.

The issues related to the question were under discussion in the 19th century: David Hilbert's 10th problem (asked in 1900) asks for an algorithm to determine whether any given diophantine equation has a solution. With hindsight, this can be expressed as a special case of the halting problem: find an algorithm to determine whether a brute force search for a solution halts or not. So X would solve the 10th problem, but the non-existence of X left the 10th problem open. It was finally closed in 1970, after 20 years of work by Martin Davis, Julia Robinson, Yuri Matiyasevich and others. Hilbert fully stated the "Entscheidungsproblem" in 1928, which is the same idea the halting problem, but for testing whether statements in arithmetic are true, rather than testing whether programs halt.

I think Alan Turing invented the terminology necessary to state the halting problem as you have, and proved the result (1936). But Alonzo Church had proved the existence of undecidable problems in lambda calculus (also 1936), and Kurt Goedel's incompleteness theorems (1931) did so much groundwork that using his techniques to get those computability results out was probably a lesser achievement in both cases than formulating the problems had been (i.e. inventing lambda calculus and the Turing computing model).

Relevance to the Russell Paradox (1901): yes, the proofs have something of the same shape to them. In both cases, you consider an object which represents a predicate evaluated on a class including the object itself ("set of all sets, program which acts on programs"). You assume its existence, allowing you to construct a new object by modifying the predicate ("set of all sets which are not members of themselves, program which halts if and only if its input does not halt"), yielding a contradiction when you try to evaluate the new predicate "applied to itself". This disproves the premise ("there exists a set of all sets", "there exists an algorithm to test halting").

It's possible that there's something in Topos theory (or other structural analysis of mathematics) which formalises the similarity, but I don't know what that would be.

There's a significant practical difference between the results, though: the non-existence of X merely proves that the halting problem isn't decidable by an algorithm, so if you're David Hilbert you have to re-evaluate your expectations of what is possible in mathematics. The Russell Paradox proved that the theories of sets in use at the time were inconsistent, so if you're Georg Cantor you have to re-evaluate every proof you've ever written. This provoked the first formal axiomatic set theories, and re-statements of the work of Cantor, Dedekind and other set theorists, who had been working with naive definitions of sets that admitted the paradox.

Answer 2

Have a look at the halting problem.