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:
“I suggested to them also the great desirability of a general knowledge on the Island of the English language. They are under an English speaking government and are a part of the territory of an English speaking nation.... While I appreciated the desirability of maintaining their grasp on the Spanish language, the beauty of that language and the richness of its literature, that as a practical matter for them it was quite necessary to have a good comprehension of English.”
—Calvin Coolidge (1872–1933)
“The natural historian is not a fisherman who prays for cloudy days and good luck merely; but as fishing has been styled “a contemplative man’s recreation,” introducing him profitably to woods and water, so the fruit of the naturalist’s observations is not in new genera or species, but in new contemplations still, and science is only a more contemplative man’s recreation.”
—Henry David Thoreau (1817–1862)