This week we discussed functions that can't be computed. One such function is one which returns whether a program will halt. It is impossible to determine while a program is running whether it will continue running forever or whether it simply takes a long time. We can prove that this can't be done by logical contradiction: if such a function existed, then we could use it to write a recursive function which halts when the halting program says that the function does not halt (and vice versa).
Knowing that the halting program is non-computable, we can then prove that other functions are non-computable by showing that they would allow us to write a working halting program if they were computable.
No comments:
Post a Comment