What does it mean to pass the machine and it's description as the input in the halting problem?

33 views Asked by At

In the proof of the halting problem, why do we have to pass the machine and its description as an input?

For example, I could have passed the description of the machine and some other input(not the machine itself) and still the proof by contradiction would have worked.

For example, say H(a, b) gives an answer "yes" if a does halt on "b" and "no" otherwise.

Now we create another machine "H*" which does the opposite of what H does.

An H halt implies that H* goes into an infinite loop and H does not halt implies that H* halts.

Now instead of passing H(H*, H*); if I passed H(H*, X) then it would have meant that H* would halt if H* didn't halt on X and vice versa(still it would have been a proof by contradiction).

I don't necessarily see the idea of passing H(H*, H*) instead of just passing H(H*, X) for some X. Wouldn't the proof work in the latter case?

1

There are 1 answers

0
Peter Leupold On

For example, say H(a, b) gives an answer "yes" if a does halt on "b" and "no" otherwise.

Now we create another machine "H*" which does the opposite of what H does.

The point is that this is not always possible. As the halting problem shows, the recursively enumerable languages are not closed under complement. So for some of their complements no such H* exists, for example for the halting problem.

The problem in building H* is detecting when H goes into an infinite loop. There is no algorithm to do this. Nonetheless, H* could in principle exist; but the halting problem is one example of a set for whose complement you can prove that no enumerating TM can exist.

If the class was closed under complement maybe your argument would go through.