Sunday, November 30, 2014

Halting Problem problems



Lately I feel as if I’m falling a little behind in this class. I’ve gotten a bit of a grasp on Big O and such, but the halting section still confuses me. I’ve spent a whole day looking at videos, reading class notes, and looking at the slides, but I don’t feel like they explained things fully. For example, in the slides, it says that “if a function is well defined…” What does “well defined” mean? I’ve tried looking it up, and the explanations seem more complicated than anything I’ve seen before. Also, the part about how one function reduces to another still confuses me. On the third assignment, there is a hint to question six where it says to reduce the halt function to prove that the function is non-computational. In the notes, there was a slide explaining how one, “f” function reduces to another, “g”, but I was never sure which of the two functions halt falls into. Does the function reduce to halt, or does halt reduce to the function?
But the most confusing part of the whole section was that for non-computational functions, we know what x to put in to get the output, but we don’t know how it works? Of course we do! We have the code right there! If our human brain can look at the function and determine the input and corresponding outputs, doesn’t that mean that we just computed it in our head? Therefore, computable?

I guess I'll have to look at more material and watch some more videos to try to figure this out before our assignment is due.

1 comment: