arrays and lamda terms

[Cagdas Ozgenc]

> The formula involves the addition of two numbers -- which is,
> generally, a O(log(n)) operation. Granted, if we operate in the
> restricted domain of mod 2^32 integers, addition can be considered
> O(1). If we stay in this domain however, the size of all our arrays is
> limited to M (which is 2^32, often less). If we implement our arrays
> as linked lists, the cost of accessing one element will not exceed
> M*2*cost(dereference), which is constant, which is O(1). Thus
> pedantically speaking, within the restricted integral domain, any
> terminating array access method is O(1).

Yes but then it will unstable complexity, whereas usually when "array
access" is considered worst/best/average case complexity are equal(i.e. one
can write a program to a hard realtime system). With linked list
implementation you'll never have that.

> The choice of "hardware" may greatly affect the apparent
> complexity. For example, associative memory access is difficult on
> conventional architectures and fast for holographic memory.

Very true.

> > Or is it possible in any rewriting system?
>
> If all your arrays are limited in size to 2^32, and if your re-writing
> system offers projection operators pi_0, pi_1, ... pi_4294967295
> (i.e., the right "hardware"), well, then it is possible.

The projection operators all should take equal amount of reduction steps.
So, does that mean it is not possible to do this in lamda calculus if the
hardware only supports alpha,beta reduction for example (and without
cheating behind the scenes for projection functions)?