On May 18, 11:58 am, Ian Kelly <ian.g.ke...@gmail.com> wrote: > On Wed, May 18, 2011 at 12:06 AM, rusi <rustompm...@gmail.com> wrote: > > 4. Recursion in 'recursion theory' aka 'computability theory' is > > somehow different from recursion in programming. > > Um, it is. Consider the simple function (lambda x, y: x + y). > Mathematically, this function is recursive. Algorithmically, it is > not. Do you disagree?
See the definition of primitive recursion eg. http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition (2 of the second set of "more complex" definitions) from where the name 'primitive recursion' is presumably derived) And for the more general (wider) class of 'recursive' functions (in the math sense aka computable functions) see a little below: http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationship_to_recursive_functions Of course I grant that the adjective 'recursive' is used differently in computability and in programming but the roots are not all that different. If I remember right (I may be misremembering) Hofstader, referring to the invention of 'recursive function' by Godel, says something to the effect that Godel was inventing lisp 30 years before lisp... -- http://mail.python.org/mailman/listinfo/python-list
