Man, this week's topic on the Halting problem truly is confusing. Making a program that can predict when all other programs in the universe could halt, gee whoever makes that, we should make a new religion for them and bow down to them as a new God, but I don't think that'll be happening anytime soon...
Anddd back on to Earth the class lectures' examples were sort of confusing it first, but I guess it's the idea of being a self referential you think of:
But then I reread the code again for the navel_gaze example and found that it's actually quite simple, it's just an infinite loop which never actually reaches the return 42 line, so when you call it upon itself a check for H(navel_gaze, navel_gaze), and of course using H() on another 'inner' execution of navel_gaze never actually halts, so an infinite loop occurs for the while H() line in the 'outer' function of navel_gaze, which then infinitely loops again. In Python though, which stops first? The inner while loop of navel_gaze in the H(navel_gaze_, navel_gaze) line or the outer while loop?
The hash function used in halt_0 has a bit strange because it was my first time seeing it in Python. The Python dictionary structure uses the hash function right? I almost forgot what hash-values and tables were and it was a huge reminder that I need to review my Java again because it'll be introduced in my second year of CS... (argh the amount of syntax...)
What I'm wondering though is how exactly we're going to be tested on the Halting problem on the final exam for this course. Will there be something simple as determining whether a program's counting is 1-1 or onto, or would it be something a bit more difficult, like predicting how a program will run another inner function and reduce to that same inner function(like the daunting fifth question on A3)?
For now, though I guess I'll refer to the course notes pdf on how to format a proof for it...
No comments:
Post a Comment