Nonempty computably enumerable sets are primitive recursive ranges

ID: nonempty-computably-enumerable-sets-are-primitive-recursive-ranges

Every nonempty computably enumerable set is the range of a primitive recursive function . Choose , decode using a primitive recursive pairing function, and output if the recognizing machine halts within steps, or otherwise. The bounded halting predicate makes this function primitive recursive, and every member of occurs for a sufficiently large bound. The empty set is excluded because such a function is total.

New to topics? Read the docs here!