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!