3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Consider: the cells in a Turing machine can only hold a finite amount of information, whereas a lambda term can be arbitrarily large. $\endgroup$
    – Dave Clarke
    Sep 12 '13 at 7:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paul Stansifer
    Sep 12 '13 at 16:21
  • $\begingroup$ 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... $\endgroup$
    – vzn
    Sep 13 '13 at 4:40
  • $\begingroup$ 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. $\endgroup$
    – Dmitry
    Feb 7 '17 at 0:34
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – MaiaVictor
    Sep 12 '13 at 10:41
  • 8
    $\begingroup$ A Turing machine cannot access bits on a tape any faster either, so what is your point? $\endgroup$
    – Andrej Bauer
    Sep 12 '13 at 10:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Charles Stewart
    Sep 17 '13 at 15:17
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.