Content deleted Content added
No edit summary |
|||
Line 49:
I can't see how both definitions can be considered "equivalent". I can see how, having an algorithm that enumerates the set, I can have another algorithm that, given an input number, eventually halts iff the element is in the set. But I can't see how, having such an algorithm, I could possibly enumerate the elements of the set. -- Anonymous, 13:20, 23 August 2006 (UTC)
: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)
| |||