# Not understanding this way of proving undecidability of the termination problem

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?

## 1 Answer

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!