Week 11- Halt, computability and many other confusions

        This week, I was introduced to the most confusing concept ever----that nobody can write a halt(f,n) that works for all programs. In order to recount my troubles, I have to first explain what is halt. Basically, halt is a Python function with two arguments. The first argument takes any other function f, and this function f has to take a single input n. The second argument is any input n that can go into the function f. What halt does is that it examines the code in f, and all the data in n, then return the boolean value True if f(n) halts at a certain value of n. If f(n) does not halt at any value of n, then halt(f,n) returns the value False. For some programs, it is possible to write a halt function that tests if the function halts.
        For instance, a halt function can be written to test if function may_halt halts at a specific s.

All I need to do is to check the length of string s. If length of s is not even, which means it's odd, then the program may_halt halts by printing the string s and the string " has odd length", while halt(may_halt, s) returns the value True. Similarly, if the length of s is even, then may_halt(s) iterates forever nonstop and halt(may_halt, s returns False. However, I cannot write a halt for function collatz(n). Maybe in the near future, someone may come up with a code for halt that tests if collatz halts or not, but as for now, no one has any idea how. All we know is that collatz halts for every single n up to more than 2^58, but we don't know if it halts for all n in the set of natural numbers.

Hence, although it is possible to write a halt for may_halt, it is impossible to write a halt(f,n) that works for all programs. The impossibility to write a universal halt confuses me and I could not comprehend why is this concept true. I understand that for functions like collatz, I might not be able to write a halt function. But what makes computer scientists so certain that it is impossible to write a halt that works for all programs? For instance, the fact that we don't know if alien exists does not necessarily mean that they don't exist. It could be that aliens do exist but we just haven't encounter one yet. My confusion is cleared after I was shown its proof.

        The proof for the claim that nobody can write halt(f,n) uses proof by contradiction. Now, consider the function sushi in two cases:

For the first case, assume sushi(sushi) halts, then halt(sushi, sushi) is True and the while loop iterates forever (an infinite loop), which means that sushi(sushi) does not halt (I arrived at a contradiction). For the second case, assume sushi(sushi) does not halt, then halt(sushi, sushi) is False and 2 is returned. This also poses a contradiction since it would mean that sushi(sushi) does halt. Thus, because contradiction occurred in both cases, we cannot write halt(f,n).