WEEK 11 JOURNAL: HALTING PROBLEMS

    This week, we talked about how to write a halt function, how to define a computable function, what is reduction and what is a countable set.
    First, we proved that we cannot write a halt(f, n) works for all functions f. To prove this, we can say that let the function test itself. Case 1 is that if the halt function does not halt, we can return a number, but if the function returns a number, it actually halts. Thus, we get a contradiction. Case 2 is that if the halt function halts, this function will continue run the while loop, this is an infinite loop and the function won't halt. Thus, we also get a contradiction for case 2. Therefore, we cannot write halt(f, n).
    A computable function is a function that f(x) is for every x in some certain domain and we know how to compute f(x) for every x in domain. Otherwise, f(x) is non-computable. For example, the halt function is a non-computable function.
     We say that f reduces to g if we find that f can be implemented by extending another function g. We can use reduction to show whether a function is computable or not, because a computable function reduces to a computable function.
     We use |A| to represent the size of  set A and if  |A| ≤ |ℕ|, we say that set A is countable. 

WEEK 10 JOURNAL: BIG-OMEGA, GENERAL PROPERTIES

    This week we continue talking about the big-oh problem. This time, we learned how to prove some general statements about big-oh. For example, we want to prove that for all f, g, h belong to F, (f∈O(g) and g∈O(h) ) => f∈O(h). In this question, we first know that if f∈O(g), and g∈O(h), then f <= c1g and g <= c2g. We want to show that f∈O(h), thus we need to choose a suitable c. We can easily know that when c >= c1*c2, f is always smaller than or equal to h. Therefore, we can pick b the biggest between b1 and b2 then pick c as c=c1*c2, then this statement is proved.
    Another statement is that ∀ f, g ∈ F, f ∈O(g) =>g∈Ω(f). Since f ∈O(g), we know that n>=B => f<= cg. Since g∈Ω(f), we know that n>= B' => g>=c'f. Because f<= cg, g>=f/c, thus, we can pick c' = 1/c and let B' = B. Then this statement can be proved.
    There is a tricky question: ∀ f, g ∈ F, f ∈O(g) =>f∈O(g*g). This statement is false, because g*g is not always bigger than g (i.e. let g = 1/(n+1)^2).
    In conclusion, to prove these statements, we need to find the relationship between the c we want to show and the c we have already known, and we also need to use the upper bound and the lower bound to bound the function.

WEEK 9 JOURNAL: BIG-OH OF POLYNOMIALS

    This week we talked about how to prove 7n^6 - 5n^4 + 2n^3 ∈ O(6n^8 - 4n^5 + n^2). To solve this problem, we first need to find the relationship between these two functions. We find that 6n^8 - 4n^5 + n^2 >= 6n^8 - 4n^5 >= 6n^8 - 4n^8 = 2n^8 since n is a nature number. Then, we can also find that 7n^6 + 2n^6 = 9n^6 >= 7n^6 + 2n^3 >= 7n^6 + 2n^3 - 5n^4. Therefore, our task now is to make some connections between 9n^6 and 2n^8. We need to make the constant the same and the number to the power of n to be different so that we can judge which one is bigger. Therefore, we choose our c = 9/2, and c * 2n^8 = 9n^8 >= 9n^6. Therefore, (6n^8 - 4n^5 + n^2) is always bigger than or equals to (7n^6 - 5n^4 + 2n^3) when c = 9/2. The hard point in this problem is that we need to pick a c that can connect both functions together.
 
    I remember that the test question 2 is a little bit similar to this question. In question 2, we need to find a "d" to make the negation of the statement to be true. Since "∃ d", this d must be unique and cannot be a universal number. The principle we judge whether a number is unique or not is that whether this number we choose can connect the antecedent and the consequent together. How to choose a unique number is quite hard sometimes, and we need to keep on practising.