Subject:
|
RE: recursion (was RE: Would-be hacker queries.)
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Thu, 13 May 1999 15:40:10 GMT
|
Original-From:
|
Blake Winton <blake.winton@pcdocs.&AvoidSpam&com>
|
Viewed:
|
1237 times
|
| |
|
|
On Thursday, May 13, 1999 10:28 AM, Rich Clemens [SMTP:clemens@wvwc.edu]
wrote:
> From: Ben Laurie <ben@algroup.co.uk>
> > John A. Tamplin wrote:
> > > I am not familiar with that function, but I believe I recall a proof in
> > > a
> > > graduate CS theory class that any recursive algorithm could be
> > > transformed into an iterative one. Do you have a reference for this
> > > function?
(From http://www.google.com/ searching for "The Ackermann Function")
The url to a description of Ackermann's function:
http://public.logica.com/~stepneys/cyc/a/ackermnn.htm
An excerpt from that page:
Ackermann's function, while Turing computable, grows faster than any
primitive recursive function.
This means that any given Ackermann number can be computed by a machine
with
a finite number of states, and an infinite tape of places to store
values.
Note that the Turing machine isn't a recursive machine. (i.e. It can't
call
another Turing machine, and get the return value.) Therefore, anything
which
can be computed by a Turing machine can be computed iteratively.
> > And, BTW, isn't this intuitively obvious, since CPUs are, in fact,
> > iterative?
> How so?
Given: That you can write a (recursive) program which implements the
calculations for any recursive function, and compile it into machine
code
for your CPU.
Given: That your CPU doesn't contain another miniature CPU.
(Alternately, that your CPU runs a sequence of statements one after
another.
Alternately, that your CPU is iterative, which is to say,
non-recursive.)
Conclusion: That any recursive program must be translated into an
iterative
version by the compiler.
(Alternately, that any recursive function must be able to be translated
into
an iterative version which does the same thing.)
Later,
Blake.
--
Did you check the web site first?: http://www.crynwr.com/lego-robotics
|
|
1 Message in This Thread:
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
