Week #11

This week is the last second week before the class ends, plus there is a fall break with two days off on Monday and Tuesday, which makes me excited. Although this week doesn't cover too many things, what we learnt, again, makes me confused. I heard that this is the last chapter for this course, which i think is also the most difficult part. Basically, what we need to do is to prove non_computable function and computable function using reduction, which is something related to halting function. I still have no idea about it until I see the course note from course website. I can understand the example that was given and structure is clear to me. But that it, I don't think I can solve the same type of question by myself. I really hope that there will be more examples with solutions on this type so that I could have a deep understanding. The following question is the one appears on the course note, which I think is pretty typical. At least, I think we can figure out the structure of same type of questions after understanding this example.
I also check other students' slog like http://davidhanslog.blogspot.ca/to see if we have the same problem on halting problem.And yes! Many people are confused by this kind of problem.

The following is an example using induction: