Re: Grammatical Recursion

From: Tak To (takto_at_alum.mit.edu.-)
Date: 12/20/04 

Date: Mon, 20 Dec 2004 10:03:08 -0500

Florian Laws wrote:

> On 2004-12-19, Lee Sau Dan <danlee@informatik.uni-freiburg.de> wrote:
>
Florian Laws <fl-usenet-2004@void.s.bawue.de> wrote:
FL.0> I does, but that only shows that Iteration is in fact
FL.0> just as powerful as Recursion.

Lee Sau Dan wrote:
LSD.1> Using a stack in an iteration cheats by adding recursive power
LSD.1> to it, thereby upgrading it to recursion. The additional power
LSD.1> of recursion over iteration lies in the (implicit) unbounded
LSD.1> stack.

FL.2> Well, computability theory doesn't care if you think of
FL.2> it as cheating.

LSD.3>>But it cares whether you use extra memory (the stack).

FL.4> By definition, WHILE-Programs can have infinitely many variables.

Not quite, but variables (or "registers") can be unbound in size.
(I am leaving out arrays of unbound size...)

      ----- -----

LSD.3> It also cares
LSD.3> how the memory is accessed (stack vs. tape vs. random-access).

FL.4> It does not, since the class of computable functions is the same for
FL.4> WHILE-Programs, µ-recursive functions and Turing machines.

Yup. Sau Dan is assuming a formalism (computation model) which has,
among other things, an unbound "stack", but fixed width "variables/
registers". Obviously, Turing Machine and Kleene Recursive Functions
are different formalisms.

As I said before, it is meaningless to compare recursion and iteration
without specifying a specific formalism (that have both notions).

Tak 

--
----------------------------------------------------------------+-----
Tak To                                            takto@alum.mit.eduxx
--------------------------------------------------------------------^^
  [taode takto ~{LU5B~}]      NB: trim the xx to get my real email addr

Relevant Pages

  • Re: Is this tai-recursion?
    ... There is no difference between tail-recursion and iteration. ... That's why tail-recursion is so simple, ... fetch next instruction from instruction pointer ... instructions will manipulate the processor stack. ...
    (comp.lang.scheme)
  • Re: counting BST nodes using iteration
    ... It uses iteration. ... size_t nodecount(node *root) { ... The problem is how to declare the stack size because we do not know ... converting the above recursion into iteration. ...
    (comp.programming)
  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Re: iterative copying of binary expression trees
    ... tail recursion as de facto optimized (bounded stack space). ... "Functional iteration" makes high sense IMHO. ... and an iterative procedure from an iterative process. ...
    (comp.lang.lisp)
  • Re: counting BST nodes using iteration
    ... without using recursion. ... It uses iteration. ... delete stack. ... If you have a decent stack ADT, ...
    (comp.programming)