Talk:Algorithm characterizations: Difference between revisions

Revision as of 21:56, 20 March 2010

Revision as of 22:51, 20 March 2010

Line 219:

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_i. 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)

::::Some of the algorithm characterizations in this article allow an algorithm to be partial recursive, i.e. on some inputs the algorithm might run forever while never producing any output. This question is different--whether an algorithm can run forever and produce an infinite amount of output. One can think of an algorithm as something that runs on a Turing machine, and a Turing machine as something that computes an abstract function but cannot do I/O. I/O can only happen through some external mechanism after the Turing machine enters a halt state. Some programming languages are organized around that concept;, e.g. a Haskell's program computes an "I/O action" (a value lifted to a state transformation mapping through a special type of functor called a "monad") thatcan isbe executed externally to the part of the language semanticsviewed that actually evaluates functionsway. I agree that "algorithm" is still a reasonable common-sense term, but we ought to source such a usage, and we haven't yet done so as far as I can tell. [[Special:Contributions/66.127.52.47|66.127.52.47]] ([[User talk:66.127.52.47|talk]]) 21:53, 20 March 2010 (UTC)