Christopher James Huff wrote:
> In article <3eb3dcbc@news.povray.org>, gimi <gim### [at] psicoch> wrote:
>>AFAIK this is only proven to be true for end-recursive algorithms
>>(though /many/ of the functions with a single recursion call can
>>be made end-recursive; but you will usually run into trouble if
>>the algorithm has multiple recursive calls).
> 
> By multiple recursions, you mean multiple recursions from a single 
> level, like branches on a tree? Those aren't a problem. And you don't 
> need them to be tail-recursive, though some languages can optimize those 
> into a more efficient iterative form automatically.
> Here's a very simple proof: computer processors are iterative. Recursive 
> functions are mimicked by using a chunk of memory as a stack. Turing 
> machines are iterative, and I've never heard of a recursive function 
> that could not be represented with a Turing machine.

You are absolutely right!  However, a Turing machine may run
forever, and it never runs out of memory.  Thus, the concept
of computable functions or numbers may be more appealing to
mathematicians than it is to computer programmers...

I have an example for you - The Ackermann function A(m, n):

for m = 0           A(0, n) = n+1
     m > 0, n = 0    A(m, 0) = A(m-1, 1)
     m > 0, n > 0    A(m, n) = A(m-1, A(m, n-1))

( http://www.kosara.net/thoughts/ackermann.html
or http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm )

Although it *is* of course a (Turing) computable function,
it is not primitive recursive, thus cannot be coded using
just for- or while-loops (or "iteratively").

( http://www-users.cs.york.ac.uk/~susan/cyc/p/primrec.htm
and http://mathworld.wolfram.com/PrimitiveRecursiveFunction.html )

>[...]
> Conceptually, a recursive definition is the most accurate description of 
> many fractals, including the Mandelbrot set. Fractals come out naturally 
> from recursive functions, but not from iterative ones. For example, the 
> Mandelbrot set's mathematical definition:
> z -> z^2 + c
 >[...]

This makes complete sense; however, a fractal does not
necessarily have to be the result of a recursive function
(as is also being stated on 
http://www.wikipedia.org/w/wiki.phtml?search=fractal&go=Go ,
the first link you mentioned).

And this definition lacks the exit condition, so neither a
turing machine nor a computer would ever return a result,
if the algorithm is implemented according to just the formula.
( - Would it be correct to call it non-computable in this case?)

>[...]
> As I've said, the recursive version is often much cleaner and simpler. 
> Just look at a few examples. The iterative version can be faster to 
> compute (especially when function calls are computationally expensive), 
> but is usually derived from a recursive mathematical definition.
 >[...]

Agreed.  Again, because I think as a programmer, I try to
keep it simple, fast and efficient.  So I avoid recursion,
if possible.

Thanks for the links; the first one
( http://www.wikipedia.org/w/wiki.phtml?search=fractal&go=Go )
is very interesting!


I see that a long time has passed since I learned about that
stuff; I forgot a lot...  Luckily, I get my programs running
properly mostly without thinking about Mr. Turing or primitive
recursion. :)


-- 
I'm pretty sure I'm seeing einsteinian light bending around
the local gravitational increase caused by programs that use
Date::Manip. :-) -- Randal L. Schwartz
++++++++++++++++ http://www.psico.ch/ ++++++++++++++++

Post a reply to this message