Programming Language Theory: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
The Church-Turing thesis equates a vaguely-defined set of "computable" functions with the [http://en.wikipedia.org/wiki/Computable_function partial recursive functions]. Several systems are only as powerful as the partial recursives (''Turing-complete''): Turing machines and the λ-calculus are two. Programming languages provide further syntaxes and semantics. | |||
==Applicative/Functional Programming== | ==Applicative/Functional Programming== | ||
Expressions compose functions rather than values. Backus proposed three tiers of complexity in his Turing Award lecture: | Expressions compose functions rather than values. Backus proposed three tiers of complexity in his Turing Award lecture: | ||