CSC 165 Halting problem, computability

Week #11

Topic: halting problem, computability

This week’s material was more difficult than the material given in other weeks. For this reason, I would like to take advantage of this space to enhance the knowledge received.

Halting Problems

One of the most interesting and somewhat abstract concept was the one dealing with halting problems. I managed to wrap my head around this idea by thinking about it in the following way:

Consider these functions:

def H(f, i):

            ¨ ¨ ¨ Return True if f(i) will halt, False otherwise. ¨ ¨ ¨

return True

def navel_gaze(f):

            while H(f, f):

                        pass

            return 42

Now, let's relate these functions to each other.

H is a function that takes two arguments. Taking f and f as arguments means that we are running the program f on a program f. We do not really have to understand what happens when running   f(f). All we care about is whether that halts or not.

H(f, i) as well H(f, f) return True if they halt and False if they do not halt.

Now, a very important question is: What does the above mean in terms of the specific statement while H(f, f):?

While is an expression that is going to keep running until the statement within it becomes False. H(f, f) is false if f does not halt. However, if it does not halt then f halts because we just get out of the loop and return 42.

By using the same argument, we can see that  H(f, f) is true if f halts. However, if it halts then we stay in the loop and the program does not halt.

This is a contradiction because the program halts if, and only if, it does not halt. And, the program does not halt if, and only if, it halts.

One to one functions

When dealing with one to one functions we can always use its definition, as suggested in class. However, if we happen to have a graph of the function we are working with, drawing horizontal lines is an easier way to determine whether a function is one to one or not. This intuitive idea of checking whether we have a different f(x) for each x in the domain is what makes us come up with the formal definition.

f : A ↦ B is 1-1: ∀x, y ∈ A, f(x) = f(y) ⇒ x = y

This definition says that my enemy picks any x, y, and if we get the same result by plugging two numbers, that must be because we plugged in the same number. In other words, the result is the same because x refers to the same number that y refers to.

After understanding these key concepts, I feel more comfortable with the material learned.