The Answer Man

Thanks! Looking at the number of views, it's not one of the more popular ones.  Perhaps it's because of the bad pun at the end.

That's a good point. However, it's not so simple to rule out programs referring to themselves. They might refer to themselves indirectly via another program or not to themselves at all, but to a near-copy. There are also ways of defining incomputable problems where the reference is not internal to the programs themselves but indirectly through the problem definition, such as the Busy Beaver problem.

I always wondered what the halting problem's result is. Is it that it's impossible to code the halting problem or that it's impossible to code the halting problem which is always correct? What does the contradiction mean?

You can write a program that solves the halting problem SOME of the time, but not ALL of the time. So, there will always be some inputs for which your program will either not halt or give a wrong answer.

Not halt? How do you arrive to that conclusion?

Someone in my class found it helpful to realize that what makes the halting problem impossible is that it must be able to predict if ANY program will halt. If it's allowed to opt out for some programs (like ones that refer to themselves!), it's not necessarily impossible anymore. The analogy in the video is that the Answer Man might bet that he can tell who will use salt, as long as that person doesn't hear his prediction.

Michael decides to do the following: he asks the Answer Man what he thinks. Knowing answer, he will do just the opposite. If the Answer Man has a sure answer for everyone, Michael's behavior is well-defined. However, this cannot be the case as can be easily seen: If the Answer Man would predict that Michael is not going to use salt, he would use salt and vice versa. Thus, we must conclude that there is no Answer Man. I hope this helps.

Michael: Great video!