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.
Articles by others on the same topic
There are currently no matching articles.