Is there a space efficient way to represent numbers on the lambda calculus? - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-20T12:09:25Z https://cstheory.stackexchange.com/feeds/question/18953 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/18953 3 Is there a space efficient way to represent numbers on the lambda calculus? MaiaVictor https://cstheory.stackexchange.com/users/17388 2013-09-12T07:09:56Z 2013-09-12T18:11:47Z <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> https://cstheory.stackexchange.com/questions/18953/-/18954#18954 11 Answer by Andrej Bauer for Is there a space efficient way to represent numbers on the lambda calculus? Andrej Bauer https://cstheory.stackexchange.com/users/705 2013-09-12T09:38:15Z 2013-09-12T09:38:15Z <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> https://cstheory.stackexchange.com/questions/18953/-/18964#18964 5 Answer by David Richerby for Is there a space efficient way to represent numbers on the lambda calculus? David Richerby https://cstheory.stackexchange.com/users/17082 2013-09-12T18:11:47Z 2013-09-12T18:11:47Z <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>