Week 10

This week was our second last lecture. We received term test 2 back. I did quite well compared to the previous test. Assignment 3 is also going to be out now. In this week's lecture, we started off by recalling the definitions of Big-Oh and Big-Ω. We went through one Big-Oh proof then we started Big-Ω. We learned the concept of the magic break point. We learned about proving general Big-Oh statements in which we pick a B and a c. In this week's lecture, we finished chapter 4 and started chapter 5 which is 'Introduction to Computability'. We learned about the concept of halt, whether or not a python function halts or not. We had to devise algorithms to check if the function halts or not. Halt basically means if the function stops or not. It is impossible to write one halt that works for all python functions. We proved this statement. One thing added to my knowledge was that computers cannot solve the halting problem. The professor showed us that the halt proof was first done by Alonzo Church and Alan Turing, independently in 1936. Halt is well-defined and non-computable. In this course, given any function, we decide whether it is computable or not using reductions. The meaning of reduction basically is that if a function f(n) can be implemented by extending another function g(n), then we say that f reduces to g. To prove a function computable, we show that a function f reduces to g that is computable. To prove a function non-computable, we show that a non computable function f reduces to this function. This is all that we learned in this week's lecture. Next week we have no lecture and the week following is our last lecture for this course and also the last week of classes for this semester.