I feel really stuck. Over the last 2 weeks, I've reviewed, studied Big-O and Omega. I went over the lecture slides, lecture note and practice on my own repeatedly, reviewed tutorials and quizzes. And I finally know how to do it. But this time, I think I am really stuck. I am really worried that I might not be able to do this even until the exam.(Hope that doesn't happen!)
It was the hardest last two weeks for me because the contents felt really hard and I barely understood material. Unfortunately, the last tutorial wasn't about computability or halt. Usually, when I'm stuck, tutorials were really helpful. I would understand the material after the tutorials so it really helped me to keep going and studying. I was hoping to deal with some of these problems on the last tutorial, but we did more of Big-O and Omega.
In terms of terminology, if the function f is well-defined function, that is we can say what f(x) is for every x, but we can't say how to compute f(x), then f is non-computable. As an example, we were introduced to the function halt as a non-computable function. Also, in order to prove uncomputable function, we use reductions.
Suppose that we know some function f is non-computable, the some other well-defined function g could be extended to build f. In other words:
If g is computable, then f is computable.
Using the contrapositive, f reduces to g:
If f is non-computable, then g is non-computable.
Unfortunately, I haven't fully understood about halt and the process of proving some function's computability so I don't think I can go further than this. I mean, I did sort of copy lecture note for Q6 in Assignment #3, but I'm not confident about this at all because I basically am not really understanding this. It feels bad that I could not make this SLOG with better understanding. But I will keep trying until the exam and get help if I really can't figure out by my self.( I usually prefer try by myself as much as possible cause in that case, it feels so much better and the contents actually last longer in my head..I think.) So, I guess at least I know what I have to do. review the slides and the lecture notes over and over until I understand and practice and practice until I get close to perfect.
I'm sorry about the difficulty understanding the halting problem. It is a complex idea, but please drop by office hours or inform the teacher when problems like these come up. Future courses will use similar ideas, so you will become familiar with the idea soon enough! I'll make a note to Danny to introduce the halting problem into tutorials.
ReplyDeleteFor reference, here's another explanation of the A3 question:
> We want to show "meaning of life" is not computable.
> We know that "halt" is not computable.
> To generate a contradiction, let's assume that "meaning of life" WAS computable.
> Then lets use this magical "meaning of life" function to implement halt itself.
> Since we've just shown we can build a solution to halt, then halt is computable.
> But that's a contradiction!
> Thus, halt is not computable.
Good luck!