Week 12: Final Remarks

    So this is the final week of the course before exam time, and hence the last slog. It's gone by quite fast but I learned a lot of new things and really found the experience quite valuable. I think, of the many courses I've done at this university, the concepts learned here will probably stick with me a lot more since they really introduced me to new ways of thinking and understanding problems.

   Anyways, I'm going to be talking about computability since I didn't touch on it last week and it's the final lesson of this class. As far as all the concepts I've learned in this course have gone, this is by far the most abstract and confusing to me. Of course, I've had past challenges with other things in this course, but I always felt that they made sense, but I just needed to do the practice and readings to develop a good intuition to solve them. This, however, takes some more time I think. Either way, I think it's a very interesting topic and I'll do my best here to explain what I've understood from lecture, course notes, and some videos I've been watching on the subject.
    First off, the definition of computability is that a function f is computable if for all inputs possible for the x, it will return the value of f(x). In other words, will the function halt (not end up in an infinite loop). Halting doesn't necessarily mean the function has to return some value you can work with. The function crashing is still considered halting if the input x doesn't satisfy function f. This definition only applies to functions that are well-defined though, or in other words, if we can say what f(x) is for every x in some domain.

So, we were shown in class how the halting problem was proven to not be computable. That wasn't too tricky. The trick is how to prove using reduction. It takes a while to understand what the reduction code is doing in the first place, and how to write it. Other than that, how is this written as a proof? Is it just writing out the function and if the implementation is right then it's proven, or is there more to do? I've been doing some research and getting vague answers, but hopefully I'll get it soon.