# Is there a space efficient way to represent numbers on the lambda calculus?

This is something I've been thinking. While it is agreed that Lambda Calculus is equivalent to a Turing Machine in power, is it actually so? Church Numerals are not very space efficient and I'm not aware of any better way to represent numbers using the LC. This leads me to the intuitive conclusion that, while, theorically, LC is as powerful as a TM, there is a natural limit that states that a program in LC will never be able to compute natural numbers as fast as a TM, given a physical world and limited resources.

Now I've throw many ideas and it is hard to define most of what I'm saying formally, but does that intuition make any sense?

• Consider: the cells in a Turing machine can only hold a finite amount of information, whereas a lambda term can be arbitrarily large. – Dave Clarke Sep 12 '13 at 7:45
• Furthermore, machines in the "real world" give the appearance of having constant-time operations like addition and array lookup, which they only achieve by having specific finite limits on the numbers they range over. – Paul Stansifer Sep 12 '13 at 16:21
• if you are interested in the physical world & limited resources, yet an abstract/theoretical study, try cache-oblivious algorithms. also, theres a whole branch of study of efficient implementations of arithmetic using integers or floating point numbers etc... the question seems to combine two concepts at the opposite end of the spectrum which dont really mix... – vzn Sep 13 '13 at 4:40
• doesn't a byte map directly to an element of a product of 8 logarithmic coproducts? in a way, native representation of numbers in the cpu circuits are done in a functional way; as a list of bits(otherwise we would have instructions to access bits directly without masking). so I see no reason why it would be any slower; the parser should be able to map byte(0)(0)(0)(0)(0)(0)(0)(1)() to native byte 1 easily if you allow it to toss out the abstract representation and map it to native representation. – Dmitry Feb 7 '17 at 0:34

If I am not mistaken the simulations between Turing machines and $\lambda$-calculus can be accomplished with a polynomial-time slowdown. Of course, for this to make sense we need to specify an evaluation strategy and measure of cost for $\lambda$-calculus but I am sure something reasonable can be found.
You ask about numbers in particular. Of course Church encodings are inefficient but they are only one possibility. In $\lambda$-calculus we can encode finite lists and the constants true and false. With these numbers can be encoded in binary as lists of boolean values, which gives an efficient representation. The charm of Church encodings is in their elegance.