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.