[cap-talk] Bounded Computation (was Re: where(), and a mobile-code JS-over-Python experiment)
warner at lothar.com
Sun Apr 11 22:46:18 PDT 2010
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
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.
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.
More information about the cap-talk