The Halting Problem


In Theory of Computation the halting problem is so talked and almost all Computer Scientists have been known.

Before of talking about the halting problem, we must to define some important aspects of definitions. The first is about decision problem and therefore we will introduce an undecidable problem. The Halting problem is an undecidable problem among others. An undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

The halting problem is historically important because it was one of the first problems to be proved undecidable.