A problem in computer science is halting-complete if a solution to that problem would imply a solution to the halting problem. Because of the unsolvability of the halting problem (which may be easily proved by diagonalisation; the proof is analogous to Gödel's Incompleteness Theorem for formal systems), halting-complete problems are undecidable. This doesn't mean that significant subsets of the problems cannot be solved.

Log in or register to write something here or to contact authors.