Week 11: Halting Problem & Computability

This week, there was a reading week thus the class only had two lectures this week. During this week, Danny taught the class about the halting problem and comparability. Most of time, he used the python program which most of us were familiar of. Danny first introduced the algorithms which we are able to solve without a problem. However, Danny explained the class that not all the algorithms can be explained and solved by showing the example as below.

def collatz(n) :
    while n  >  1 :
       if  n  >  1 :
           n = n / 2
       else:
           n = 3*n + 1
    return "Reached 1..."

No matter what natural number n, you put for the above function collatz, the code will execute infinitely, without any halt. This example is what caught my attention as I tried to find the natural number which allow the function to halt, I was able to see how the coding in the computer program can be interesting.

Next, Danny taught the class some terminology we had to be familiar of such as computable and non-computable. Halt function is the one of examples for non-computable function.

Moreover, by relating to the topic of computable, Danny introduced how the implication works when the terminology "computable" is involved. For instance, "if g is computable, then f is computable", its contrapositive which is "if f is not computable, then g is not computable" should be true as well.

What I found really difficult this week was the topic of diagonalization and the definition of the terminology, "countable" and "non-countable".  Countable indicates when lAl < lNl, A is countable. For instance, the rational numbers can be consider as countable.

Thus this is just brief summary of what I learnt so far this week. By the way, there was no quiz this week, so I felt somewhat disappointing as I was not able to get the practice handout regarding the previous week's course materials. The weather is starting to get cold, but my passion towards the code will never fade away.