General Observations
Given the standard semantics, the simply typed lambda calculus is strongly normalizing: that is, well-typed terms always reduce to a value, i.e., a abstraction. This is because recursion is not allowed by the typing rules: it is impossible to find types for fixed-point combinators and the looping term . Recursion can be added to the language by either having a special operator of type or adding general recursive types, though both eliminate strong normalization.
Since it is strongly normalizing, it is decidable whether or not a simply typed lambda calculus program halts: it does! We can therefore conclude that the language is not Turing complete.
Read more about this topic: Simply Typed Lambda Calculus
Famous quotes containing the words general and/or observations:
“All the critics who could not make their reputations by discovering you are hoping to make them by predicting hopefully your approaching impotence, failure and general drying up of natural juices. Not a one will wish you luck or hope that you will keep on writing unless you have political affiliations in which case these will rally around and speak of you and Homer, Balzac, Zola and Link Steffens.”
—Ernest Hemingway (1899–1961)
“All observations point to the fact that the intellectual woman is masculinized; in her, warm, intuitive knowledge has yielded to cold unproductive thinking.”
—Helene Deutsch (1884–1982)