We have learned about the halting problem this week and, for the most part, everything has gone in one ear and out the other. Even referring to the course notes and reviewing the lecture notes did not really give me the confidence that I was actually comprehending what I was incessantly studying.
After I requested a last-minute office hour with one of the professors for the course (thank you thank you thank you thank you!!), I can now confidently say that I may or may not understand reductions and computability (haha). Okay, but no, seriously. I now have a much clearer understanding of the halting problem, and what we're trying to prove when we prove that halt is non-computable. I'm also more confident about reductions; where we prove that another function, F, is non-computable by reducing halt to the aforementioned function. In essence, we prove that a function is not computable by implementing a valid implementation of halt using the function F.
In disproving the the halting problem, we perform a proof by contradiction by assuming that the halt function is computable. After we construct a function that contradicts the halt function, we can use proof by cases to show that there exists a function that contradicts itself by halting when it doesn't halt, and doesn't halt when it's supposed to halt.
---Update--
Sadly, despite his excellent explanation and step-by-step guidance... I have come to realize that I still do not understand the halting problem.
No comments:
Post a Comment