# Lambda Calculus

#1

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]
#2

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.

http://www.secnetix.de/olli/Python/lambda_functions.hawk

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

#3

link is to a German website

Wow ive never heard of this stuff :0

#4

XD

#5

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

(I love computational linguistics!! )

#6

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

#7

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

#8

Hmm I see you are thinking of where else to put this (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

#9

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

#10

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.

#11

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!

#12

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?

#13

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.

#14

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!

#16

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.