Reflection of CSC165 Lec. 10 Nov. 11th

Reflection of CSC165 Lec. 10   Nov. 11th

10.1 Big -omega proof

After the big oh proof we did last week, omega proof is taught today. The principle of big-oh proof and omega proof is the same since big-oh means the upper bound and big-omega means the lower bound, they are almost in opposite position.

In definition, Big- omega means:

A function f(n) is in Ω(g(n)) iff:

∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≥ cg(n)

Keep in mind Big-oh means:

A function f(n) is in O(g(n)) iff:

∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≤ cg(n)

The proof of big-omega means you need to underestimate f(n) and overestimate g(n) in order to make the overestimated cg(n) equals to underestimated f(n)

10.2 Big-Oh proof for general cases

After proofing a lot of specific cases of Big-oh proof, it is time to find some general pattern or do some proof without any actual functions and numbers.

Proof:  ∀f,g,h∈F, (f∈O(g) ∧ g∈O(h)) →f∈O(h)

Assume f,g,h∈F, f∈O(g) ∧ g∈O(h)

    Then ∃c∈R+, ∃B∈N, such that ∀n∈N, n ≥B →f(n) ≤ cg(n)    # def of f(n) is in O(g(n))

    Then ∃c'∈R+, ∃B'∈N, such that ∀n∈N, n ≥B' →f(n) ≤ c'h(n) # def of f(n) is in O(g(n))

    Pick c'' = c*c', then c''∈R+

    Pick B'' = max(B,B'), then B''∈N

        Assume n∈N, n≥B''

        Then f(n) ≤ cg(n)

        Also g(n) ≤ c'h(n)

        Then f(n) ≤ cg(n) ≤ cc'h(n) = c''h(n)

        Then ∀n∈N, n≥B'' → f(n) ≤ c''h(n)

    Then ∃c∈R+, ∃B∈N, ∀n∈N, n≥B'' → f(n) ≤ c''h(n)

Then ∀f,g,h∈F, (f∈O(g) ∧ g∈O(h)) →f∈O(h)

In this case, the tricky choose of c is the core of answering the question. The answer substitute cg(n) to cc'h(n).

In fact, the choice of c plays an important role in this type of general question. It is used to link the condition together to form what we want to prove.

                                                                                

10.3 introduction to computability

After studying this section, I think it is the most difficult part so far I have learnt in this course. It is so abstract that I cannot get it from the example showed in the slide. Also the last question of Assignment 3 talks about the halt problem. I think I do not do it very well. Even though, I will try to explain this part in my words and comment on the question of Assignment 3.

Computer computes things by using algorithm, it is so powerful that it can solve a lot of complicate questions and returns the answer. However it is not always the case, sometimes the an easy program may lead to problem like infinity loop, which the computer would work forever inside the loop and cannot return the answer.

A typical infinity loop program may be this:

def blah(x):

    if x % 2 == 0:

        while True: pass

    else

        return x

The function would return x when x is an odd number, but when x is even, it will go into if x % 2 == 0. The while statement is true, so it will loop in the while line forever.

In order to judge this kind of functions, we use halt(f, i) to do so. I spend a lot of time to understand halt because the definition of it given on the slide is too vogue. I think it can be improved like this:

def halt(f, i):

    '''(function, input) -> Bool       

    

    Return true if the function halts (return sth. As result). Return False if it does not return                        anything. (Does not halt)   

    '''

    How to write halt in this case???

     return True

It is said that nobody can write halt(f, n) and it could be proved by contradiction.

So we suppose we can write halt(f,n)

Also I do not recommend to return sth. Like 42 as it is really confused for those who have  not seen or do not know the story and context of it.

 

There are three levels of function in terms of computability.

1. Computable

F is well defined in and we can tell how to compute f(x) for every x in the domain.

2. Well defined

We can tell the meaning of f(x) (what f(x) is for every x in some domain)

3. Non-computable

We cannot tell what f(x) is for some x in all domain.

Halt(f, n)  is well-defined but not computable because we cannot compute the f(x), but know the meaning of it.

After knowing the function for halt is not computable, we can decide any function is computable by using reduction.

We say f reduces g, if

Def f(n):

    return g(n)

This simple relation between f(n) and g(n) means their computability is the same.

G computable implied f computable

In contrapositive, f non-computable implied g not-computable

There are still some problems remain  unsolved and I will get the answer as soon as possible during upcoming office hour.