Week 11 - Halt !! Confused again !!

Little did I know that this course will confuse me from the beginning until the end of the semester; it gives me no breathing room to fully understand the different concepts. This week, while I felt a lot confident in my proof techniques and understanding of the Big Oh and Big Omega, I was hit hard in the face by the Halt problem. 

In this concluding week of the course, the course limited computer science by introducing the idea that not all the problem in the world can be solved by algorithm. I struggled to accept this reality for a long time until the example popped up. 

The code in the example measures if  an particular input will cause the algorithm to halt. When I first encountered, I didn't fully anticipate the running time. Therefore, I though it was going to work as expected. Nevertheless, with a longer running time, it is almost impossible to anticipate the result due to the vacuously distinguishing of whether the program is running for ever or halt eventually. 

It all seems reasonable at first, until naval gaze come in. 

It was impossible for me to grasp the idea of navel_gaze with a weak background in programming and coding (only taking CSC108 currently). Particularly when H halts, and how that will effect navel_gaze ; with function in side a function, it twisted inside my mind.  In order to fully understand the definition of navel_gaze, I had to draw out the map of the two function and trace the different input. It took forever to finally to work out that navel_gaze is uncomputable. However, I believe it was definitely worth the time since now I have a better understanding in this material.

*This slog also helped me in grasping the idea of halt. The description is quite logical. 
http://165slog.blogspot.ca/2014/11/week-11.html

The uncomputable program introduces a new technique in proof: reduction. The new technique allows me to prove that many other programs are also uncomputable. The technique is much easier to grasp once I understood the idea behind the halt function. The proving technique uses the fact that one program is uncomputable implies that another program is also uncomputable. Such technique is simple yet powerful in depicting the limit of algorithms. 

The reality that explain this phenomenon was more fascinating. In math, I knew there was always a different between the different infinities. However, I never quite dig into the truth that makes them different. The halting problem also introduces one to one counting. For different sets of infinities, there could be one to too many resulting the phenomenon of the halting problem. This is another point where I struggled during the week, trying to figure out the different sets of infinities : from natural numbers to rational numbers. 

Overall it was a week of hectic.