Lambda the Ultimate

Mathematics is full of imperative algorithms, including Egyptian multiplication, which was written down in the Rhind Papyrus by mathematicians over three and a half thousand years ago. Euclid's algorithm for the greatest common divisor etc. These are imperative algorithms, yet form the very core of mathematics as expressed in Euclid's Elements.

Take functions, for example, and let's take a look at the definition of factorial:

f(n) = n * f(n - 1) if n > 0
f(n) = 1 if n == 0

With addition of "if", mathematics turns into real little functional language, right? So you can finally program whatever you can with functional languages.

That really is a fundamental example, isn't it?

If I remember correctly, they are teaching it in high school. We also learned a bit of mathematical logic, so "if" can be replaced with -> operator.

But, I think, what is really happening is that classical math leaves a lot of unsaid common sense conclusions that float up when you try to completely formalize them with programming languages. I think it is that magical glue (theory about theories) from my above post that is needed to connect all the booleans, algebra, differential calculus, set operations and gods know what else that comes with classical math. I'm talking about that bit of common sense that we use naturally and take for granted, without even thinking about it.

Seemingly, the flexibility of mathematics in contrast to programming comes from the fact that mathematical proof is a conversation between human beings, whereas programming is usually an attempt to engage in a "conversation" with a computer. Computers don't think, and so the programmer typically descends to the computer's level. I've noted before that abstraction tends to be easy to do in mathematics but difficult in programming; abstraction is really a human conceptual thing, and trying to explain it to a computer is an exercise in frustration. I suspect the difference between human conversation and human-computer interaction is also responsible for the longevity of Lisp: Lisp minimizes the conversation with the computer. There's much emphasis nowadays on complex mathematical support infrastructure for languages — type systems, especially — which reduces flexibility because it's all "conversation" with the computer; but most Lisps, exactly because they lack this rigid mathematical support infrastructure, are potentially more like mathematics.

I would say most of the problems with maths are caused by the implicitness and informality of human conversation.

I would say most of the problems with maths are caused by the implicitness and informality of human conversation.

I wouldn't so much disagree with the statement itself as object to [well, okay, be wary of :-) ] the apparent emphasis. Try this as a complement: the strengths of mathematics are caused by the flexibility and adaptivity of human thought. Here's another related proposition: the problems with type systems are caused by their explicitness and formality.

For a long time now we've had a strong economic motive to play up how "smart" our technology is. Also, for the past century and more we've been motivated to play up how "smart" evolution is, because we've been trying to get across to people why evolution is powerful enough to explain things traditionally explained by religion. We've had no comparably strong motive to figure out what makes us special, and when we did try to investigate it we've tended to focus on our ability to do particular tasks over and over (easy to test), which I suspect is entirely the wrong place to look for our essential strengths. The result of all this is that we've ended up denigrating ourselves, convincing ourselves that there really isn't anything special about us. Except it's not true. We got here because we're good at things that are prohibitively difficult to do by other means. Now we're on the brink (or, the cusp if you're an optimist) of giving up control of our civilization to things that aren't human; and if we do that while we're busy not noticing what we can do that these other things can't do, the new management won't be up to the task. That could just be the explanation for the Fermi paradox; civilizations get just so far, then forget to value sapience and effectively self-destruct.

[note interpolated]

There are 2 kinds of people in the world: Those who prefer slower more probably really actually provenly correct answers vs. Those who prefer more of everything even if it is potentially wrong since it wasn't as nailed down as it could have been.

I doubt that. It seems a bit like saying there are two kinds of people, those who have five fingers on their right hand and those who have six toes on their left foot. Though of statements of this form, I rather like There are two kinds of people in the world, those who divide people into two kinds and those who don't.

any "there are n kinds of people in the world" statements are i assumed universally seen as never really serious. apologies for not putting in a smiley disclaimer originally :-)

Humor is amazingly difficult to convey in text. Even if one knows there's something meant to be humorous, it can be hard to know which aspect of things is meant that way. Open up the bandwidth to its maximum extent by actually being in the same room with someone looking at them while they talk to you, and (if you're a native speaker of the language) you can pick right up on nuances that you'd be hard put to even enumerate afterwards.

More practically, I suggest there are two goals here (amongst others, of course), to prove that things have been expressed correctly, and to express things at all. We don't nearly fully understand the interplay between the two, and if we want to learn about either we may have to temporarily bump up its priority relative to the other.

Yup. A lot of things in history were done by hacking them up and leaving them thus for a long time. They work, but are ugly and kinda just poor, even if sorta amazingly surprising at the same time. Then we hope somebody smart can see the right abstraction underlying it all and fix it for us. :-)

Heh. Possibly not what I had in mind; not sure, actually. I'm concerned with expressing ideas, in part perhaps I'm thinking of the Dijkstra quote about Lisp "assist[ing] a number of our most gifted fellow humans in thinking previously impossible thoughts." In what you describe, it's unclear whether or not the earlier thing involves expressing an idea, but the latter presumably does — evolution, which I see as a classic example of an immensely powerful engine that nonetheless fundamentally lacks that something special that makes us sapient, might do the first part about finding something that works, but would never find an abstraction underlying it.

I think it is entirely correct to view programming languages as mathematical representations, whether or not they are imperative. In either case, programming languages describe abstract operations in an idealized world of abstract entities, which seems sufficiently mathematical to me.

I think the best way to describe the distinction between *doing* programming and *doing* mathematics is primarily one of intent. From this point of view, you might consider programming a form of *applied* mathematics, as distinct from the pure stuff.

As with any mathematical notation, we tend to adapt the form of our notation to suit our intent, so it is not surprising that most programming languages don't look like the conventional notation for mathematics -- particularly since foremost among the requirements of programming is that the notation be executable by computer.

Also, most mathematical notation was originally formulated before computers were available to execute it. So even the most mechanically executable math notation (like formal logic and lambda calculus) was originally intended to communicate ideas between people, rather than supply a practical framework for an applied execution which didn't yet exist.

you might consider programming a form of *applied* mathematics, as distinct from the pure stuff.

Yes. I've maintained for years (and am certainly not the first) that theoretical computer science is a relatively pure branch of mathematics; as the flip side of that, it feels right to view programming as applied math.

... can Turing machine be programmed in math?

I'm not convinced math has to handle state badly. I think the math we've developed handles it badly. What does math that handles state well looks like? Good question. Probably not like anything we have atm.