Tuesday, 2 December 2014

#11 Halting Problem

This week we were taught about halting problem. Honestly saying I still find it is hard to tell what exactly it is. Yet there is a question about proving some function is not computable in Assignment 3. I went through the given proof in course note. Here is the question below.
Claim : the function meaning_of_life is non-computable.
Proof by reduction:
For a contradiction, assume that meaning_of_life is computable,i.e. It can be implemented as a python function. So, implement halt(f, n) using meaning_of_life(f, I),
def halt(g, i):
     def meaning_of_life(f, I):
         ...code for meaning_of_life goes here...
     def g_prime(x):
         g(i)
         return 42
return meaning_of_life(g_prime, i)
If g(i) halts, then g_prime(i) will execute the statement return 42, so meaning_of_life(g_prime, i) returns True, so halt(g, i) returns True.
If g(i) does not halt, then g_prime(i) will not execute the statement return 42(no matter what value x has), then meaning_of_life(g_prime, i) returns False, then halt(g, i) returns False.
But there is no python implementation of function halt.
Hence, there is no python implementation of function meaning_of_life.

It just use the property of halting problem(it has no result)

No comments:

Post a Comment