Content deleted Content added
→can an algorithm produce infinite output?: new section |
|||
Line 218:
:* There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>, ... . If necessary, this algorithm may run forever.
Is that a legitimate use of the "algorithm"? I can't find support for it in [[algorithm characterizations]]. I would say the set is recursively enumerable if there is an algorithm (recursive function) that takes input i and computes s<sub>i</sub>. I think that a function that takes some finite or empty input and produces infinite output (a list of all the primes) but is computable for every initial segment of the output is called [[corecursive]]. I don't know if "algorithm" applies to that. [[Special:Contributions/66.127.52.47|66.127.52.47]] ([[User talk:66.127.52.47|talk]]) 21:19, 20 March 2010 (UTC)
:::This bleeding thing keeps coming up; we really should document things somewhere and be able to point to it. The fact is that there's an older sense of the word ''algorithm'' that requires it to halt in finite time on every input. However this restriction tends to get in the way more often than it clarifies, and I don't believe the word is very often used in this strict sense anymore. Of course "not very often" is not the same as "not" (and for that matter I'm not even all that sure about "not very often"), so one way or another we need to deal with the ambiguity wherever it comes up — we can't just silently pick one definition or the other, because that would confuse readers expecting the other definition. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 21:31, 20 March 2010 (UTC)
| |||