This week, although we had only two lectures, the content is really much harder for me to digest. Suddenly, we went from basics to a much deeper topic on halting problem and compatibility. In terms of halting problem, it is accordingly one of the first problems to be proved undecidable by Alan Turing in 1963.
Basically, the problem is to determine, if a program will eventually halt when run with given input. It is clear, some specific program can have a implementable halt; however, a general halt is intuitively very hard to get, and in fact it is proved to be impossible to get. This is the interesting part of this lecture. I was expecting an proof like we did previous in this course, but the one we saw was quit supervising to me.
def navel_gaze(f):
while H(f, f):
pass
return 42
This is a 'simple' counterexample, because it will halts if and only if it doesn't halt, which is clearly a contradiction.
Serving as a important background information of computability, halting problem gave me a different taste on logic and math. It is difficult to come up with a proof, but when reading the proof, the idea is not all that complex.
No comments:
Post a Comment