Showing posts with label numerical domain. Show all posts
Showing posts with label numerical domain. Show all posts

Sunday, June 23, 2013

An enumerable but not effectively enumerable set

Let's focus on the first half of chapter 5 in Peter Smith's book. First, Smith describes a new characterization of effectively enumerable sets. Second, Smith gives an example of a set of integers that is not effectively enumerable.

Let's define the numerical domain of an algorithm as the set of natural numbers with the following property: when the algorithm takes one of these numbers as input, it terminates and returns a result. Every algorithm has a numerical domain. If the input to some algorithm is not a single natural number, then the numerical domain of this algorithm is the empty set. Otherwise, the numerical domain is the set of those natural numbers on which the algorithm does not crash and does not go into an infinite loop.

It turns out that each numerical domain is effectively enumerable. In fact, the converse is also true, according to the following theorem: