Also known, roughly speaking, as confluence or the Church-Rosser property.
From “NYU Lambda Seminar, Week 2” —
[See also the parent page Seminar in Semantics / Philosophy of Language or:
What Philosophers and Linguists Can Learn From Theoretical Computer Science But Didn’t Know To Ask)]
A computational system is said to be confluent, or to have the Church-Rosser or diamond property, if, whenever there are multiple possible evaluation paths, those that terminate always terminate in the same value. In such a system, the choice of which sub-expressions to evaluate first will only matter if some of them but not others might lead down a non-terminating path.
The untyped lambda calculus is confluent. So long as a computation terminates, it always terminates in the same way. It doesn’t matter which order the sub-expressions are evaluated in.
A computational system is said to be strongly normalizing if every permitted evaluation path is guaranteed to terminate. The untyped lambda calculus is not strongly normalizing: ω ω doesn’t terminate by any evaluation path; and (\x. y) (ω ω) terminates only by some evaluation paths but not by others.
But the untyped lambda calculus enjoys some compensation for this weakness. It’s Turing complete! It can represent any computation we know how to describe. (That’s the cash value of being Turing complete, not the rigorous definition. There is a rigorous definition. However, we don’t know how to rigorously define “any computation we know how to describe.”) And in fact, it’s been proven that you can’t have both. If a computational system is Turing complete, it cannot be strongly normalizing.
There is no connection, apart from the common reference to an elementary geometric shape, between the use of “diamond” in the above Church-Rosser sense and the use of “diamond” in the mathematics of (Cullinane’s) Diamond Theory.
Any attempt to establish such a connection would, it seems, lead quickly into logically dubious territory.
Nevertheless, in the synchronistic spirit of Carl Jung and Arthur Koestler, here are some links to such a territory —
Link One — “Insane Symmetry” (Click image for further details)—
See also the quilt symmetry in this journal on Christmas Day.
Link Two — Divine Symmetry
(George Steiner on the Name in this journal on Dec. 31 last year (“All about Eve“)) —
“The links are direct between the tautology out of the Burning Bush, that ‘I am’ which accords to language the privilege of phrasing the identity of God, on the one hand, and the presumptions of concordance, of equivalence, of translatability, which, though imperfect, empower our dictionaries, our syntax, our rhetoric, on the other. That ‘I am’ has, as it were, at an overwhelming distance, informed all predication. It has spanned the arc between noun and verb, a leap primary to creation and the exercise of creative consciousness in metaphor. Where that fire in the branches has gone out or has been exposed as an optical illusion, the textuality of the world, the agency of the Logos in logic—be it Mosaic, Heraclitean, or Johannine—becomes ‘a dead letter.'”
– George Steiner, Grammars of Creation
(See also, from Hanukkah this year, A Geometric Merkabah and The Dreidel is Cast.)
Link Three – Spanning the Arc —
Part A — Architect Louis Sullivan on “span” (see also Kindergarten at Stonehenge)
Part B — “Span” in category theory at nLab —
Also from nLab — Completing Spans to Diamonds
“It is often interesting whether a given span in some partial ordered set can be completed into a diamond. The property of a collection of spans to consist of spans which are expandable into diamonds is very useful in the theory of rewriting systems and producing normal forms in algebra. There are classical results e.g. Newman’s diamond lemma, Širšov-Bergman’s diamond lemma (Širšov is also sometimes spelled as Shirshov), and Church-Rosser theorem (and the corresponding Church-Rosser confluence property).”
The concepts in this last paragraph may or may not have influenced the diamond theory of Rudolf Kaehr (apparently dating from 2007).
They certainly have nothing to do with the Diamond Theory of Steven H. Cullinane (dating from 1976).
For more on what the above San Francisco art curator is pleased to call “insane symmetry,” see this journal on Christmas Day.
For related philosophical lucubrations (more in the spirit of Kaehr than of Steiner), see the New York Times “The Stone” essay “Span: A Remembrance,” from December 22—
“To understand ourselves well,” [architect Louis] Sullivan writes, “we must arrive first at a simple basis: then build up from it.”
Around 300 BC, Euclid arrived at this: “A point is that which has no part. A line is breadthless length.”
See also the link from Christmas Day to remarks on Euclid and “architectonic” in Mere Geometry.
