Talk:nonrecursive

From RFV

"Incapable of being computed by any deterministic algorithm in any finite amount of time." I think a reference would be more useful than citations for this. See also w:Recursion#Recursion_in_mathematics. Kappa 08:19, 16 January 2007 (UTC)

This is a big confusion in math/comp sci/logic. The meaning in question dates from the early 30s, possibly before the more common meaning of recursive. It's just a case of the same word having two meanings, but the confusion is greatly confounded by the fact that the two meanings are closely related. Recent literature tends to shy from "recursive" and use the synonym "computable", but people still use "recursive" in this sense. More importantly, this meaning has very large amounts of usage in older computability theory books and journals. If I have time, I'll go find three books with it tomorrow... — This unsigned comment was added by 140.254.93.113 (talk).

I don't think there's much confusion in practice. The term recursive has overwhelmingly come to mean "involves a function calling itself, either directly or indirectly." This is because in certain popular environments, recursive calls eat stack space (even when they don't have to) while the logically equivalent "iterative" form doesn't. By this logic, "non-recursive" means "not involving a function calling itself, and thereby consuming constant stack space".

The older sense of recursive meaning "computable", and "nonrecursive" meaning "not computable" (in the technical sense) is certainly attested; it used to be the accepted definition. Unfortunately, the article as it stands has it wrong. Nonrecursive refers to a particular technical model, not to any possible model (recursive functions, Turing machine, lambda expressions, combinators ... take your choice). There might be some magic technology we haven't thought of that can solve the halting problem in finite time, but that wouldn't make the halting problem recursive.

As the anonymous comment says, this sense probably less used now. In any case, both senses should be given, and this would probably be another place where a usage note on prevalence would be good. Otherwise someone is bound to complain that recursive "really means" the old definition, and the current definition is "incorrect." -dmh 15:54, 16 January 2007 (UTC)

I'm not sure what you mean by "a particular technical model" -- do you mean only things that are Turing-equivalent and not magical, or, say, only Turing machines and not the lambda calculus?

Perhaps we should make nonrecursive say only "not recursive" and move this discussion to recursive. Cynewulf 16:56, 16 January 2007 (UTC)

I'm considering "Turing machine or lambda expressions or combinators or anything else proved to be equivalent to them" as the model in question. They're all isomorphic (so you might as well say they're all combinators as they're all Turing mchines). Complexity theory often allows you to throw in "oracles", which are assumed to be able to do things that would otherwise be outside the model at hand. For example, you might prove that a particular problem is still hard even if you have access to an oracle that can solve the traveling salesman problem in constant time. Just so, you could posit an oracle that can solve the halting problem and talk about whether you can do anything interesting with a Turing machine (or whatever) together with that oracle. Such a beast could solve problems that are computable (under that model) but not recursively computable, that is, nonrecursive.

But even my eyes are glazing over here. For all practical purposes (that we know of) "computable" and "recursive" are synonymous. -dmh 00:31, 17 January 2007 (UTC)

All of those things are equivalent. In terms of what is computable, your choice of recursive function, lambda expression, etc. are all Turing machines. Is there something else out there? Doesn't matter. When I see "computed" I think "Turing machine". When I see "deterministic algorithm" I think "Turing machine". If the definition is "wrong", it's less incorrect than it is a little rigorously imprecise. But when it comes to understanding these mathematical concepts, a more precise definition isn't necessarily a better one. I consider the definition to be correct and this flaw nothing more than an unclarity too minor to fix. DAVilla 17:33, 16 January 2007 (UTC)

OK, as promised, I went and found some usages. It is annoying to FIND usages of "nonrecursive" because obviously indices only list "recursive". But in the few minutes I looked, I did explicitly find two usages of nonrecursive (among mountains and mountains of usages of "recursive"). These two specific "NONrecursive" usages were speaking about sets rather than functions, but this is a generalization: the mathematicians will agree that (at least in discrete math) a function is itself just a set of tuples, and it's computable as a set if and only if it's computable as a function. If anything, we might add a THIRD sense of "recursive" to talk about sets. Anyway, here are three books:

1. "Computable Structures & the Arithmetical Hierarchy", C.J. Ash & J.F. Knight, 2000. Page 4 gives a handy table with one column labelled "informal" and the other labelled "formal". Recursive (actually "total recursive", a special case) is listed under "formal", "total computable" under "informal".
2. "Computability, a mathematical sketchbook", Douglas S. Bridges, 1994. Page 75 specifically uses "nonrecursive". Page 38 uses "recursive". As mentioned above, this author speaks of (non)recursive SETS.
3. "Computability in analysis and physics", Marian B. Pour-El & Jonathon I Richards, 1988. Page 6 uses both recursive and nonrecursive (it uses nonrecursive to speak of sets, and uses recursive in both senses), and is also chock full of nice quotes:

   "Intuitively, a recursive function is simply a ``computable function."

   "The weight of fifty years experience leads to the conclusion that ``recursive function is the correct definition of the intuitive notion of a computable function."

Yep. That's the Complexity Theory 101 sense. OTOH, if you google nonrecursive "stack space" you'll find a bunch of instances were "recursive"/"nonrecursive" has to do with functions calling each other. As I said, I'm pretty sure this is what most folks mean (even folks who took Complexity Theory 101) -dmh 00:39, 17 January 2007 (UTC)

Arguably, nonrecursive isn't idiomatic. It means (as the first def says) "not recursive". In either sense. I'd vote for removing the second def and adding "(in either sense)" to the first, just to be clear. That's a pet peeve of mine, by the way. We define something in terms of something else, complete with link, but neglect to say which sense of that something else. -dmh 00:44, 17 January 2007 (UTC)

RFV failed. Sense deleted. (This being covered by the previous sense anyway, I'm not sure why it came here instead of RFD, but O.K.) —Ruakh_TALK 18:22, 23 May 2007 (UTC)