Suppose someone claims that a particular Turing machine program halts when run on the blank tape. How can this claim be verified? The obvious answer is to run it on the blank tape and see if it halts. But what if the program in fact does not halt? The verifier will be stuck running a non-halting program, waiting forever for a halt that will never come.
