Week 11

This week we learned how to distinguish whether a function is computable or not.
Some functions are not computable because the solutions are infinitely long, and some other functions are not computable because they are just not.

For example,
def halts_or_not(f, I):
      "return true if the function will halt, false otherwise"

This function is not computable. Why?
Consider this function:
def test(f):
      while halts_or_not(f,f):
             pass
      return True

Then halts_or_not(test, test) only halts when it doesn't halt. By contradiction, we know the function halts_or_not is not computable.

Then, the idea of 1-1 and onto is introduced. Two infinite sets have the same size only when they can be matched up in a way that is 1-1 and onto. Here's the definition of 1-1 and onto:

 Then, when |A| <= |N|, where N is the set of natural number, we say A is countable.