SLOG #8: Finally Understanding Big-Oh, but New Confusion with Halting

I haven't written in about two weeks so this post is going to be longer than usual.

Last Monday and Tuesday was reading break. Hooray for long weekend! I was planning to get some studying done for CSC165, but other assignments and midterms kept me busy.

Last Tutorial: 
We covered proofs with big-Oh.

Steps to proving big-Oh:

1. Write out the definition of what it means for a function to be in big-Oh. In words, the definition basically means that there is a c in the set of positive real numbers, and there is a B in the set of natural numbers, such that for all natural numbers (n), if n is greater than or equal to B, then beyond B (the break point), function f(n) is upper-bounded by c multiplied by the other function.  
2. Do some rough work to find values for c and B. Try to play with manipulating inequalities until you have the result you want. 
3. Write the proof structure, and fill in the body of the proof with the information gathered from rough work. 

Lectures and New Information

For the past week in class, we've been talking about the halting problem. I have to say this is the most confused I've been all semester. All I know is that Church and Turing first proved the halting problem. And my job is to reduce halt to a function (not even sure what that means). Literally, that's all I know about it. I did go visit the CS aid center but the TA there didn't learn about so he couldn't help much. I'm planning to read over both Danny's and Larry's class notes on it, and definitely go through the course notes. And then after that, visit office hours. I'm really worried I won't understand this in time for the assignment though. In our assignment, it's asking us to reduce halt to meaning_of_life. The only information we're given is "return True if f(I) return 42, False otherwise". I'm not quite sure what I'm supposed to do with that piece of information.

However, I'm glad to find that I'm not the only person with this confusion. http://celinasopiniononcsc165.blogspot.ca/ expressed similar confusion. She did do a blog post on a halting problem, but after reading her post, I'm still confused as ever.