Lambda Calculus



Discuss about lambda calculus.
Lambda calculus is a simple formal system for representing and applying functions that is turing complete (it can do everything that a universal turing machine can do)

For introductory information about lambda calculus, look at this short paper

The Numberphile Topic -- The Official Nerdy Math Topic! [OLD]

I'm definitely not in a high enough position in terms of math to understand calculus in general (I'm actually finishing up Geometry in school right now), but nonetheless, this is all interesting to me. I've seen the lambda symbol in miscellaneous places, but I've never really paid much attention to it.

This is all interesting to me. I'll read into it more later, but for now, I have a bus to catch. ^^;


link is to a German website

Wow ive never heard of this stuff :0




Wow I just found out that this could be applied to linguistics, I'm gonna take a look.

(I love computational linguistics!! :heart_eyes:)


Yeah I have seen lambda used as a symbol e.g. it is used for wavelength in physics with light calculations I think, but not much on those either :smiley:


I don't think this is much help to our maths category, should I switch the category of this topic?


Hmm I see you are thinking of where else to put this :thinking: (I have been putting computer science under #math because it is sort of a branch of maths and I don't know where else to put them.)

I think it sounds rather interesting even though we might not post on it immediately at the moment, but I am not sure :smiley:


Yeah, I guess it'll just hang around in the maths category until we start to use it

The more I think about it, this might be really interesting to talk about


I’m looking for an expert in lambda calculus to help me understand a question I have above the theoretical limits of functions as such. I’ll pose the question here, but I’m not sure if it’ll be intelligible.

Imagine you want to produce every possible function that takes one argument, and returns a transformation on that argument. That’s a lot of functions. An example of a function that would be in this list is the identity function: f(a)->a now it seems to me that lambda calculus, being a formal language of computation (functions), should tell us about the nature of all possible functions. For instance, many functions in our theoretical list are actually functions made up of other functions. So just as in math, where you have prime numbers which create all other numbers, it seems we also must have ‘prime’ functions which create all other possible functions. That is essentially my question: what are the prime functions? and what does the tree of all possible functions look like near the root?

If anybody has a way to answer this or knows the answer out right please let me know, thank you.


Your answer probably doesn’t lie in lambda calculus. Instead, I’d put this squarely in the branch of math called functional analysis. And it’s a really cool question. So cool that it’s inspired pretty much a whole branch of math. Sadly, it’s probably even a lot bigger than you think it is. What you’re studying, I would probably call most closely irreducible elements of algebraic function fields.

So let’s narrow a little to show the scope. A big group of "transformation’ functions (which we call functions R -> R, possibly you might want to limit it to continuous) are polynomials, which are functions of the form axn+bxn-1+… all the way down to just a constant. You can add and multiply polynomials, so we say they form a ring. Within this ring there are irreducible elements, which is what you’re talking about - polynomials that can’t be made from adding or multiplying other polynomials. “Prime polynomials”. And it turns out, even in this restricted case, there is no algorithm that can always tell you whether a polynomial is prime or not! Not “we haven’t found an algorithm yet”, or “it’s really hard”, but it’s literally an uncomputable problem. The most advanced computer in the whole universe couldn’t do it with 100% accuracy (source). So even in this limited case of polynomials, your prime function tree is uncomputable.

Now think about adding all sorts of things like exponential functions, logarithms, ratios of polynomials, etc and you get all sorts of problems. There will be infinitely many of your prime functions, and a very large branch of modern mathematics is dedicated to classifying them. But you will have to narrow it down quite a bit before the answer becomes managable, as you can see from the polynomial example.

This is my field, so if you have any questions feel free to ask!


Wow, thanks for making me aware of this. I had no idea.

I didn’t look into math because I thought “math is a specific case of information transformation, a specific case where every symbol of information represents a quantity. But information doesn’t have to be made up of symbols that represent quantities like numbers, information is just symbols and their patterns.”

So I thought it would be best to go as general as possible and not “narrow the scope” as you say, into a particular subdomain; a special case. Is my intuition wrong about that? I’ll admit it seems like my intuition about these kinds of things really doesn’t seem to match the normal intuition, but I don’t yet see why, or if that’s a bad thing.

Anyway, So when I found Lambda Calculus I realized you can reduce them - I think it’s called beta reduction or something. Every function can be reduced to it’s simplest form. I thought this was important because there are an infinite amount of functions, but if you define a function as ‘a particular expression of a more general transformation’ you have a much larger infinite. I’m a lowly coder so allow me to illustrate my point in pseudo code:

def func_a(arg):
    return arg

def func_b(arg):
    arg = arg + 1
    return arg - 1

func_b is merely a convoluted expression of the transformation in func_a (the identity function). In regular old imperative programming languages (the kind I’m familiar with) there’s no way to automatically reduce func_b to func_a but in lambda calculus, there are algorithms for doing so.

Thus I thought, “ok, first of all, you want to isolate every possible transformation on information (every possible function) in its simplified expression.” Though, now that I talk it over, I’m not actually sure that beta reduction is doing exactly what I wanted: by “simplest” I mean the fewest number of symbol changes during the transformation.

I mean if you think about it, the problem is really easy to articulate. There’s lots of ways we can transform information; there are lots of functions. We’ve only named a few of these functions, and those names are arbitrary and human-readable (such as ‘y-combinator’ or ‘the identity function’). We should instead, name every function. But in order to do that we have to know the tree, the shape, the graph of how they’re related to each other. Which means we need to know the transformations on data that can be combined to make all other transformations on data. That’s what inspired my question about the prime functions. However, we can go a little further. Every function actually does have a name in the form of byte code - 0’s and 1’s that are fed to a modern day computing architecture. Every function is a different combination of 0’s and 1’s. Every function has a name, furthermore, similar functions share somewhat similar names. That’s cool, but it’s arbitrary in that instead of english; human language, it’s byte code; machine language (the name, the representation of that function, depends on the context of our modern day hardware and software and arbitrary informational structures such as ascii). What we really want is a non-arbitrary way to name every possible transformation on data. Enter lambda calculus. It seemed that this might provide a non-arbitrary mapping of all possible functions, a graph of their relationships with each other; and by so doing; provide the perfect name for every function; the name of it’s relative location in the graph.

Anyway, regardless of my intuition regarding the usefulness of lambda calculus for this endeavor, you suggest taking a mathematical approach with functional analysis. But my question about that is: is functional analysis the most general case to answer this question, or is it, as I suspect, a specific case? In other words, how do I write a mathematical function that transforms symbols into other symbols not tied to quantities (such as transforming language and textual data)? If the answer is, “well you really can’t do that,” then shouldn’t I be looking into a more generalized domain of like information theory or something? (I mean “information theory” literally, I’m not using the term as it has become to be known as just a pseudonym for “entropy theory”).

I know that math is the most abstract of all disciplines so for that reason I think, perhaps math is exactly what I’m looking for, but I really don’t know. Perhaps the context of symbols that represent quantities is important, and general because symbols always represent relativities - that is they only mean something relative to what other symbols mean.

Anyway, I know this is more philosophical, but I feel like I have to get my mind right on this point before I can jump headlong into trying to find the answer via functional analysis; a branch of mathematics. What am I missing?


So, this is a really good question. And I think it’s something that a lot of people miss about mathematics - I didn’t get it until my first abstract algebra course. Math is as abstract as you want it to be. Math isn’t just the study of numbers, but really the study of patterns. So it is perfectly all right to say “I have a function that takes the set {a,b,c,d} to the set {e,f,g,h}”. In fact, even if no one had done it before, it would be alright - because math can really do whatever you want it to. If you’re studying categories of things, and patterns, you’re studying math.

Really, lambda calculus is quite literally a branch of math. It’s a higher-order version of what’s called “first-order logic” in math, which is very hard to work with on it’s own. Lambda calc is to first-order logic as Java is to assembly code.

But in the end, now that you’ve clarified your point, I’m not sure standard mathematics will get you where you want to go. This is because we avoid the issue completely in mathematics - unlike in programming, where f(x)=x-1+1 and g(x)=x are different functions, in math a function is defined only by it’s pre-image and image (domain and range), and the connections between them. Writing f(x)=x+1 is just a convenient way for mathematicians to notate “{…,-2,-1,0,1,2,…}->{…,-1,0,1,2,3,…}”. So f(x)=x+1 and g(x)=x+2-1 are completely and utterly the same function. They are undifferentiable (not in a calculus way, in a literal way).

I think before you go any farther you gotta make what you want more precise - for example, is f(x)=x^2-1 a more “basic” version of f(x)=(x-1)(x+1)? Or vise versa? Do you define a function as being "composed of other functions through addition, multiplication, composition, or what? For example, is f(x)=2(x-1) made up of the functions f(x)=2x and g(x)=x-1 being composed and therefore not basic?
But I’d direct you towards expression simplification algorithms, perhaps some study of which could lead you to a more precise definition of what you want.

I’m sorry I can’t say more right now, I’m in court on my phone for a mock trial competition.


You’ve helped me immensely. Thank you, I’ll think and study more in order to more accurately define exactly what I’m looking for. If I have questions about functional analysis or if I feel I reach a break through, I’ll message you here. Thanks!


As an exact answer to your question, which I don’t think was answered, there are sets of “prime functions” that can be used to build all other (computable) functions.

The most well known set is of the SKI combinators (though the I combinator is redundant as it can be represented in terms of S and K.)
There are other sets as well, of which one that is interesting is the set which contains the iota combinator, as the iota combinator by itself can be used to build all other functions.