Tuesday, December 2, 2014

Halting the Slogs (Week 11)

It's great that there was a shorter week during this week. However, I didn't actually do anything productive over that extended break. I guess relaxing can count as something, after all it's good to alleviate stress once in a while.
During this week, we touched onto the last topic in this course that was noted in Chapter 5 of the course notes. Just like starting any new topics, I immediately get lost and stop paying attention for a short while until I can actually grasp the ideas being discussed. However, with a certain test for a certain course coming up, I found myself neglecting this week's notes completely.
I kind of thought that all things in the universe could be computed given enough knowledge of it and time to implement the algorithm. This week brought to light that there exists things in which no one could ever implement an algorithm for, no matter how knowledgeable they are on the required task and no matter how much time is given. This struck me as rather strange. It is certainly true that you cannot implement everything using Python or perhaps any other programming language, but I wonder if the same can be said about implementing an algorithm by words. If it can be implemented using words, then certainly, one day, it should be possible to implement current day impossible algorithms.
One example given in class on an uncomputable algorithm, is the function halt. This student provides a proof for it. This function takes in a function and some other argument then calls the function on said argument. It will return True if that call halts and it will return False should it not halt. This problem is very apparent since if the call of the function does not halt, meaning never returning control back to the user, we will never get an answer. The fact that the function does not halt means we will never move on to the next line to return False, thus the function cannot be implemented. It may work well for function calls that halts, but it cannot determine when the calls do not halt. As said in class, it is impossible to tell if a bunch of code is taking a really long time to execute or it is caught up in some infinite loop.

No comments:

Post a Comment