En representación de negativos y complejos de números usando el cálculo lambda

Question

La mayoría de los tutoriales en cálculo lambda proporcionar ejemplo en números enteros positivos y booleanos pueden ser representados por funciones. ¿Qué pasa con -1 y i?

Answer 1

Primera codificar números naturales y pares, como se describe por Jmad.

representan un número entero $ k $ como un par de números naturales $ (a, b) $ tal que $ k = a - b $. A continuación, puede definir las operaciones habituales de números enteros como (usando la notación de Haskell por $ \ 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)

El caso de los números complejos es similar en el sentido de que un número complejo se codifica como un par de números reales. Pero una cuestión más complicada es cómo codificar reales. Aquí usted tiene que hacer más trabajo:

1. codificar un número racional $ q $ como un par $ (k, a) $ donde $ k $ es un número entero, $ a $ es natural, y $ q = k / (1 + a) $.
2. Codificar un número real $ x $ por una función $ f $ tales que por cada $ naturales k \ in \ mathbb {N} $, $ f k $ codifica un número racional $ q $ tal que $ | x - q | <2 ^ {- k} $. En otras palabras, un verdadero se codifica como una secuencia de números racionales que convergen a la misma a una velocidad $ k \ mapsto 2 ^ {- k}. $

La codificación de números reales es mucho trabajo y no quieren hacerlo realmente en el $ \ lambda $ -calculus. Pero ver por ejemplo el subdirectorio de etc/haskell Marshall para una simple aplicación de reales en el más puro Haskell. Esto podría, en principio, ser traducido a la pura $ \ lambda $ -calculus.

Answer 2

Lambda-cálculo pueden codificar la mayoría de las estructuras de datos y tipos básicos. Por ejemplo, puede codificar un par de términos existente en el cálculo lambda, usando el mismo Church codificación que se ve generalmente para codificar números enteros no negativos y booleano:

$$ \ mbox {par} = $$ ?xyz.zxy $$ \ mbox {} FST = ?p.p (?xy.x) $$ $$ \ mbox {SND} = ?p.p (?xy.y) $$

A continuación, el par $ (a, b) $ es $ p = (\ mbox {par} ab) $ y si desea obtener una copia de $ a $ y $ b $ que puede hacer $ (\ mbox {fst} p) $ y $ (\ mbox {} p sND) $.

Esto significa que usted puede fácilmente representar números enteros positivos y negativos con un par: el signo de la izquierda y el valor absoluto de la derecha. El signo es ser un valor booleano que especifica si el número es positivo. El derecho es un número natural usando codificación Iglesia.

$$ (signo, n) $$

Y ahora que tiene los enteros relativos. La multiplicación es fácil de definir, sólo hay que aplicar el $ \ mbox {} $ xor función en el signo y la multiplicación en números naturales en el valor absoluto:

$$ \ mbox {mult} _Z = ?ab. \ Mbox {par} ~~ (\ mbox {xor} (\ mbox {fst} a) (\ mbox {fst} b)) ~~ (\ mbox {mult} _N (\ mbox {SND} a) (\ mbox {SND} b)) $$

Para definir la adición, usted tiene que comparar dos números naturales y el uso de sustracción cuando los signos son diferentes, por lo que este no es un ? plazo, pero se puede adaptar si realmente desea:

$$ \ mbox {add} = _Z ?ab. \ Left \ {\ begin {array} {ll} (\ Mbox {true}, \ mbox {add} _N (\ mbox {} SND a) (\ mbox {SND} b)) y \ mbox {si} \\ a=0?b=0 (\ Mbox {false}, \ mbox {add} _N (\ mbox {SND} a) (\ mbox {SND} b)) y \ mbox {if} a <0?b <0 \\ (\ Mbox {true}, \ mbox {sub} _N (\ mbox {SND} a) (\ mbox {SND} b)) y \ mbox {if} a=0?b <0? | un | = | b | \\ (\ Mbox {false}, \ mbox {sub} _N (\ mbox {SND} b) (\ mbox {} SND a)) y \ mbox {si} a=0?b <0? | a | <| b | \\ (\ Mbox {true}, \ mbox {sub} _N (\ mbox {SND} b) (\ mbox {} SND a)) y \ mbox {si} un <0?b=0? | a | <| b | \\ (\ Mbox {false}, \ mbox {sub} _N (\ mbox {SND} a) (\ mbox {SND} b)) y \ mbox {if} a <0?b=0? | a | = | b | \\ \ End {array} \ right. $$

pero luego la resta es muy fácil de definir:

$$ \ mbox {minus} _Z = ?a. \ Mbox {par} (\ mbox {no} (\ mbox {fst} a)) (\ mbox {SND} a) $$ $$ \ mbox {sub} _Z = ?ab. \ Mbox {add} _Z (a) (\ mbox {minus} _Zb) $$

Una vez que tenga los números enteros positivos y negativos que se pueden definir enteros complejos muy fácilmente: es sólo un par de dos enteros $ (a, b) que representa $ $ a + b \ mbox {i} $. Entonces Además es punto a gota y la multiplicación es como de costumbre , pero no voy a escribirlo, debería ser fácil :

$$ \ mbox {add} _ {Z [\ mbox {i}]} = ?z_1z_2. \ Mbox {par} (\ Mbox {add} _Z (\ mbox {} FST z_1) (\ mbox {} FST Z_2)) (\ Mbox {add} _Z (\ mbox {} SND z_1) (\ mbox {} SND Z_2)) $$