Lesson 5

Below, we will prove the undecidability of an important problem — the halting problem \(\mathcal{H}\). It is formulated as follows: given a program and its input, determine whether the program will halt on that input. Before proving its undecidability, let us imagine how the world would look like if it were decidable.