X-Message-Number: 9343 Date: Tue, 24 Mar 1998 07:16:56 -0800 From: Peter Merel <> Subject: Recursive Nature Though I hate to disrupt the struggle betweeen Ping and Pong, and I still have to find time to do the reading I've promised Mike Perry, a couple of definitions have rankled and I thought I might poke my nose in for just a moment. Recursion: speaking in craft terms, Ping is quite right - a recursive routine is one that calls itself. The most popular way to implement this is with a stack, though trees and lots of other funny structures can be used to the same effect. Church and Turing didn't die for nought. But speaking in computability terms the customary definition is that an algm. is called recursive if the set of expressions in its output is recursively enumerable and the set of expressions not in its output is recursively enumerable. As I recall it, such algms. may be said to halt, that being the big deal about that. Recursion in the craft sense does not imply recursive in the computability sense. Nature: humans are natural creatures and so whatever they do is natural. Ergo Nature is quite capable of constructing diamondoid fibres; it just evolves men to design them for it. Heinlein's shade said to say something about beavers and damns. As to the eternal game, I score it this way: Ping will happily define the limits of what's possible in terms of the limits of what's constructable. Pong won't. All else is cross-purpose. Peter Merel. Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=9343