The Unsolvable Problem

Note: This post covers Week 12 (There was no class during Week 11),

Since the most difficult concept always gets introduced in the last class before the exam, this week we explored the Halting problem. Essentially, we were asked to create a function halt that predicts whether or not a function would halt, or stop (a task we soon proved was impossible). I generally wouldn't complain that we had proved a problem impossible, intuitively that would mean that we wouldn't have to try to solve it. Unfortunately, for halting problems, we have to prove whether a function is computable or not by attempting to reduce it to a halt function (since halt is not computable, if a halt function can be written using a function f, that function is not computable).