<p>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 <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/">something reasonable can be found</a>.</p>

<p>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 <code>true</code> and <code>false</code>. 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.</p>

CC BY-SA 3.0
2013-09-12T10:41:11.290Z
But then for accessing those lists you'd be limited at O(n). Then I can't see how adding could be fast enough. Woudln't this in the end be even more inefficient ?
MaiaVictor
CC BY-SA 3.0
2013-09-12T10:49:50.277Z
A Turing machine cannot access bits on a tape any faster either, so what is your point?
Andrej Bauer
CC BY-SA 3.0
2013-09-17T15:17:44.050Z
There's are some rather suggestive observations in Asperti & Guerrini (1998, *The Optimal Implementation of Functional Programming Languages*) that seem to indicate that if you operationalise the lambda calculus using optimal-reduction sharing graphs, then the size of the graph you get for the normal forms of calculations formalised as problems using Church numerals (and lists, etc.) will be linearly bounded by the size of the input term plus the the value of the result.  Unfortunately, no one can prove anything much about cyclic sharing graphs, but I would call this a conjecture.
Charles Stewart
CC BY-SA 3.0
2013-09-12T09:38:15.993Z
2013-09-12T09:38:15.993Z
Andrej Bauer
<p>To say that Turing machines and the lambda calculus have equivalent power means that they compute/define the same class of functions, which is a pretty coarse-grained equivalence. If you want to consider efficiency, then you've moved from computability theory to complexity theory and you're looking at a finer-grained equivalence.</p>

CC BY-SA 3.0
2013-09-12T18:11:47.023Z
2013-09-12T18:11:47.023Z
David Richerby
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-09-12T07:45:14.387Z
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
CC BY-SA 3.0
2013-09-12T16:21:39.057Z
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
CC BY-SA 3.0
2013-09-13T04:40:59.977Z
if you are interested in the physical world & limited resources, yet an abstract/theoretical study, try [cache-oblivious algorithms](http://en.wikipedia.org/wiki/Cache-oblivious_algorithm). 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
CC BY-SA 3.0
2017-02-07T00:34:06.473Z
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.
Dmytro
<pl.programming-languages><lambda-calculus>
Is there a space efficient way to represent numbers on the lambda calculus?
MaiaVictor
# Is there a space efficient way to represent numbers on the lambda calculus?

(Asked by: username_0 on 2013-09-12)

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?

**Tags:** pl.programming-languages, lambda-calculus

> **Comments:**
> **username_1**: Consider: the cells in a Turing machine can only hold a finite amount of information, whereas a lambda term can be arbitrarily large.  
> **username_2**: 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.  
> **username_3**: if you are interested in the physical world & limited resources, yet an abstract/theoretical study, try [cache-oblivious algorithms](http://en.wikipedia.org/wiki/Cache-oblivious_algorithm). 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...  
> **username_4**: 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.  

---

## 2 answers

### Answer by username_5 on 2013-09-12. Score: 11

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](http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/).

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.

> **Comments:**
> **username_0**: But then for accessing those lists you'd be limited at O(n). Then I can't see how adding could be fast enough. Woudln't this in the end be even more inefficient ?  
> **username_5**: A Turing machine cannot access bits on a tape any faster either, so what is your point?  
> **username_6**: There's are some rather suggestive observations in Asperti & Guerrini (1998, *The Optimal Implementation of Functional Programming Languages*) that seem to indicate that if you operationalise the lambda calculus using optimal-reduction sharing graphs, then the size of the graph you get for the normal forms of calculations formalised as problems using Church numerals (and lists, etc.) will be linearly bounded by the size of the input term plus the the value of the result.  Unfortunately, no one can prove anything much about cyclic sharing graphs, but I would call this a conjecture.  

---

### Answer by username_7 on 2013-09-12. Score: 5

To say that Turing machines and the lambda calculus have equivalent power means that they compute/define the same class of functions, which is a pretty coarse-grained equivalence. If you want to consider efficiency, then you've moved from computability theory to complexity theory and you're looking at a finer-grained equivalence.


---

