[cap-talk] Bounded Computation (was Re: where(), and a mobile-code JS-over-Python experiment)

[Brian Warner]

Ben Laurie wrote:
> 
> 
> On 11 April 2010 21:17, Brian Warner <warner at lothar.com
> <mailto:warner at lothar.com>> wrote:
> 
>     The #3 approach, while probably infeasible, is interesting to think
>     about. Imagine a function that maps size of the input code to the number
>     of CPU cycles it will take to run. What influences this function? If you
>     pretend that CPU cycles are an authority, then subroutines which use a
>     lot of them are a larger authority than low-complexity subroutines. A
>     for-loop becomes high-authority if it has access to large counter
>     values, making large integers into large authorities too. Imagine a
>     language in which you had addition but not multiplication,
>     exponentiation, or factorial functions: would you wind up with a mostly
>     linear relationship between size of the program and cycles needed to
>     execute? And if you then imposed a limit on the size of the program,
>     you'd get some corresponding limit to the number of cycles it could
>     consume. Access to super-linear-complexity subroutines would allow the
>     program to exhibit super-linear codesize-to-cycles behavior, so denying
>     ambient access to them would keep it linear.
> 
> 
> I think the Ackermann function pretty convincingly rules out any such
> possibility.

You know, I was going to cite that one, since it certainly is a way to
express a huge number with very small inputs: A(4,2) is almost 10^20000.
But it's defined in terms of recursion, and if this hypothetical
language subset forbids recursion (and I suppose function calls too, to
prevent you from recreating it with mutual recursion like A->B->A->B..),
then you'd have to unroll the whole thing in your source code, which
would bring the size-of-code--to--size-of-data relationship back into line.

 http://en.wikipedia.org/wiki/Ackermann_function


I must admit I'm not clear on the difference between recursive and
"primitive recursive", though, which might have a bearing on this stuff.
And anyways, a language in which you aren't allowed to make function
calls is pretty limiting.

cheers,
 -Brian