Hey guys, how are you all doing? Hope you did better than me during this week 11 because I was confused on many occasions during this week. But there's no use in telling you this week was hard without telling you why is there? So as always this is Kyle checking in to bring u guys a week round up of week 11 of CSC165. With only a week remaining before the end of classes I thought I had all the concepts of this course figured out and that I was ready to do well on the final. Then I got introduced to halting and computability. I think this might have been the hardest week for me personally, just because I've never felt as lost during this course as I did this week. With that being said, let's get into the details.
This week didn't start off that badly, so it wasn't completely overwhelming. We started off by simply identifying that not all problems have an algorithm that can be used to solve them and looked at examples of such problems. This was simple enough because we looked at a python code that when executed would not return control to the user. This was relatively easy to understand because I am familiar with python. We then found that there was no way to implement a function that could return true when another function passed in as a parameter would halt and false otherwise. If this was to be used in another function that used function f as a parameter and would pass if the halt function on function f returned true and return 42 if the halt function returned false the result would be that this function would only halt when it didn't halt, which is a contradiction. To prove the non-computability of a function, proof by contrapositive would have to be used. This proof almost always involved the halt function as part of the implication. Unfortunately to this day I still don't completely understand how to completely prove the non-computability of a function. I had gotten the structure down after looking at the course notes but more studying is needed, possibly looking at sample proofs for non-computability. We wrapped up the week by talking about countability, and how a set of numbers could only be properly counted if the counting was 1-1 and onto, to ensure there was no over counting and under counting, respectively. We also found that two infinite sets of numbers are not always equal, meaning, strangely, that infinity does not equal infinity all the time. the size of two sets can be different even if both containing more elements than any number. I was able to grasp this concept after closely listening to Danny along with rereading the annotated slides when they were posted, though it took quite a while. We also found that some infinite sets like the natural numbers, even natural numbers, and rational numbers were countable because could be counted 1-1 and onto. Finally, we ended the last lecture with an intriguing statement, that not all sets are countable, and that a mathematician named Cantor would show this using diagonalization, But that would be for next week.
Well I think that might have been the one of the longest wrap-ups I have ever done for this course. As you can see, it took a lot for me to even mildly understand these concepts and there is still much work to be done. But with only 2 weeks till the final exam it definitely is crunch time. Of course, just because I personally found this week difficult doesn't mean you all did. Comment below how you felt about this week and if I am over-complicating these concepts and I should just relax when studying computability and countability. Also, let me know how all of you are feeling now that the term is almost over. Its been a crazy week, but that's to be expected. As always, words are hard, comp-sci is awesome, and later days. This is Kyle signing out.
No comments:
Post a Comment