5
$\begingroup$

The question is just what is on the title, but I'll describe the context for completion:

Natural numbers can be encoded quite elegantly on the Lambda Calculus as church numbers, that is, a function applied to an argument N times:

0 = (λ f x → x)
1 = (λ f x → f x)
2 = (λ f x → f (f x)))
3 = (λ f x → f (f (f x))))

That representation gives us a very simple formulas to addition, multiplication and exponentiation:

add = λ n f x → f (n f x)
mul = λ m n f → m (n f)
exp = λ m n → n m

The representation of their inverses is not as straightforward, though. Division implementations either require recursion through the Y-combinator, or are huge formulas. This makes me suspect that church numbers are not an ideal representation of fractionals, so I've been looking for a better alternative. I guess the problem is fundamental: there is something about the nature of numbers I am missing. This is why I ask the following question: is there any kind of system/encoding in which fractional numbers can be represented elegantly? One for which algorithms such as division, logarithm and sine are as simple as the add, mul and exp above?

Put short, what is the most elegant representation of fractional numbers you know?

$\endgroup$
  • $\begingroup$ Sine is never going to be a simple formula, because its output isn't anything like a natural number. Note that the exp you've listed isn't a one-argument function (i.e., $e^x$) but a two-argument function ($m^n$); it's 'combinatorial' exponentiation, not 'analytic' $\endgroup$ – Steven Stadnicki Feb 24 '15 at 1:11
  • $\begingroup$ If the solution is restricted to formalizations in Lambda Calculus then it would be helpful to mention that in the title. $\endgroup$ – Bill Dubuque Feb 24 '15 at 1:14
  • $\begingroup$ True! But what about division and log? For those willing to answer, I'm looking for an enlightenment more than anything else. "Why there is not a simple formula? Maybe it has something to do with the fact they are inverses, and the lambda calculus is unidirectional? Maybe unification has something to do with it? Or maybe it is just that church numbers are a bad representation for this, and another representation has simple algorithms?" Those are things I've been thinking as a non-mathematician. Texts and references are more than welcome. $\endgroup$ – MaiaVictor Feb 24 '15 at 1:15
  • $\begingroup$ @BillDubuque it is not! I'm completely open for alternative systems. Just used what I know for example. Maybe the lambda calculus is not the best way to express it? So what would be? Is there a more elegant system? Can it be used for computation? Etc., etc. - I have so many questions and so few answers. $\endgroup$ – MaiaVictor Feb 24 '15 at 1:16

Your Answer

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

Browse other questions tagged or ask your own question.