ICM2010 — Spielman, Csornyei, Lurie

I’ll begin this with a question: why is it that theoretical computer scientists are, on average, far better than other mathematicians at giving general-audience talks? Irit Dinur’s plenary lecture at the ICM was, as I have already said, excellent, but that kind of excellence seems to be the norm for theoretical computer scientists: I basically know, when I go to the TCS plenary lecture at an ICM, that I’m in for a treat. (But that is not the whole story at all. For example, I also know that if I’m at an additive combinatorics conference at which Ryan O’Donnell is speaking, then again I am guaranteed an extremely interesting, entertaining and comprehensible talk.)

Even by the exalted standards of theoretical computer scientists, Spielman’s talk was masterful. (If you’ve been reading all these posts, you may remember that I predicted this after hearing him answer a question at the post-opening-ceremony press conference. Well, my prediction was not just correct but hypercorrect.) He started by thanking all sorts of people who had inspired him to become a theoretical computer scientist, and even this he made interesting and amusing — for instance, he showed us a picture of one person, a high-school teacher or something, and ended a brief discussion of that person by saying, “And he was the one who made me want to become a mathematician.” And then after the next person he said, “And he was the one who made me want to become a computer scientist.” And at the end of the talk he somehow (in a way that I’ve now forgotten) brought the whole thing full circle and reminded us of these initial remarks about his early intellectual life.

During the talk, he marched about the stage, always talking to us, the audience, and never to his slides — it was as though he knew from memory what was in them, though there was something on the stage (other than the lectern) that may have been a display for the benefit of the speakers. I never quite got round to checking.

In between the initial remarks and the clever return to them, he told us about one of his main interests: quick ways of solving systems of linear equations. He began by telling us what the holy grail was: to find an algorithm that can solve the equation Ax=b, where A is an n\times m matrix and x and b are appropriate vectors, in a time that is linear in the number of non-zero entries of A. Such an algorithm would be of major theoretical and practical interest, and it seems from what Spielman was saying that it might even exist.

But if we don’t see how to devise it, what else can be done? One natural line of enquiry is to look at important classes of systems of linear equations and try to find fast algorithms for those. For instance, if you are trying to solve a PDE by discretizing it, you end up with a large number of equations, but they have some special properties: each equation involves only a few variables, and those few variables will typically correspond to points in some nice space that are very close to each other. For example, one big and interesting class of equations is Laplace’s equation on the graph of a triangulation of a surface. (That is, one wants the combinatorial Laplacian at each point in the graph to be zero.)

One thing that is always nice to get out of a mathematics talk is a bit of philosophy, or an insight into other people’s philosophies. Spielman at one point said something like, “I find I don’t understand a graph unless it is a …” and although I remember liking this statement very much, I can’t now remember it. The basic idea was that the graph should have been produced in some concrete way, but what he said was more specific than that.

I find that I have written almost nothing about the talk — I was just sitting back and enjoying it. So I’ll end by saying that one of Spielman’s main themes was that in order to solve these special cases of the problem about solving systems of linear equations, it had been necessary to draw on a large amount of existing work that had been done in connection with quite different questions. He demonstrated this convincingly, thereby justifying Gil Kalai’s remark that Spielman’s work was a wonderful marriage of theory and applicability.

That was the regular 1.45-2.45 slot. I then had to decide which talks to go to in the parallel sessions. I decided on two prodigies: Marianna Csörnyei and Jacob Lurie. Marianna I have known quite well for many years, and she works in areas that I can be expected to understand reasonably well (which is not quite the same as saying that I do understand them reasonably well, but in fact I do usually follow quite a bit of her talks). Jacob Lurie is the opposite: I had never met him, or even seen him, and had absolutely no chance of understanding anything he would say, so I was going for the sole purpose of gawping.

Why do I describe them both as prodigies? Well, in Marianna’s case there are some extraordinary anecdotes about how David Preiss, then at University College London and now at Warwick, brought her over to England at some extremely young age such as 18 (I can’t remember exactly) and set her unsolved problems with deadlines of, say, 48 hours. In case you want me to confirm what I’ve just written, I do indeed mean that he would say things like, “This is an interesting unsolved problem: you have until the day after tomorrow to tell me the answer.” And the even more extraordinary thing was that Marianna would indeed come back two days later with the answer. And I’m not talking about something that happened just once: it was a regular occurrence. The problems were things like finding sets of real numbers with extraordinary properties, and to solve them Marianna would produce incredibly delicate inductive constructions of sequences of sets that would tend to a limit with the desired properties. I think there are similar stories about Jacob Lurie — I heard about professional mathematicians consulting him when he was about 16 and getting the answers they sought the next day. And the amazing thing was that it wasn’t amazing — they consulted him because they knew he would be able to do it. [Edit: I've recently been told, by someone who knows what they are talking about, that if there are such stories about Jacob Lurie then they are groundless. So suffice it to say that he is a mathematician whose talent was recognised early.]

While I’m on this subject, let me counteract it with another story, that of James McKernan. He was an undergraduate at Trinity College, Cambridge in the same year that I was. I did not know him all that well (there were 40 of us), but I remember him as someone who was … I don’t know quite the right way of putting it because the truth is that I don’t remember all that well how good he was at mathematics at this stage. But the fact that I don’t remember puts upper and lower bounds on his performance: he wasn’t one of the best in the year and he wasn’t one of the worst in the year. I think the result of that was that he did not get a PhD place in Cambridge, but it’s possible that he just didn’t want to do a PhD here, and so he disappeared out of my life — I think he did his PhD at Brown — to reappear over twenty years later as the coauthor with Christopher Hacon of some astonishing papers that completed Mori’s minimal model programme. Now I don’t know what that programme is, but I do have some conception of how important it is, and have seen how excited algebraic geometers are about these developments.

Both Hacon and McKernan were invited speakers at the ICM. I was strongly tempted to go to McKernan’s talk, but, agonizingly, it clashed with Assaf Naor’s and I went for the latter. It occurs to me that, given that I tended to bump into the people I knew about two or three times a day, I may have accidentally cut McKernan dead a few times (I stupidly didn’t remind myself what he looked like until well after I had left Hyderabad). James, if I did, and if by any chance you read this, then please know that it was the opposite of what I planned. What I would have liked to do is tell him how pleased I was at how well he has done. I don’t know whether it is right to describe him as a late developer, but the evidence I have suggests that that is a reasonable description. I hope it is, because I very much like stories of late developers: I think it is important to show the world that if you are not a Marianna Csörnyei or a Jacob Lurie, then you still have a chance of proving major theorems.

Marianna’s talk was packed, partly because the room was much too small for an invited lecture at an ICM, so I ended up standing. Given my state of tiredness and the temperature in the room, this was both a good thing (it stopped me going to sleep) and a bad thing (it was pretty tiring). Marianna spoke quietly, but loudly enough to be audible in that room, at least if there wasn’t any background noise. I’ve forgotten what she said about her own work, except that it sounded amazing in the way that it always does, but let me mention a pair of results of David Preiss that she mentioned as part of her introduction. (Added later: if you want to know about more than this, here is her ICM proceedings article.)

A Lipschitz function from \mathbb{R}^n to \mathbb{R}^m is differentiable almost everywhere. But some very subtle questions arise if you ask about the nature of the exceptional set. Preiss showed that there is a set X of measure zero in \mathbb{R}^2 such that every Lipschitz function f:\mathbb{R}^2\to\mathbb{R} is differentiable at at least one point in X. By contrast, given any set Y of measure zero in \mathbb{R}^2, there exists a Lipschitz function g:\mathbb{R}^2\to\mathbb{R}^2 that is not differentiable at any point of Y. Marianna (I’m calling her that rather than Csörnyei not out of sexism but because I know her well enough that it would feel weird to say Csörnyei — I’ll do the same for Assaf Naor and Benny Sudakov) explained that a feature of the first result that makes it pretty deep is that the proof does not tell you in any sense that almost all points of X are points of differentiability of f — it just tells you what it says on the tin, that there exists such a point.

After Marianna’s talk I allowed myself a break (as I had in the morning when I skipped Carlos Kenig’s plenary lecture — today, as on the previous day, I was sufficiently worried about overdoing it that I missed some talks that I would ordinarily have liked to go to) of just over an hour until Jacob Lurie’s talk. I thought that there were likely to be many people besides me who would be there for entirely extra-algebro-topological reasons, so I decided to turn up ten minutes early. The room was already very full, but I tried a tactic that sometimes works — to march to the front, spot one seat right in the middle of the fourth row that nobody has quite been able to face getting to, and to face getting to it. OK you have to climb over six sets of knees, but it seems that people don’t hold permanent grudges against you for this (except perhaps if you arrive late for a film and clamber over someone, blocking their view at a crucial moment, but then you’ll probably never see them again).

As I’ve already made clear, Lurie is a certified genius. I mean “certified” in the sense of “universally acknowledged” but there was just a hint of an alternative interpretation in the way that he moved his head, which seemed somehow more loosely attached to the rest of him than most people’s heads are. We sat waiting for quite a long time, partly because I had arrived early (which I was glad of, because there were plenty of people standing for this talk as well) and partly because Richard Thomas, who was chairing the session, was trying to persuade the conference organizers to remove the partition between the room we were in and the room next door, which was empty. Unfortunately, he failed to persuade them, although in another way it wasn’t unfortunate: I think it does something good for the atmosphere of a talk if the room is packed.

What can I say about the talk itself? Well, early on he put up a slide that had the following names on it: Deligne, Drinfeld, Feigin, Hinich, Kontsevitch, Milgram, Schlessinger, Soibelmann, Stasheff. I haven’t heard of all of those, but I’ve definitely heard of some of them and was duly intimidated. And Deligne-Mumford stacks made an appearance too (you may remember those from Ngo’s work). There were also some things called Artin stacks.

By the end of the talk, Lurie had leapt into first place for interesting or amusing quotations with three. (The next day David Aldous managed two, but he had an hour.) The first one was one of those bits of folk wisdom that I mentioned earlier: having pointed out that it was difficult to define (or discuss, or do something to) something or other using equations, he said, “If you can’t use equations, then what you want to do is use words.” In other words, you wanted to be more conceptual about what you were doing (where “you” means “Jacob Lurie”).

I’ve written, “Lots of mathematical structures — abstract.” What I meant was that to someone like me, who still has the temerity to think about mathematical objects rather than sticking to sets of sets of sets of objects (all very nicely structured of course), the experience was a sort of bombardment. I don’t really understand why I should be happy that we can define a canonical sequence of graded Artin stacks or whatever it might be (whatever it was, it wasn’t that, but it sort of sounded like that). But I wasn’t there to understand — just to drink in the experience while Lurie told us, “And then one can do A, and then B, and then C,” and the algebraic structures he mentioned became more and more sophisticated (or did they? I can’t claim to be sure of this).

I think Lurie is slightly sensitive to the criticism that his work is too abstract (not that I’m making that criticism myself — I’m not really in a position to judge how abstract it is). This sensitivity led to the second of his great quotes, which came about two thirds of the way through, when he said, “I don’t want you to think all this is theory for the sake of it, or rather for the sake of itself. It’s theory for the sake of other theory.” This got a good laugh, as you might imagine. He said that he would demonstrate that by giving us an example, which to my inexperienced eyes seemed to be yet another building of algebraic structures, but I suppose to be fair to him he did say at one point (or at least I wrote), “M is the moduli stack BGL(n),” where I think M had been an abstract something or other about which something in one of his abstract results had been stated.

There was one bit that intrigued me, where he talked about things called E_n algebras (which I would completely have forgotten about had I not written anything down). If I remember correctly, an E_0 algebra is associative, and as n\to\infty the E_n algebras become more and more commutative in some sense. Additive combinatorialists will see why I found this idea appealing, though I think the appeal might vanish on closer investigation (or rather the reasons for it might — I wouldn’t rule out their being replaced by different and better reasons).

The third quotable sentence came after 35 minutes or so. He said, “I expected that I would be going overtime, but I think I haven’t.” And that was the end of the talk, apart from some questions that sounded frighteningly intelligent to me. I found myself wondering about a nightmarish scenario in which my brain suddenly inhabited Lurie’s body. Would I be able to answer the questions in a way that would seem genuine to most of the audience? Each time Lurie answered one, I realized that the answer was definitely no — there were little touches of a kind that I just wouldn’t have thought of, that made it clear that some kind of communication really was going on.

A short time afterwards I found myself chatting with Richard Thomas, who clearly had a very great respect for Lurie. I asked him two questions that I can now remember. The first was, roughly speaking, whether it was true that Lurie is revolutionizing mathematics. The answer is yes, apparently. Richard told me that Lurie has a huge programme and is slowly working through it, writing hundreds and hundreds of pages. (I think I had heard this from other sources too.) The second question was whether all this theory was leading to solutions of open problems that could not be solved without it. The answer to this is also yes, apparently, though it seems that the process of using the theory for applications is in its infancy. In other words, we can expect to hear a great deal more about Lurie over the next few years. He also said that Lurie has made several claims about what he will eventually be able to do, and already has an impressive record of backing those claims up with results. It’s just that there’s a lot more work to do. [Added later: if you want to know more, there is now a discussion at Mathoverflow about what exactly it is that Lurie has done and is doing, which may help a bit.]

I’ll end this post with perhaps my worst photo — unfortunately, the camera decided to focus on the head of the person just in front of me rather than on Lurie. But at least you get some idea of what he looks like.
Jacob Lurie just before his talk

About these ads

19 Responses to “ICM2010 — Spielman, Csornyei, Lurie”

  1. Robert Says:

    Many (most?) computer science department are housed in engineering “colleges”. My intuition tells me this may have something to do with the presentation skills.

    But then again it may not.

  2. Todd Trimble Says:

    I’ve heard that academic computer scientists put a lot more stock (than do academic mathematicians) in the quality of conference talks, for purposes of assessing candidates for appointments, tenure, grants, etc., whereas academic mathematicians emphasize journal publications more. If that information is basically correct, then delivering good talks is simply expected of competent academic computer scientists.

  3. Xamuel Says:

    Simple answer– they’re better at passing Turing Tests ;)

  4. Greg Martin Says:

    Exactly Todd. And inversely, there is virtually no serious pressure within the mathematical community for people to give good talks. It’s pure economics: without incentives, only occasional people (whose personal utility functions are increased by giving good talks) will invest the effort into trying to give good talks.

  5. observer Says:

    On the other hand, mathematicians seem to be improving in promoting the work of their young in mass media, e.g., http://www.newscientist.com/article/dn18931-proof-at-last-for-boltzmanns-140yearold-gas-equation.html – congratulations for http://arxiv.org/abs/0912.0888

  6. John Sidles Says:

    Tim Gowers’ question has a natural answer if we broaden its context a little bit.

    Medical grand rounds conferences are (in my experience) always tremendously interesting and clear; even more interesting and clear are morbidity-and-mortality conferences; for the simple reason that neither the speaker nor the audience patients to come to harm.

    Thus medical talks are targeted—by a nearly inviolable tradition that began with William Osler—to that 1/3 of the audience who are *most* clueless. As for the remaining 2/3 of the audience, experience swiftly teaches them that they surely will encounter cases that challenge them, no matter how great their skills.

    In consequence, at medical talks the whole audience listens with rapt attention.

    Engineering talks generally are reasonably interesting and clear, because they are targeted to that 1/3 of the audience whose skills are moderate, and who want to improve those skills. Not to mention, the bottom 1/3 of an engineering audience wants to catch up, and the top 1/3 of the audience can reasonably hope to learn a few new tricks.

    Thus at engineering talks (broadly speaking) the whole audience listens with moderate levels of attention.

    Mathematical talks often are targeted to the top 1/3 of the audience who already grasp what’s going on. The middle 1/3 of the audience has to scramble to keep up … as for the bottom 1/3 of the audience .. well … they can always think about their own mathematical speciality.

    Thus a pretty fair fraction of any given mathematical audience (again, broadly speaking) tends to tune-out of an advanced-level talk.

    Arguably, all of this is as it should be. Because if medical talks were socially constructed like mathematical talks … that is, pitched only at the most knowledgeable members of the audience … then it would become unacceptably risky ever to go to a hospital, because there would be too many marginally competent physicians.

    Conversely, if mathematical talks were socially constructed like medical talks … then the most advanced mathematics would never be transmitted at all … as a result, we would perhaps have more ordinary mathematicians … and perhaps fewer great ones.

    Isn’t it true, that the mathematical community as a whole, would regard this as a bad trade-off? On the grounds that great mathematicians are more important to mathematics, than great physicians are to medicine?

    Perhaps not too much change in this situation can be expected … so can we conclude that the present traditions are nearly optimal?

    That would be my opinion … except that these traditions and trade-offs (IMHO) contribute greatly to the gender imbalance that is so markedly characteristic of mathematics, and which is so nearly absent (relatively speaking) in medicine.

    That is why (IMHO) the question Tim asked is a deep one.

    • gowers Says:

      I don’t think the situation in mathematics is as simple as you suggest, because there are different kinds of talks. It’s perfectly possible to have specialist seminars to keep the experts happy and much more general talks (which a plenary lecture at an ICM is supposed to be) aimed at communicating the ideas more broadly and in less detail. I don’t think there has to be a trade-off, and if a TCS lecture at an ICM is much clearer than a lecture in some other branch of mathematics, then I don’t think that situation is nearly optimal.

    • John Sidles Says:

      Tim, you are 100% right that “the situation in mathematics” is not as simple as I said it was. Because if it were, then perhaps we would have a broad, reliable understanding of the origins of professional gender imbalances in STEM enterprises … which at present we don’t have.

      In which case, perhaps efforts to mitigate those professional gender imbalances in the last four decades would have been effective … which they have been in medicine, but by-and-large not in science, mathematics, and engineering.

      Unless the University of Cambridge is surprisingly different from the University of Washington, the clinical conferences at Cambridge’s Addenbrooke’s Hospital will in general have no mathematicians attending, and correspondingly, there will be few or no physicians attending Cambridge’s mathematical conferences.

      This is a pity, as this kind of cross-disciplinary experience is immensely illuminating! A well-written overview of the goals of a clinical conference is the British Medical Schools Council’s two-page Role of the Doctor Consensus Statement.

      You will note in this consensus statement that ‘doctor’ explicitly encompasses all qualified doctors, including those in training. If there exists a similar consensus statement for mathematicians (British or otherwise), then I would be very interested to read it!

      The proof of the educational pudding, though, is in the lecturing. Thus, if you were to arrange (via a colleague) to attend an Addenbrooke’s clinical conference—these conferences typically commonly are held in crowded rooms at shockingly early hours of the morning, but occasionally are held at jolly evening dinners; the former are more instructive—then I think you would have a very enjoyable and memorable time of it.

      One thing you will come to appreciate is that there are some exceedingly important respects in which mathematical educational methods lead all other STEM disciplines, including medicine. Here in particular I have in mind ideals of naturality, which IMHO are defined better and taught more effectively in mathematics, than in any other discipline.

      It is conceivable, therefore, that you might encounter physicians who would take a keen interest in mathematical methods of education.

    • Jonathan Vos Post Says:

      Synchronicity! I’d just written in a chapter of my Quantum Computing novel (which quotes heavily but strangely from Scott Aaronson and John Baez):

      “Sir William Ostler once said ‘the transition from layman to physician
      is the most awesome transition in the universe.’”
      [Analog, July/Aug 2010, p.56]

      If he said so, then the bootstrapping of my brain by the
      neuromagnetometry/IR laser/entanglement/Quantum Advice download from the quantum computing ET was like transitioning me from a layman to a physician to the cosmos.

      I had a bedside manner. I had a way of diagnosing anomalies in
      physical systems, and a way of making prognosis on a partially
      completed proof of a hitherto unknown truth, an unimagined truth, a
      previously unimaginable truth.

      Remember when Neo, played by Keanu Reeves in “The Matrix”, said:

      “I know Kung Fu!”and then proved it, in simulated fight with Morpheus
      played by Laurence Fishburne, asks:

      “Do you think that’s air you’re breathing?”

      Remember how it took more training before he could punch faster than
      his muscles? Dodge bullets? Leap from rooftop to rooftop of
      skyscrapers in Sydney, Australia? I recognized that
      part of Sydney from a flyover by a drone on way to Tidbinbilla.

      I know Konigsberg Bridges Fu!

      I know Rubidium Bose-Einstein Condensate Fu!

      I know Godel Incompleteness Bridges Fu!

      I know Quantum Oracle Fu!

      I know Stardrive Fu!

  7. Hany M. El-Hosseiny Says:

    In the photo: there not only one head, but two (other than Lurie).

  8. Matthew Emerton Says:

    A good mental model for a Deligne–Mumford stack is the quotient of a manifold by the action of a finite group, which may however act non-freely. Thus some points will have finite isotropy groups, which one remembers as part of the structure.

    A good mental model for an Artin stack is then the quotient of a manifold by a group which may no longer be finite, e.g. a Lie group. Thus the isotropy groups of points may be infinite, and may have non-trivial Lie group structure.

  9. s Says:

    A far-fetched speculation: is it possible that the answer to “why do theoretical computer scientists give better talks” may have a bit to do with the nature of computer science itself? Something like: the reason these good speakers got into TCS in the first place is that they are attracted to the kinds of things that make for better talks: concrete examples, easily-stated problems, etc.? :-)

  10. Melissa Tacy Says:

    Mathematicians in general are too much like the Emperor with no clothes. That is we create talks that are only to be understood by the “brilliant of mind”. Consequently we don’t call poor talks for what they are, a complete failure to communicate that mathematician’s work. If we want mathematicians to improve not only will we need to tie career progression with good speaking, we should also stop making excuses for ourselves.

  11. D. Eppstein Says:

    As a theoretical computer scientist I’m somewhat envious of the smooth blackboard talks I’ve seen many mathematicians give. It’s a different skill than giving talks with pre-prepared slides. I suspect that more practice with one or the other type of talk may play a bigger role in the differences you’re seeing than any substantive difference in the disciplines.

  12. Peter Says:

    Allow me to add a direct link for those who’d like to watch the talk (it’s availabe through the ICM homepage).

    [video src="http://player.bitgravity.com/debug/embedcode.php?ap=true&video=http%3A//bitcast-a.bitgravity.com/highbrow/livearchive40009/21aug-13.45to14.45.flv" /]

    Thank you very much for this journal from Hyderabad!

  13. Bhupinder Singh Anand Says:

    “… why is it that theoretical computer scientists are, on average, far better than other mathematicians at giving general-audience talks?”

    I suspect that the gap will only widen before it closes – as I believe it must.

    Reason why I believe the gap must widen
    ==========================
    As I see it, the focus of theoretical computer science (post-Turing) seems to be on discovering how humans can compute better; whilst the focus of mainstream mathematics (post-Goedel) seems to be on deciding how humans ought to reason better.

    Thus, I would suspect that a post-Turing theoretical computer scientist would probably hold sub-liminally (based instinctively on experience with the reliability of the communication between mechanical artefacts) that SETI should be safe because nature is not malicious; and Turing’s analysis of computable numbers suggests that there must be a categorical language of effective, and unambiguous, communication between different forms of intelligence that would allow them to always co-operate despite having to compete for common resources.

    However, I would suspect that a post-Goedelian mathematician would probably hold sub-liminally (based on an unquestioning faith in the validity of Goedel’s interpretation of his own formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions) that SETI is dangerous because we should not presume that nature cannot be malicious; since Goedel’s conclusion of the existence of a formally undecidable arithmetical proposition suggests that there is no categorical language of effective, and unambiguous, communication between different species of intelligence that would allow them to always co-operate whilst competing for common resources.

    See http://alixcomsi.com/25_Aristotlean_particularisation_Presentation_Update.pdf

    If so, such sub-liminal beliefs should lead over time to increasingly differing motivations in deciding upon the amount of effort that one should put into developing results in a language (such as first order PA) that, prima facie, appears ideally suited for communicating effectively and unambiguosly (the ‘Can you understand my meaning?’ syndrome) by an objective yardstick (a finitary interpretation of PA in terms of Turing computability); as compared to the effort one shoulld put into developing results in a language such as ZF that, prima facie, appears ideally suited only for expressing oneself effectively and unambiguosly (the ‘I can understand my meaning’ syndrome) by an essentially subjective yardstick (belief that the axiom of infinity is ‘self-evidently true’, and so ZF must be consistent).

    Reason why I believe the gap must close
    ==========================
    Basing one’s efforts on the way things are will always be more productive than basing them on the way they ought to be.

    To illustrate.

    Apart from an almost ‘religious’ faith in the consistency of ZF, the faith that mainstream mathematics has in the validity of Goedel’s conclusions is founded essentially on the almost ‘religious’ belief that Aristotle’s particularisation ought to always hold over the natural numbers.

    By this I mean the belief that, if I can show that it is not the case that a number-theoretic relation R(x) always holds over the natural numbers, then I may conclude that not-R(n) must hold for some natural number.

    This belief is reflected in the introductory pages of any logic text (or paper), where it is almost ‘informally’ stated as almost ‘self-evident’ that the formula [(Ex)R(x)] of any formal first order logic / language (the mainstays of mathematics) may always be validly interpreted as ‘There exists some x such that R(x) holds’ over the domain of the interpretation.

    However, I have yet to come across any literature that highlights the consequences (say, for Rosser’s incompleteness argument) of the fact that Aristotle’s particularisation holds under any sound interpretation of first-order Peano Arithmetic over the natural numbers if, and only if, PA is omega-consistent.

    Now, Turing’s analysis of the Halting problem does not allow a theoretical computer scientist (as distinct from theoretical computer science – which uncritically accepts the mainstream mathematics of the day as the court of last appeal) to appeal to Aristotle’s particularisation when interpreting the discipline’s results to engineers for practical application (which, of course, is the very raison d’etre for most presentations in theoretical computer science).

    Reason: A machine intelligence cannot conclude that if it is not the case that a number-theoretic relation R(x) always holds (is algorithmically computable as always ‘true’) over the natural numbers, then it may conclude that not-R(n) must hold (be computable as ‘true’) for some natural number

    The distinction is seen even more vividly if we introduce adequate definitions that allow us to interpret the satisfiability of the atomic formulas of PA over the natural numbers:

    (a) in terms of Turing-computability (as commonly understood by theoretical computer scientists);

    (b) in terms of PA-provability (as commonly understood by mathematicians).

    Now, it is not very difficult to construct such a set of definitions. The challenge is in recognising, first, that the ‘standard’ interpretation of PA – which appeals to Aristotle’s particularisation – is then a consequence of (b) and is inconsistent; and, second, that (a) yields a sound interpretation of PA which seems to imply that PA is categorical.

    See http://alixcomsi.com/27_Resolving_PvNP_Update.pdf

  14. Why Read the Heroes? « Pink Iguana Says:

    [...] – Rouse Ball chair, Cambridge U, Fields Medal 1998, see ICM 2010 or Finding Cantor’s proof that there are transcendental numbers, and he was piqued to comment Re: [...]

  15. Higher and Enriched Topos Theory – Links | Soto van Cavalera Says:

    […] http://gowers.wordpress.com/2010/08/31/icm2010-spielman-csornyei-lurie/ […]

  16. Opetuksessa pitää olla aitoja ongelmia | Lahjakkaat lapset Says:

    […] päivänä. Hän oli ratkaissut ongelman. David Preiss oli haltijoissaan. Marianna oli ratkaissut ongelman, jota yksikään matemaatikko ei tuohon mennessä ollut ratkaissut. Ongelma liittyi […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,571 other followers

%d bloggers like this: