Not understanding this way of proving undecidability of the termination problem

Question

I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following:

– Assume termination(P) always terminates and returns true iff P always terminates on all input data;

– The following program yields a contradiction

while termination(P) skip; 

But I do not see what kind of contradiction there. Any idea?

Answer 1

This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain this remarkable and beautiful argument, from many viewpoints.

Still, to answer your question: denote by $Q$ the program you describe. Then $Q$ is a valid program, that takes as input another program $P$, and works as above.

Now ask yourself - what would $Q$ do if you gave it its own encoding $Q$? Would it terminate or not?

• If $Q$ terminates when given $Q$, then the "while" condition would stay true, meaning $Q$ would not terminate when given $Q$, but this is a contradiction.
• If $Q$ does not terminate when given $Q$, then the while condition is false, so $Q$ does terminate when given $Q$, which is again a contradiction.

Therefore, a procedure such as "terminate" cannot exist.

Again, I cannot stress this enough -- read this proof elsewhere, watch youtubes of it, read textbooks. It's one of the most fundamental and exciting results in computer science!