Part of the reason I struggled with understanding last week's lecture was that I am not familiar with Python. I had started with Java, and one of the things that confused me was having a function inside another function, since in Java you could not have nested methods.
Last week we talked about a function halt(f, n) that takes a function f and determines if it halts, given the input n, and learned that no one can write halt(f, n) that works for all Python functions. To prove this, we can first assume that it is possible to write such a function, use a function clever(f) that reduces to halt(f, n), and prove that it leads to a contradiction. We looked at the following function:
1. def clever(f)
2. while halt(f, f):
3. pass
4. return 42
and considered the case of clever(clever):
If clever(clever) halts, then then halt(clever, clever) on line 2 returns true, and we enter into an infinite while loop, and clever(clever) does not halt.
In the other case, if clever(clever) does not halt, then halt(clever, clever) on line 2 returns false, then we skip line 3 and return 42 at line 4, and clever(clever) halts.
Since both cases lead to a contradiction, we have just proven that no one can write halt(f, n)!
From here, we can prove that some function is not computable if we can show that halt(f, n) reduces to said function.
No comments:
Post a Comment