Turing machines don’t have to halt. They can run forever. It would be nice if we could determine in advance whether a given machine will halt on a given input, so we don’t waste time waiting for an answer will never come. Note that although a universal Turing machine can simulate any Turing machine on any input we can’t use it for this purpose. If we give a universal Turing machine as input a description of a Turing machine and an input on which that Turing machine doesn’t halt then the universal Turing machine also won’t halt. What we want is a Turing machine which will take as input a description of a Turing machine and an input for that machine and will always terminate, successfully if that Turing machine would halt on that input and unsuccessfully if it would not. This is called the Halting Problem.
There is, unfortunately no solution to the Halting Problem. This can be proved as follows. Assume there is a Turing machine which solves the Halting Problem. There will be several Turing machines to consider in this proof, so we’ll number them. The one just considered will be Machine 0. Machine 1 is some Turing machine which takes a pair of inputs of some kind and which always halts, either successfully or not, no matter what those inputs are. Machine two takes a single input and simulates running Machine 1 on two copies of that input. It halts unsuccessfully if Machine 1 would have halted unsuccessfully and does not halt at all if Machine 1 would have halted successfully. Machine 0 and Machine 1 cannot be the same. To see this, give them both, as input, two copies of the description of Machine 2. If Machine 1 would terminate unsuccessfully on this input then Machine 2 would halt unsuccessfully when given itself as input which means Machine 0 would halt successfully. If Machine 1 would terminate successfully then Machine 2 wouldn’t halt and so Machine 0 would halt unsuccessfully. In either case Machine 0 and Machine 1 have different behaviour on this input and so they are not the same machine. But Machine 1 was an entirely arbitrary Turing machine except for the requirement that it always halts eventually and if the Halting problem has a solution then Machine 0 is a Truing machine of that type, so we have a contradiction.
You may notice a similarity between this argument and Cantor’s diagonalisation argument from set theory, and also with the rather vague explanation I gave to make Tarski’s Theorem plausible. Indeed all of these arguments are related. Cantor’s was the first and inspired all of the others.
The unsolvability of the Halting Problem shows that some well defined computational problems are provably unsolvable. Perhaps more surprisingly it also provides an effective method for proving large classes of problems to be unsolvable. The most commonly used technique for proving unsolvability is to assume that there is a Turing machine which solves the problem and then show how to construct from it a machine which solves the Halting Problem.