Wednesday 3 December 2014

Week 12: Computability and Countability Continued

Well the time is here guys, it's the last week of official classes is here. This also means that this is the last weekly report that I will be making. It has been an adventure making all these blogs and even though it is a required part of the CSC 165 curriculum, I will admit that I had fun making some of these entries. So, let's make this last weekly roundup a good one. This is Kyle Mendoza checking in for one last time to bring you guys a weekly report for week 12 of CSC165. During this week we continued our studies on computability and countability, or lack thereof in our case. We focused on identifying non-countable sets and non-computable functions more than anything else this week, starting with explaining why the set of natural numbers and the set of rational numbers are countable while the set of real numbers is not. We also briefly went over proof by induction to wrap up the week and the term. So with all that said, let's get into it.

During the first part of the week, we continued learning about countability and now addressing why certain sets are not countable. We discovered that for a set to be countable it also had to be listable, meaning that each value of the set had a position that would correspond to some element of the set of natural numbers. Cantor, a mathematician, proved that real numbers could not be listable and thus, were not countable. Cantor essentially stated that no matter what you do to try and list the real numbers between 0 to 1, you will always omit an entry if you take '0.' and traverse the diagonal adding 1 to the digit if the digit is less than 5 and subtracting 1 if the digit is 5 or greater. This proved to be true as multiple entries was seen to be omitted. This means that the set of real numbers from 0 to 1 is larger than the set of natural numbers, which is mind blowing. It took me a lot of re-reading and answers to questions provided by my peers in order for me to fully understand this idea. Next we explored diagonalization, an idea that can help identify functions that are not computable. Essentially, list the infinite countable python functions as well as whether they halt or loop when passed into each other as arguments and traverse the diagonal of the result, toggling the values from halts to loops and loops to halts and create a hypothetical function that cannot exist on such list. Finally we wrapped up by exploring proof by induction, another method of proof that we can use in our proof structures. I'm not sure if I will be using this proof in the final exam, simply because I don't completely understand it, but who knows, maybe after studying it prior to the exam I'll find that it makes a lot of proofs a lot easier. With that being said, there's nothing much I can say about induction other than it's just another weapon I can add to my arsenal when tackling proofs once I learn how to use it effectively and efficiently. To end the week we finished with a problem solving session about finding the number of squares that a diagonal can pass through in a rectangular grid.

So, this is it guys, this is the end of this blog entry, and the end of this term. I personally found this last week's concepts to be more on the challenging side, but a lot more manageable than week 11. Comment below on how you guys found this week's concepts, and let me know your solutions for the problem solving session. Let us compare and contrast our answers. As always words are hard, comp-sci is and always will be awesome, and later days. Good luck on your exams everybody. This is Kyle Mendoza signing out.

No comments:

Post a Comment