How to make a proof of halting problem more convincing: a pedagogical remark

As an example of an algorithmically undecidable problem, most textbooks list the impossibility to check whether a given program halts on given data. A usual proof of this result is based on the assumption that the hypothetical halt-checker works for all programs. To show that a halt-checker is impossible, we design an auxiliary program for which the existence of such a halt-checker leads to a contradiction. However, this auxiliary program is usually very artificial. So, a natural question arises: what if we only require that the halt-checker work for reasonable programs? In this paper, we show that even with such a restriction, haltcheckers are not possible – and thus, we make a proof of halting problem more convincing for students. 1 Formulation of the Problem Halting problem: reminder. A computer science degree means acquiring both the practical skills needed to design and program software and the theoretical knowledge describing which computational tasks are possible and which are not. Different programs include different examples of problems for which no computational solution is possible, but all of them include – with proof – the very first example of such a problem: the halting problem, according to which no algorithm is possible that, given a program p and data d, always checks whether p halts on d; see, e.g., [2]. Some textbooks describe this result in terms of Turing machines but, in our opinion, this result is much clearer to students when it is described in terms of programs – i.e., something with which are very familiar – rather than in terms of Turing machines, a new concept that they have just learned in the corresponding theoretical course and with which they are not yet very familiar. Let us therefore concentrate on the formulation of this result in terms of programs.