Representation As A Set
The conventional representation of decision problems is the set of objects possessing the property in question. The halting set
- K := { (i, x) | program i will eventually halt if run with input x}
represents the halting problem.
This set is recursively enumerable, which means there is a computable function that lists all of the pairs (i, x) it contains. However, the complement of this set is not recursively enumerable.
There are many equivalent formulations of the halting problem; any set whose Turing degree equals that of the halting problem is such a formulation. Examples of such sets include:
- { i | program i eventually halts when run with input 0 }
- { i | there is an input x such that program i eventually halts when run with input x }.
Read more about this topic: Halting Problem
Famous quotes containing the word set:
“He could walk, or rather turn about in his little garden, and feel more solid happiness from the flourishing of a cabbage or the growing of a turnip than was ever received from the most ostentatious show the vanity of man could possibly invent. He could delight himself with thinking, “Here will I set such a root, because my Camilla likes it; here, such another, because it is my little David’s favorite.””
—Sarah Fielding (1710–1768)