Cagdas Ozgenc wrote:
Is it possible to encode an array using lamda terms only, and recover the term specified by an index term in O(1) time?
I'd like to go on a limb and argue that there is generally no such thing as O(1) array access operation. On the conventional hardware, the fastest access to the i-th element of an array 'ar' is expressed by the following formula, which underlies C "arrays": ar[i] = *(ar + i) 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). 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.
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.