Representing Negative and Complex Numbers Using Lambda Calculus

Problem Detail: 

Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?

Asked By : zcaudate

Answered By : Andrej Bauer

First encode natural numbers and pairs, as described by jmad.

Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus):

neg = \k -> (snd k, fst k) add = \k m -> (fst k + fst m, snd k + snd m) sub = \k m -> add k (neg m) mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m) 

The case of complex numbers is similar in the sense that a complex number is encoded as a pair of reals. But a more complicated question is how to encode reals. Here you have to do more work:

1. Encode a rational number $q$ as a pair $(k,a)$ where $k$ is an integer, $a$ is natural, and $q = k / (1 + a)$.
2. Encode a real number $x$ by a function $f$ such that for every natural $k \in \mathbb{N}$, $f k$ encodes a rational number $q$ such that $|x - q| < 2^{-k}$. In other words, a real is encoded as a sequence of rationals converging to it at the rate $k \mapsto 2^{-k}$.

Encoding reals is a lot of work and you do not want to actually do it in the $\lambda$-calculus. But see for example the etc/haskell subdirectory of Marshall for a simple implementation of reals in pure Haskell. This could in principle be translated to the pure $\lambda$-calculus.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2272