![]() ![]() Note that we must now be careful to use an explicit multiplication sign where juxtaposition might be wrongly interpreted as function application. We see that function abstraction and function application are inverses. We can then apply this function to anything we like, for example z 2, and we find that (λ a.2 a+3)( z 2) simplifies to 2 z 2+3. We could, of course, have used any symbol we like in place of a. This operation is called function abstraction. Church used the greek letter lambda and a dot and showed that we could simply write λ a.2 a+3 as a name for the function. But this is all rather indirect and it would be a nuisance to have to keep making up new names and remembering what they meant. We might make up a name for it, say "DoubleAndAddThree" or just " f", and write f( a) = 2 a+3 to describe what we mean. For example we may write y := 2 x+3 to describe how to obtain y given x, but suppose we want to describe, in the abstract, what it is we are doing to x, so that we can do it to other things. The lambda calculus is based on the more abstract notion of "applying a function". These symbols can be interpreted as instructions (to move left or right or read or write symbols) but may also be interpreted as data, particularly when it comes time to read the result. The Turing machine is based on the idea of a tape of unbounded length, with a head which can move left or right along the tape reading and writing symbols. The Lambda calculus is reflected in the programming language Lisp and its relatives which are called "functional" or "applicative" languages. The Turing machine is reflected in the Von Neumann machine which describes the general form of most computing hardware today. Today, the best known of these are the Turing Machine, of the British mathematician Alan Turing (not to be confused with his touring machine, the bicycle of which he was so fond), and the Lambda Calculus, of the American logician Alonzo Church (1941). Remarkably, they were all eventually shown to be equivalent in the sense that any one could be made to behave like the others. Several such systems were invented and for the most part looked entirely unlike each other. They wanted to find the simplest possible system that could be said to compute. The "effectively" part is included to indicate that we are not concerned with the time any particular computer might take to produce the result, so long as it would get there eventually. A "computer", originally, was a person who performed arithmetic calculations. In the 1930s and 40s, around the birth of the "automatic computer", mathematicians wanted to formalise what we mean when we say some result or some function is "effectively computable", whether by machine or human. This paper provides an informal and entertaining introduction by means of an animated graphical notation. The lambda calculus, and the closely related theory of combinators, are important in the foundations of mathematics, logic and computer science. To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reductionġ16 Bowman Parade, Bardon QLD 4065, Australia ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |