Halt Right There!

I'm going to be brutally honest here. I haven't had time to review course notes recently and so I was really really lost during the lectures involving reduction and halting functions. I had almost no idea what was going on and I was really confused.

Halts? Halting? Naval_gaze? Infinite loop? Halt cannot exist? What?!?

I felt horrified that I didn't have the slightest clue what was going on especially since Assignment #3's deadline was closing in, which involved using halts. So I did some strenuous reviewing of the lecture notes along with the course notes.

After reviewing, I still felt dazed and confused about what a function halts was all about. It was only when I was semi-explaining (I had a vague idea of what halts was but didn't really understand it) the course notes/lecture notes to a fellow CSC165 classmate that I had an epiphany and almost fully understood what halts is all about.

Halts is a function that would take a function and an input as a parameters and return True if and only if the given function halted on the given parameter.

Halts has proven to not be computable (i.e. impossible to write in code) because there exists a contradiction. The proof is in the course notes on page 70. With this knowledge in mind, we can reduce the halting function to another function that is similar and show that a contradiction exists to prove that this other function can not be computed as well.

For example, let's consider this function (I made this example and I'm assuming this function is not computable so let me know if I'm mistaken):

def prints_something(f, x):
    ''' (function, object) -> bool
    Return whether the given function prints anything on the given input x.
    '''
    # Here exists valid Python code that scans the functions codes and
    # returns True if and only if the given function prints anything on
    # the given input x

Now, let's assume this function is computable and reduce the uncomputable function halts to this function:

Assume prints_something is computable

def halts(F, i):
    ''' (function, object) -> bool
    Return True if and onlf if function F halts on input i.
    '''

    def prints_something(f, x):
        ''' (function, object) -> bool
        Return whether the given function prints
        anything on the given input x.
        '''
        # Here exists valid Python code that scans the functions codes and
        # returns True if and only if the given function prints anything on
        # the given input x

        pass
   
    pass

So far this doesn't tell us anything. Now let's create an arbitrary function that function prints_something will analyze:

def f_naught(g):
    ''' (str) -> NoneType
    After calling F(i), the function and input that was passed
    to halts as arguments, print g.
    '''
    F(i)
    print(g)

Considering the function f_naught, we can see that if F(i) (a function and input that was passed to halts) halts, f_naught will print something thus prints_something will return True. If F(i) does not halt, f_naught will never print something and prints_something will return False.

So now let's put all these functions together. Obviously, f_naught must go into halts since it uses F(i) from halts:


Assume prints_something is computable with valid Python code

def halts(F, i):
    ''' (function, object) -> bool
    Return True if and onlf if function F halts on input i.
    '''

    def prints_something(f, x):
        ''' (function, object) -> bool
        Return whether the given function prints
        anything on the given input x.
        '''
        # Here exists valid Python code that scans the functions codes and
        # returns True if and only if the given function prints anything on
        # the given input x

     def f_naught(g):
        ''' (str) -> NoneType
        After calling F(i), the function and input that was passed
        to halts as arguments, print g.
        '''
        F(i)
        print(g)
   
    return prints_something(f_naught, '')

If F(i) halts, prints_something(f_naught,'') will return True because the "F(i)" line in f_naught will stop running, thus allowing print(g) to print something.Thus halts(F, i) will consequently return True as well.

If F(i) doesn't halt, prints_something(f_naught, '') will return False because the "F(i)" line in f_naught will never stop running, thus never allowing print(g) to print anything. Thus halts(F, i) will consequently return False as well.

Thus halts(F, i) returns True when F(i) halts, and it returns False when F(i) doesn't halt.

Now, the problem should be pretty clear. We've somehow successfully created a halting function!

The meaning of reducing one function to another is if this inner function can be made, the outter function can be made. Thus:

prints_something is computable implies halts is computable.

But there exists a contradiction; halts was previously proven to not be computable

Also, if we take the contrapositive of the statement:

"prints_something is computable implies halts is computable"

 We get:

"halts is not computable implies prints_something is not computable"

Thus, since halts was previously proven to not be computable, this implies prints_something is also not computable!

I hope this helps someone better understanding the halting function and related information!