Content deleted Content added
Futonchild (talk | contribs) Does S have to be a set of natural numbers? |
|||
Line 51:
:The definitions aren't ''considered'' equivalent -- they are provably equivalent. If you have an algorithm ''A'' that halts on exactly those numbers that are in a set ''S'', you can enumerate ''S'' based on how many steps it takes ''A'' to halt, as follows. Run ''A'' for one time step on input ''0''. Then run ''A'' for two time steps on input ''0'' and for two time steps on input ''1''. Then run ''A'' for three time steps on each of the inputs ''0'', ''1'', and ''2''. Whenever you run ''A'' long enough on a particular input that ''A'' halts, enumerate that input into ''S''. If you continue methodically in the pattern just listed, you run ''A'' arbitrarily long on every input, and thus your enumeration will include every number for which ''A'' halts. [[User:CMummert|CMummert]] 13:53, 23 August 2006 (UTC)
== Does S have to be a set of natural numbers? ==
Why not just say that a set ''S'' (of natural numbers, teacups, or whatever) is r.e. if <insert favored def. here>? Why (as is done in the article) restrict S to a set of nat. num's and attempt to accommodate other sets via goedel numbering? Infinite sets of natural numbers don't necessarily have godel numbers. Consider the set ''C'' of those that do. Now consider one that doesn't--of course, it's not possible to actually ''specify'' one--and call it ''s''. ''C'' U {''s''} is r.e., but not (not entirely) due to goedel numbering. In any case, it seems to me that the best method would be to present the general definition (where the nature of the elements of ''S'' is left unspecified) and then later, if necessary, restrict attention to r.e. sets of natural numbers.
| |||