🚀 go-pugleaf

Hi,

does anyone out there in netland know whether it is possible to write a Prolog
program that 

(1) *generates* natural numbers in ascending order,
(2) does not make use of side effects (assert, retract etc.),
(3) generates the first n numbers in time O(n).

The toplevel predicate should be nat(X), which is of course invoked with X
uninstantiated. Any number of additional predicates are admitted. Note that
the program should be self-contained, i.e. I'm not interested in programs
like

	next_nat(X,Y) :- Y is X+1.

which leave it to the responsibiliy of the calling program to "conserve" the
last number generated until the time the next number is needed.

Be warned that complexity can creep in through your backdoor - especially if
you use many auxiliary predicates. The number of exits and redos and the number
of variable renamings needed to get at the next number deep within a recursion
also take time and count therefore!

Alternatively I would very much appreciate a negative result - preferably in
the form of a proof.

Please, post your contributions to this notes group or mail to:

UUCP: ...!mcvax!unido!uklirb!noekel