Halting problem

    The materials we learned this week were a real challenge to me. We started a new chapter on computability and more specifically, the halting problem. The halting problem is one of supposedly many questions that computer cannot solve. The idea is to write a function that determines whether a function will halt or not. This is proved to be impossible by both Alonzo Church and Alan Turing, independently, in 1936.

    While in lecture, I found the disproof of the halting problem confusing. Admittedly I was lost in the proof and had to review the lecture slides to fully understand it. To disprove the halting problem, we have to create a contradiction. For example the function below solves the halting problem:

def new(f):

while halt(f, f):

pass

return “haha”

    Consider halt(new, new), which tests if the function new halts. If new(new) halts, then halt(new,new) is true and new(new) gets stuck in the while loop then new(new does not halt). The obvious contradiction in the sentence is highlighted in red, and a similar contradiction is shown when we assume new(new) does not halt.

    What is truly interesting about the halting problem is that it is only impossible in the current programming languages that we have. This leads to other provoking questions. Is it possible to invent a new language that makes some ‘unsolvable problems’ in the current languages solvable? As for me, such a language is beyond my imagination, because it will be a whole new way of thinking and a whole new dimension of logic.