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