Was bringt es ,

Was ist der Unterschied, wenn man Kalkül eine Algebra anstelle eines Kalküls nennt ? Ich stelle diese Frage, weil ich irgendwo die Zeile " λ- Kalkül ist kein Kalkül, sondern eine Algebra" gelesen habe (iirc, Dana Scott zugeschrieben). Was ist der Sinn? Vielen Dank.$\lambda$$\lambda$

Ein Kalkül ist ein Berechnungssystem, das auf der Manipulation symbolischer Ausdrücke basiert. Eine Algebra ist ein System symbolischer Ausdrücke und Beziehungen zwischen ihnen [*]. Das heißt, ein Kalkül ist ein System zum Herausfinden von Antworten, und eine Algebra ist eine Möglichkeit, die Beziehungen zwischen Begriffen auszudrücken.

Der Kalkül ist entweder ein Kalkül oder eine Algebra, je nachdem, ob Sie die β- und η- Regeln als orientierte Reduktionsregeln oder als nicht orientierte Gleichungen betrachten möchten . Wenn Sie die Regeln als orientiert betrachten, haben Sie eine Bewertungsreihenfolge festgelegt, und die Regeln zeigen Ihnen, wie Sie einen Begriff nehmen und eine normale Form erstellen. Wenn Sie die Regeln als unorientiert betrachten, erhalten Sie die Gleichheitsrelation für λ- Terme.$\lambda$$\beta$$\eta$$\lambda$

[*] Es gibt auch eine kategoriale Definition der Algebra, die etwas restriktiver ist als die informelle Idee. Der Unterschied besteht im Großen und Ganzen darin, dass die formale Definition der Algebra nur solche Systeme ohne variable Bindung umfasst. SKI-Kombinatoren bilden also eine Algebra, der Kalkül jedoch nicht.$\lambda$

Traditionell ist eine Algebra ein Trägersatz mit Operationen, die einige Gleichungen erfüllen (denken Sie an "Gruppe"). Es gibt viele Möglichkeiten, wie der Begriff verallgemeinert werden kann:

• $M$$R$$E$$V$$s : E \to V$$E \to V$

• $x \neq 0 \implies x \cdot x^{-1} = 1$

• $M$

$\lambda$$\beta$$\eta$

Es gibt eine ziemlich genaue Definition dessen, was eine Algebra in der Kategorietheorie ist: siehe diesen Artikel zum Beispiel. Es dauerte einige Jahre, um zu verstehen, wie eine Struktur mit gebundenen Variablen im selben Kontext wie der in Mathematik und Informatik gebräuchliche Begriff Algebra-Struktur verstanden werden kann , und es stellt sich heraus, dass das kategoriale Konzept der F-Algebren in der Lage ist, die zu vereinheitlichen zwei. Ich bin mir über die historischen Aspekte der Lösung nicht sicher, aber ein möglicher Ansatz sind die von Fiore, Plotkin und Turi ( hier verfügbar ) eingeführten Presheaf-Algebren, die die Frage geklärt und unterschiedliche, aber ähnliche Ansätze angestoßen haben , siehe z . B. Hirshowitz et al. und seine Doktorandin Julianna Zsido .

$\lambda$

Während der Begriff "Kalkül" zwar weniger genau definiert ist als der Begriff "Algebra", impliziert "Kalkül" im Allgemeinen einen Berechnungsprozess, während Algebren Konstruktionsmuster mit Gleichungstheorien aufweisen.
Man könnte sagen, es besteht eher das Gefühl, dass Algebren als Strukturen "bereits existieren", und wir decken lediglich Wahrheiten über sie auf, anstatt eine Methode zu verwenden, um neue Antworten zu erhalten, die vorher nicht existierten.

Wenn Sie darüber nachdenken, was Scott mit Scott-Domänen erreichen wollte, ist seine Aussage sinnvoll: Er hat versucht, vordefinierte mathematische und algebraische Strukturen zu finden, die als feste Semantik für LC dienen. Er wollte das Gefühl beseitigen, dass die Bedeutung eines Begriffs das war, was aus einem bestimmten Prozess hervorging.

Möglicherweise interessiert Sie eine frühere Antwort auf eine verwandte Frage: Was macht eine Denotationssemantik aus?

$\beta$$\eta$$M$$N$

Wenn Scott Lambda-Kalkül jemals als "Algebra" bezeichnet hätte (was ich eher bezweifle), dann hätte er einen ziemlich subtilen Punkt gemacht, nämlich, dass man sich Lambda-Kalkül als a priori- Bedeutung vorstellen kann .

Trotzdem würde es ihm schwer fallen, Algebraisten von seiner Behauptung zu überzeugen, da er keine Gleichungen in der Lambda-Rechnung hat, sondern Äquivalenzen (dh auf Metaebene). "Kombinatorische Algebra" ist dagegen völlig normal.

Es gibt keinen Kalkül , aber es gibt ein genau definiertes mathematisches Objekt namens Algebra , obwohl das Wort viele Verwendungszwecke hat . Ich vermute jedoch, dass der Name im Sinne von gegeben wurde

(...) die abstrakte Untersuchung von Zahlensystemen und Operationen in ihnen.

$\lambda$