Week 11

We started halting problems this week. Halt means to stop, so halting problems are related to if a function will stop running.

Of course, if we have to test if a function halts, we won't be able to test it by running the function directly, since if the function doesn't halt, then it will keep running and not return anything. What we do is to make another function by predicting if the function halts or not. My confusion is that is there always a function that can predict if the other function halts or not? Does the function always work for all the parameters for the other function, or it only works for some of the cases?

Like the open problem that we talked about in class. Takes a natural number, halves it if it's even, and multiply it by 3 and add 1 if it's odd, and continues this operation until this number reaches 1. How can one proves this other than trying out all the cases?

I think this halting problem and computability is a more advanced part of Computer Science, and it contains many unsolved problems.