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