Week 10+11 - big-theta and computability!

Oh man, I think I'm really behind, where I think I understand what's going on in class, but the second I walk out of class, I have no clue what I'm doing. Anyways, this week we learned about proving big theta. Similar to proving Big O, you try to under-estimate the antecedent, and over estimate the subsequent to create a link between the two, proving that one function is smaller than the other. Furthermore, we should always try to keep in mind the definition of big theta and big O, and remember that we should consider the point which the functions start diverging and increase at different rates, helping us select variables to use for the proof, where we pick B and c based on known B's and c's.

Now onto harder, but more interesting things, computability. Computability is where we want to see if a function can return a result. Through the analyzing the algorithm we can predict what the computer is able to compute. However, not all things are computable. For example, if there existed a function which could see the computability of any function. If it were to compute itself, there would be a contradiction. Therefore it is actually impossible to make a single function that can see the computability of any function. Furthermore, if you're thinking what if we just run the function and see when it halts? Well if the function did not halt at all, you would never get a result back!

And so, what are reductions? This part I don't understand too well just yet but i'll see if my explanations are correct. Assume there are two functions f(n) and g(n). If f(n) was implemented by extending g(n), we can conclude that f(n) reduces to g(n). Therefore if g is computable, it implies that f is computable. And with the contra-positive, if f is non-computable, g is non-computable! Through this we can prove if functions are non-computable by relating it back to the halt function!

Anyways that's all I've got for today, this course is getting very interesting but unfortunately very hard. I hope that I can end up with a 75% to apply for the computer science minor, but with how mind boggling stuff is getting, I think I'm going to have to put in more effort.