Week 11: Halting Problems

This week, we were introduced to two totally new ideas: halting problems and computabillity. These were first introduced and proved by Alonzo Church(who introduced Lambda calculus) and Alan Turing(who described Turing machine) before they even had a computer.


Then prof showed us one function collatz:
def collatz(n):
    #n is a natural number
    while n>1:
        if n%2 == 0:
            n = n/2
        else:
            n= 3*n+1
    return "Reach 1.."
Nobody on this planet know the answer that whether this function halts or just loops forever. Even mathematicians cannot do that -- they can only show that the function halts for n less than 2^58.
Then we turned to the function H(f, i), which takes in a function f and a variable i and output if the the function f(i) halts. For the proof of H(f, i), we need to use contradiction: If we assume that the function halts, then we will end up with the conclusion that it doesn't halt; if we assume that a function doesn't halt, then finally we conclude that it halts.

Finally, we learnt computability, which says that if f is a well-defined function, i.e. we can say what f(x) is for every x in the domain, but we can't say how to compute f(x), then f is noncomputable. And we know that computability has to do with halting to some extent as the example functions prof showed in class all have H(f, i) within the codes.

In conclusion, this week's topic is the most staggering and impressing part of this course so far because it showed me something I've never been exposed before and it is also different from the usual material taught in class like algorithms and other stuff. Although I still don't really grasp everything prof said about this topic in class, but I really found this interesting and I will keep working on it!