[Haskell-cafe] Criteria for determining if a recursive function
can be implemented in constant memory
Andrew Coppin
andrewcoppin at btinternet.com
Mon Jul 5 14:33:51 EDT 2010
Tillmann Rendel wrote:
> Hi Steffen,
>
> Steffen Schuldenzucker wrote:
>> Given the definition of a recursive function f in, say, haskell,
>> determine if f can be implemented in O(1) memory.
>
> Constant functions are implementable in O(1) memory, but interpreters
> for turing-complete languages are not, so the property of being
> implementable in O(1) memory is non-trivial and therefore, by Rice's
> theorem, undecidable.
Damn Rice's theorum, spoiling everybody's fun all the time... ;-)
Of course, as I understand it, all the theorum says is that no single
algorithm can give you a yes/no answer for *every* possible case. So the
next question is "is it decidable in any 'interesting' cases?"
Then of course you have to go define 'interesting'...
More information about the Haskell-Cafe
mailing list