[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail recursion

   Date: Mon, 23 Apr 90 16:50:51 CDT
   From: harrison@sp21.csrd.uiuc.edu (Luddy Harrison)

   >>   for every program state P,
   >>      if continued execution eventually causes state P to recur,
   >>         and every non-tail-recursive evaluation begun since
   >>             the first occurrence of state P has completed
   >>             before the second occurrence of state P
   >>      then state P will recur indefinitely many times without
   >>	 running out of resources

   This is a wonderful definition.  It appears, however, to have a hole
   through which a tricky implementation would be entitled to jump.  It
   would permit me to be very consumptive of resources, could I
   demonstrate that the repitition of states was impossible for an input


Yeah, but I suspect that the lurking possibility of having to handle the
halting problem in the general case will tend to keep implementors honest.
It will simply be easier to be reasonable than to cheat.