Darstellung negativer und komplexer Zahlen mit Lambda -Kalkül darstellen

Question

Die meisten Tutorials zu Lambda Calculus bieten ein Beispiel, in dem positive Ganzzahlen und Boolesche durch Funktionen dargestellt werden können. Was ist mit -1 und mir?

Answer 1

Kodieren Sie zuerst natürliche Zahlen und Paare, wie von JMAD beschrieben.

Stellen Sie eine Ganzzahl $ k $ als ein Paar natürlicher Zahlen $ (a, b) $ dar, so dass $ k = a - b $. Anschließend können Sie die üblichen Operationen von Ganzzahlen als (mit Haskell-Notation für $ lambda $ -Calculus) definieren:

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)

Der Fall komplexer Zahlen ist in dem Sinne ähnlich, dass eine komplexe Zahl als Realpaar kodiert wird. Eine kompliziertere Frage ist jedoch, wie man Realis codiert. Hier müssen Sie mehr Arbeit machen:

1. Codieren eine rationale Nummer $ q $ als Paar $ (k, a) $ wobei $ k $ eine Ganzzahl ist, $ a $ ist natürlich und $ q = k / (1 + a) $.
2. Codieren eine reelle Nummer $ x $ nach einer Funktion $ f $ so, dass für jedes natürliche $ k in mathbb {n} $ $ fk $ eine rationale Nummer $ $ $ codiert, dass $ | x - q | <2^{-k} $. Mit anderen Worten, ein Real wird als eine Abfolge von Rationalen codiert, die mit dem Preis $ K MapSto 2^{-k} $ konvergieren.

Codierung von Reals ist eine Menge Arbeit und Sie möchten es nicht im $ lambda $ -Calculus tun. Aber siehe zum Beispiel die etc/haskell Unterverzeichnis von Marshall Für eine einfache Implementierung von Real in reinem Haskell. Dies könnte im Prinzip in das reine $ lambda $ -Calculus übersetzt werden.

Answer 2

Lambda-Kalkulus kann die meisten Datenstrukturen und Grundtypen codieren. Zum Beispiel können Sie Ein Paar codieren der bestehenden Begriffe im Lambda -Kalkül, mit demselben Kirchenkodierung dass Sie normalerweise nicht negative Ganzzahlen und Boolesche codieren:

$$ mbox {pair} = λxyz.zxy $$ $$ mbox {fst} = λp.p (λxy.x) $$ $$ mbox {snd} = λp.p (λxy.y) $$

Dann ist das Paar $ (a, b) $ $ p = ( mbox {pair} ab) $ und wenn Sie zurückbekommen $ A $ und $ B $, können Sie $ ( mbox {fst} p) $ machen und $ ( mbox {snd} p) $.

Das bedeutet, dass Sie leicht positive und negative Ganzzahlen mit einem Paar darstellen können: das Zeichen links und den absoluten Wert auf der rechten Seite. Das Zeichen ist ein Boolescher, der angegeben hat, ob die Zahl positiv ist. Das Recht ist eine natürliche Zahl mit der Kirchencodierung.

$$ (Zeichen, n) $$

Und jetzt, wo Sie relative ganze Zahlen haben. Die Multiplikation ist leicht zu definieren, Sie müssen nur die Anwendung anwenden $ mbox {xor} $ Funktion auf dem Schild und dem Multiplikation mit natürlichen Zahlen auf den absoluten Wert:

$$ mbox {mult} _ℤ = λab. mbox {pair} ~~ ( mbox {xor} ( mbox {fst} a) ( mbox {fst} b) ~~ ( mbox {mult} _ℕ ( mbox {snd} a) ( mbox {snd} b)) $$

Um die Zugabe zu definieren, müssen Sie zwei natürliche Zahlen vergleichen und die Subtraktion verwenden, wenn die Zeichen unterschiedlich sind. Dies ist also kein λ-Term, aber Sie können sie anpassen, wenn Sie wirklich:

$$ mbox {add} _ℤ = λab. links { begin {array} {ll} ( mbox {true}, mbox {add} _ℕ ( mbox {snd} a) ( mbox {snd} b)) & mbox {if} a ≥ 0∧b ≥ 0 ( mbox {false}, mbox {add} _ℕ ( mbox {snd} a) ( mbox {snd} b) & mbox {if} a <0∧b <0 ( mbox {true}, mbox {sub} _ℕ ( mbox {snd} a) ( mbox {snd} b)) & mbox {if} a ≥0∧b <0∧ | a | ≥ | B | ( mbox {false}, mbox {sub} _ℕ ( mbox {snd} b) ( mbox {snd} a)) & mbox {if} a ≥ 0∧b <0∧ | a | <| <| < | b | ( mbox {true}, mbox {sub} _ℕ ( mbox {snd} b) ( mbox {snd} a)) & mbox {if} a <0∧b ≥ 0∧ | a | <| < | b | ( mbox {false}, mbox {sub} _ℕ ( mbox {snd} a) ( mbox {snd} b)) & mbox {if} a <0∧b ≥ 0∧ | A | | b | end {Array} rechts. $$

Aber dann ist Subtraktion wirklich leicht zu definieren:

$$ mbox {minus} _ℤ = λa. mbox {pair} ( mbox {nicht} ( mbox {fst} a)) ( mbox {snd} a) $$ $$ mbox {sub} _ℤ = λab. mbox {add} _ℤ (a) ( mbox {minus} _ℤb) $$

Sobald Sie positive und negative Ganzzahlen haben, können Sie definieren Komplexe Ganzzahlen Sehr leicht: Es ist nur ein Paar von zwei Ganzzahlen $ (a, b) $, was $ a+b mbox {i} $ repräsentiert. Dann ist Addition punktuell und die Multiplikation ist wie gewöhnlich, aber ich werde es nicht schreiben, es sollte einfach sein:

$$ mbox {add} _ {ℤ [ mbox {i}]} = λz_1z_2. mbox {pair} ( mbox {add} _ℤ ( mbox {fst} z_1) ( mbox {fst} z_2))) ( mbox {add} _ℤ ( mbox {snd} z_1) ( mbox {snd} z_2)) $$