Turing’s Lambda Notation

I’m still working through Turing’s paper on Computability and the Turing Machine.  I am at the end and reading the appendix on Alonzo Church’s equivalent approach using Lambda Calculus.   His work is so familiar to most programmers since we use the concepts in C, C++, Java, and C#.   I decided to use C# Lambda syntax to get familiar before reading through the rest of the paper.


I started simply and considered how I could make the following expression be represented by M.

Math.Pow(x, 2.0) + 5 * x + 7

Most commonly we see it in this form when programming.

static double F(double x)

return Math.Pow(x, 2.0) + 5 * x + 7;


So convert it to a lambda expression.

OneV firstExp = x => Math.Pow(x, 2.0) + 5 * x + 7;

where OneV is defined as (not suprisingly)

delegate double OneV(double x);

In C# the two variable syntax could be something like this:

TwoV Exp = (x, y) => Math.Pow(y, 2.0) + 5 * y + 18 * x + 2 * x * y + 7;

So thats how I got my head around the very basic syntax.

Leave a Reply

Your email address will not be published. Required fields are marked *