The Answer Man

A Schoolhouse Rock-style video that presents the halting problem and computability. Created for use in an introductory computer science class at Rutgers University (NJ, USA). Tune: Piano Man by Billy Joel

Category:

Howto & Style

Tags:

• schoolhouse
• rock
• halting
• problem
• computability
• piano
• man
• billy
• joel

[kewlman139]

i had your class 2 semesters ago and for some reason, of all the videos you showed us, i liked this one the most. it's funny to see all the contradictions you point out

[mlittman]

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.

[mtanti87]

Did Turing ever say anything about programs which don't refer to themselves? I think that's the source of all contradictions in mathematics...

[mlittman]

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.

[mtanti87]

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?

[mlittman]

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.

[joshcena33]

Was every example some sort of contradiction? I only got the speaking ones... was the barber one some sort of contradiction? Also all the others? Lol.

[mtanti87]

Not halt? How do you arrive to that conclusion?

[CsSzepi]

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!

[mlittman]

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.