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

A friend w开发者_运维技巧ho 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?

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.

Have a look at the halting problem.

Isn't this just the halting problem?

There's no answer to the question. Program X does not exist. Alan Turing proved that:

There is no total computable function that decides whether an arbitrary program i halts on arbitrary input x

See proof here: http://en.wikipedia.org/wiki/Halting_problem

In summary, Alan Turing defined the halting problem as "given a description of a program, decide whether the program finishes running or will run forever". The question here though is what would be the output of this program if the input was the program itself. The reason why there is no actual answer to this question is that, as Alan Turing proved (see link in this answer), such a program does not exist: "there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x"

X has two inputs, so X(X) does not make sense, therefore X(X,X) does not make much sense either.

Which is ok, because X does not exist anyway (see other answers) :)

This sounds like the Halting Problem, and to answer your question, I believe it was Alan Turing who first discussed it (though I am not sure he actually called it "The Halting Problem").

The question suppose X exists, so:

Lets say that X is our "impossible" algorithm that informs if any other algorithm A finishes for a given input. If we supply X with X itself as the algorithm to analyze and a set of input Y to test in X, like:

X(X,Y)

We know that it will return true. Now, lets say that X receives as input X itself, which means,

Lets see if X ends when X is analyzing X... Which is true, since X can analyze anything. In other words, if X existed, then X(X,X) would be true.