Is it possible to encode an array using lamda terms only, and recover the term specified by an index term in O(1) time (in other words in one step reduction, without cheating using several steps behind the scenes)?

depends a bit on your definitions, doesn't it? if you take lambda with unary abstractions only,

it is going to be rather difficult; if you take lambda with n-ary abstractions, it is going to be

rather easy, assuming you mean constant-steps, not single-step (typically, access to function

parameters is implemented via a single instruction, directly indexing into some parameter

structure, which is little different from array access - you can play with the idea in Haskell,

so it's not even off topic;-).

hth,

claus