Twelfth Week

                                 17th ~ 21th Nov

• Introduction to computability
• Reduction
• Finite Sets and Infinite Sets
• Countable ---- |N|

  'computers cannot solve the halting problem'.

  It is really confusing when first see this. But computer just know using the algorithm to compute again and again. There is no ending to a finite loop but we could not deny that there may be a end with time moving.

  Hence,Halt(f,n) is non-computable. Hence, to us, if we want to prove a function is computable or non-computable, we need the help of another already known computable or non-computable, which is called 'reduction'.

  The concept of finite and infinite is also interesting. For example, natural number and natural even number has infinite elements but do they share the same size? Actually, I am not really sure about there relationships. I think as to two sets P and Q. If we could say every element in P is one to one to Q, and P -> Q is onto if for all elements y in Q, there is at least one element x in P that f(x)==y.