1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.