Content deleted Content added
GreenC bot (talk | contribs) Move 1 url. Wayback Medic 2.5 per WP:URLREQ#angelfire.com |
Changed hypen to en dash. |
||
Line 48:
Moreover, in lambda calculus, notions such as '3' and '{{tmath|*}}' can be represented without any need for externally defined primitive operators or constants. It is possible to identify terms in lambda calculus, which, when suitably interpreted, behave like the number 3 and like the multiplication operator, q.v. [[Church encoding]].
Lambda calculus is known to be computationally equivalent in power to many other plausible models for computation (including [[Turing machine]]s); that is, any calculation that can be accomplished in any of these other models can be expressed in lambda calculus, and vice versa. According to the [[
It is perhaps surprising that lambda-calculus can represent any conceivable computation using only the simple notions of function abstraction and application based on simple textual substitution of terms for variables. But even more remarkable is that abstraction is not even required. ''Combinatory logic'' is a model of computation equivalent to lambda calculus, but without abstraction. The advantage of this is that evaluating expressions in lambda calculus is quite complicated because the semantics of substitution must be specified with great care to avoid variable capture problems. In contrast, evaluating expressions in combinatory logic is much simpler, because there is no notion of substitution.
| |||