Week 11

So this weekend CDF was down so the course website and MarkUs could not be accessed which was inconvenient. We also got a break from classes on Monday and Tuesday which was a pleasant surprise. It was back to lectures on Wednesday where learned about the halting problem as well as countability.

I think the halting problem is the one of the most interesting topics we have learned so far. The halting problem is the problem of determining whether given a function and an input, will the function halt or continue to run forever. One would think to just run the function and if it halts then you know it will halt. The problem is that if it doesn't halt, you cannot tell if it will eventually halt or continue running forever.

I think this post here http://soohamrafizslog165.blogspot.ca/2014/11/week-11-halting-problem-and.html gave an interesting explanation and visualization for the halting problem.

Countability was also an interesting topic. A set is countable if it has a one-to-one correspondence with the set of natural numbers and it is onto the natural numbers, which means every number in that set can be reached from at least one natural number. We used this to show that the size of the set of even natural numbers is equal to the size of the set of natural numbers, which is not very intuitive. There are also some sets that are not countable. Cantor used diagonalization to show that there are infinite sets such as the set of rational numbers that are not countable.