I think it’s time for Captain Recursive to take the podium. (If you don’t think so, but would like to, see Kleene, S. C., “Metamathematics” or any number of more recent texts, most having the word “computable” in their title.) To begin with, it is important (for reasons some of which will appear below) that recursive sets be defined in the context of a well defined superset. Always, recursive sets and other related kinds of sets are taken to be subsets of numbers (Mr. Goedel and others have convincingly demonstrated that pretty much everything can be realized as numbers of some sort or other), and we shall do so. We’ll use “~” to indicate the complement of a set.
A recursive set is one whose membership is computable, in the strong sense that, given a number n, there is an algorithm (a computer program, if you will) which, in finite time, outputs the answer to the question, is n a member of the set.
A recursively enumerable set is one whose membership is computable, in the sense that there is an algorithm which cranks out the members, and only the members, of the set, all in finite time each.
Obviously (?), a recursive set is recursively enumerable; the reverse is not true. (Can you find a recursively enumerable set that is not recursive?)
If S and ~S are recursively enumerable, then S and ~S are recursive. (Just keep grinding away until the number in question shows on one of the two lists, QED.)
If the recursive enumeration of a recursively enumerable set S follows a computable linear order, then S is recursive. (Grind away until you have passed the ordering of the number in question; either it has shown up, or it has not.)
OK, why have I gone through all this, other than to impress y’all how brilliant I am (or at least how well I remember my math courses)?
Let’s look at the Cantor set C. Clearly (?), ~C is recursively enumerable. So what else can we say?
If you wish to better understand Zeno's worry about the continuum, you could do worse than to consider loops in software. Case 1: You...
Declares LewRockwell.com : "All of this means that while the government has been artificially propping up the economy and 'stimu...
Is shaping up nicely .
The language won't die, but that doesn't mean the programmers won't ! Funny quote: '"Just because a language is 50...