Re: deductive databases

Clinging to sanity, Christopher Browne <cbbrowne_at_acm.org> mumbled into her beard:
> Quoth "ken quirici" <kquirici_at_yahoo.com>:
>> AFAIK there is no algorithm using recursion that can't be 'emulated'
>> by one not using recursion.
>
> Ackermann's function may be an exception; there do exist some
> fundamentally recursive expressions where "emulation" doesn't work out
> well.

I said this badly.

There is a class of functions termed as "primitive recursive functions" which are defined using recursion, but which may be implemented using only "for loops." Power function and GCD, are examples of primitive recursive functions.

You may have found that all of the recursive algorithms _that you have looked_ at were primitive recursive, thereby making them particularly amenable to non-recursive alternatives.

There was a theory widely believed at the turn of the last century that all functions were, in fact, primitive recursive.

Ackermann provided the counterexample named after him back in 1928, thereby proving such beliefs to be false.

At some level, computers implement everything via state machines, and so there is a sense in which they're "not doing things in a manner that is aware of recursion." But that is normally as blandly useless as is the use of "Turing equivalence" to argue that any programming language is as good as any other.

There is _some_ sense in which it is true, but immediately that you have to read and write code, that sense disappears.

-- 
let name="cbbrowne" and tld="gmail.com" in String.concat "_at_" [name;tld];;
http://linuxdatabases.info/info/slony.html
"When we write programs that "learn", it turns out that we do and they
don't." -- Alan Perlis