Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> So what's the smallest limitation you could impose on the programs to 
>> make it possible to solve them all?
> 
>   I don't know, but I would bet that if you can't loop nor recurse, that's
> a pretty safe bet.

You can loop if you can prove a bound on the looping; i.e., a Pascal style 
for-loop, or any loop with a loop variant (in the technical sense of that term).

You can recurse as long as you always have an upper bound on the recursion.

You can also prove it if your language disallows dynamic allocation, 
including not having unboundedly-large integers.  Think of some of the 
original microcomputer BASIC interpreters, with 26 16-bit variables to work 
with. You could still loop forever, but if you run more than 26^2^16 steps, 
you're looping.

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message