week[11]_ending

Our last thing before the final exam is the assignment 3.

To be honest I didn’t put too much time in this course since November, and I was so wrong that I under estimate the difficulty of the course, it is kind of out of my control now :( I don’t have much clues about the algorithms until I forced myself to sit and read Larry’s notes and attended his office hour, then everything becomes clear haha. I didn’t do well on my second test (like 60%), and my second assignment I got like 37%. The situation is much more dire than I expected…I’m so sure most of my work in assignment 2 are correct after compared my answers to the sample answer, maybe my terrible layout ruined it :( I requested remark anyways, I hope the TA will forgive my layout and grade it fairly.

Another remarkable thing is in assignment 3, for question number five I picked f=sinx and g=cosx in the first. However Larry’s notes inspired me that just pick f(n) = 0 when n is odd and 1 when n is even, g(n) = 1 when n is odd and 0 when n is even, the whole problem just collapses. Its difficulty drops from above the highest clouds to the lowest possible seabed. The metaphor may sound funny but that was how I feel when I finally can solve that problem and the only thing left is to write an appropriate proof structure, which is such an easy piece.

One more last thing is, the semester is over. Thanks all for everything! Cheers!! 

week[10]_fallBreak

Finally it’s the fall break, everyone can catch their breath now. Have fun and enjoy!

week[9]_halt

This week more programming things are involved. For example the halt problems. As what are wrote in the course notes, we use the following technique to prove some programs are not computable.

First of all, we proved halt() is not computable. However, to prove some functions are not computable as well, we need to assume halt() is computable. The strategy is using contradictions, that we assume halt() is computable, we use it to prove the function is computable, however halt() is wrong, so does the function.

Generally, we define a halt function, such as

                                                                  def halt(F, I):

Then we use the given function as a helper function within the halt function, such as

                                                                  def given(f, i):

                                                  ‘’’return certain result when certain conditions are satisfied’’’

Then, we write another function within halt() by ourself, it much call the halt() and its result is not affected by the input. For instance

                                                  def given_prime(x):

                                                           F(I)

                                                           return ‘hahafail’

So, put them all together we can write like

def halt(F, I):

    def given(f, i):

        …implement code...

    def given_prime(x):

        F(I)

        return ‘hahafail’

return given(f, given_prime)

so the only thing we need to do here is prove when halt is true, our result is true; when halt if false, then result is false, and by contradiction, given is not computable!