Skip to content

David Hilbert Speaks

October 17, 2010


A focus on Hilbert’s famous speech, not on his problems

David Hilbert is the mathematician for whom Hilbert Spaces are named, as well as a huge number of other concepts and theorems. He has a type of hotel: Hilbert’s Hotel named after him too. Here is a very partial list of other things that are named for him:

  • Hilbert’s irreducibility theorem
  • Hilbert’s Nullstellensatz
  • Hilbert’s Theorem 90
  • Hilbert’s syzygy theorem

    Even better a street:

Today I wanted to look at the beginning of his famous speech on what became known as “Hilbert’s Problems.”

Many of his twenty-three problems—apparently a twenty-fourth has been found—have become famous, some like the “Tenth” are known by their number alone. The Tenth is the question, in modern terms: is there a decision procedure for deciding whether or not a polynomial equation

\displaystyle  P(x_1,\dots,x_n) = 0

has a solution over the integers? The famous answer, of course, is no—this the work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson. I recently discussed the still open question: what happens if the values of the {x_i}‘s are allowed to range over the rationals.

I think the brilliance of Hilbert in selecting problems that still are interesting, problems that helped shape mathematics for over a hundred years, has overshadowed his wonderful insights about mathematics in general. It is his general insights that I want to discuss today.

The Speech

Here is the beginning of the speech. I did quote part of it before in a discussion on another topic.

Who of us would not be glad to lift the veil behind which the future lies hidden; to cast a glance at the next advances of our science and at the secrets of its development during future centuries? What particular goals will there be toward which the leading mathematical spirits of coming generations will strive? What new methods and new facts in the wide and rich field of mathematical thought will the new centuries disclose?

History teaches the continuity of the development of science. We know that every age has its own problems, which the following age either solves or casts aside as profitless and replaces by new ones. If we would obtain an idea of the probable development of mathematical knowledge in the immediate future, we must let the unsettled questions pass before our minds and look over the problems which the science of today sets and whose solution we expect from the future. To such a review of problems the present day, lying at the meeting of the centuries, seems to me well adapted. For the close of a great epoch not only invites us to look back into the past but also directs our thoughts to the unknown future.

The deep significance of certain problems for the advance of mathematical science in general and the important role which they play in the work of the individual investigator are not to be denied. As long as a branch of science offers an abundance of problems, so long is it alive; a lack of problems foreshadows extinction or the cessation of independent development. Just as every human undertaking pursues certain objects, so also mathematical research requires its problems. It is by the solution of problems that the investigator tests the temper of his steel; he finds new methods and new outlooks, and gains a wider and freer horizon.

It is difficult and often impossible to judge the value of a problem correctly in advance; for the final award depends upon the gain which science obtains from the problem. Nevertheless we can ask whether there are general criteria which mark a good mathematical problem. An old French mathematician said: “A mathematical theory is not to be considered complete until you have made it so clear that you can explain it to the first man whom you meet on the street.” This clearness and ease of comprehension, here insisted on for a mathematical theory, I should still more demand for a mathematical problem if it is to be perfect; for what is clear and easily comprehended attracts, the complicated repels us.

Moreover a mathematical problem should be difficult in order to entice us, yet not completely inaccessible, lest it mock at our efforts. It should be to us a guide post on the mazy paths to hidden truths, and ultimately a reminder of our pleasure in the successful solution.

\displaystyle  \S

Comments

I have read this a number of times, but cannot imagine having a speaker today start this way. I think there are several important ideas in his speech that I really like.

{\bullet } What makes an area important? He points out that what makes an area of mathematics less interesting is not the decision of someone or even a group. What can “kill” an area is the lack of new and exciting questions. Areas survive and thrive exactly when they have a multitude of interesting problems. There are many parts of theory I have discussed before that are no longer central, even though they once were. I hesitate to name one lest I hurt someone’s feelings. But certainly one example must be language theory. When I was a graduate student we learned many wonderful theorems about languages. Yet today I wonder how many know these old results? I do not think they are not important, but I believe that Hilbert would say that the area has lessened its output of problems, and thus has become less central.

{\bullet } What makes a theory well understood? He discusses a goal we should have in making theories “simple”: “A mathematical theory is not to be considered complete until you have made it so clear that you can explain it to the first man whom you meet on the street.” I sometimes wonder if we can even come close to that with any of the great ideas of theory. Can we explain the P=NP question in this way? Can we explain in this way any of the great results of theory? I wonder.

{\bullet } What makes a problem great? I always liked his notion of what makes a good problem: “for what is clear and easily comprehended attracts, the complicated repels us.” Questions that are simple to state are the best. This seems obvious, but I definitely have violated many times by working on complex problems. But I think the most important problems do satisfy Hilbert’s criterion.

Open Problems

There are some Hilbert problems that are still open, but most left are either not precise enough to really be solved or extremely technical. For example the sixth asks “Axiomatize all of physics.”

One more realistic problem for all of us is to ask do we agree with the ideas of Hilbert? Do you think his comments about mathematics still apply today? Do they also apply to complexity theory? What do you think?

Hilbert’s speech ends:

The organic unity of mathematics is inherent in the nature of this science, for mathematics is the foundation of all exact knowledge of natural phenomena. That it may completely fulfill this high mission, may the new century bring it gifted masters and many zealous and enthusiastic disciples!

Of course he was talking about the twenty century—yet his excitement seems to still apply and be relevant to this century.

34 Comments leave one →
  1. Math Boy permalink
    October 17, 2010 8:40 am

    Most of automata theory is fairly useless. The original motivation seemed to be language parsers, and that’s fallen by the wayside.

    You can add to that oracle results. The point is as simple as the fact that if it can be settled by relativizable techniques then it wasn’t a particularly interesting question in the first place.

    Of course, all “fashionable” stuff is all useless (web algorithms, network nonsense, economic algorithms.) None is likely to pass the smell test in even five years (even though it did get their proponents tenure.)

    • Anonymous permalink
      October 17, 2010 2:18 pm

      You seem to have a naive and local view of mathematics and science. Automata theory is well and alive and used extensively in verification of both software and hardware. Important questions, models, and answers don’t arrive out of the blue one fine morning. They arrive after people explore various threads and build a deeper understanding of what is going on.

      • rjlipton permalink*
        October 18, 2010 1:52 pm

        Anonymous

        Hi. You are right of coures. But once language theory was central: AFA, ballon automata, AFL, stack automata, stack automata pumping lemma—most of these topics are no longer as central as they once were. I am a big fan of all things about finite automata and have discussed them many times.

        dick

    • October 18, 2010 2:59 am

      I’m somewhat confused by “Most of automata theory is fairly useless.”

      Mildly Context Sensitive Languages are used in computational linguistics.
      Büchi automata underlie model checkers.
      Obviously CFGs underlie all our parsers
      L-systems are used to generate natural flora in movies and video games, as well as virtual cities
      Graph grammars are used to generate video game levels:
      http://portal.acm.org/citation.cfm?id=1814257&dl=GUIDE&coll=GUIDE&CFID=106230597&CFTOKEN=17028062

      This is just a few examples that pop into my head immediately.

    • OM57 permalink
      October 20, 2010 1:15 pm

      The statemnt of the uselesness of most of automata theory, under some interpretation, is probably the most wrong statement I have never seen. Finite-state automata are the second most important concept in TCS (after Boolean functions). It is true that any theoretical domain may degenerate into proliferation useless results (compexity is not an exception) but the the strangth of automata theory is not by its theorem but by the conceptual picture of a discrete event dynamical system which suggests a way to look at and analyze complex systems. This is also the interface between software and hardware. Classical textbooks emphasizing the parsing application indeed mislead. The important theorems are indeed few (Kleene, Myhill-Nerode, Buchi-Mcnaughton, Schutzenberger) but theorems are not the point in automata theory, its the picture of the world as a product of interacting systems is extremely important.

  2. October 17, 2010 9:19 am

    the sixth asks “Axiomatize all of physics.” is not stated very clearly,since Axiomatization was not defined very clearly in Hilbert period.Today this question may stated or comprehended in two senses:Axiomatization is formal,or Axiomatization may not be formalization.I remember that Hao Wang quoted some articles as saying that every physical equations had been computable if the input has not violated physical conditons or the inputed data happen in physical world.In the sense of formalization,does this mean all of physics may be axiomatized(computable)?

  3. October 17, 2010 10:03 am

    The informal nature of the problem of axiomatizing all of physics seems to me like a feature, not a bug. It’s not, strictly speaking, a problem at all, but rather a suggestion not just for a research program, but really for a whole collection of research programs. Two of the seven Clay problems are arguably instances of this problem – the Navier-Stokes problem, and the Yang-Mills problem. And then there are other related problems, such as laying a rigorous foundation for statistical mechanics, which has motivated work by people such as Ruelle, Khinchin, Kolmogorov, and many others.

    Incidentally, on whether the results of theory can be explained to someone on the street: the unsolvability of the halting problem seems like an example. Certainly,it’s been explained many times in popular books.

    • October 17, 2010 10:58 am

      I know Mr.Nielsen is a scientist in Quantum Computation,which may be regarded as a interdisplince between physics and computar science or math. A lot of physics knowledges are based on intuitions or heuristical empiricals,by formalization or systemization,one may find questions or problems that lead to original ideas or by heuristical observation,one may finde solutions to problems more easily than formalization.I think ,people such as Kolmogorov was motivated this way.

      Informtion therories such as Shannon’s or Kolmogorov Complexity is closely related to physics,and NP=P? and CT or Church-Turing Thesis ,seem to me to be related to physics implicitly,and one may give a lot of examples alike.But those do not nessarily mean Axiomization may be applicable to all of physics,or application of axiomization to all of physics is meaningful,rather,physics is more heuristical or observations-motivated.

      • October 22, 2010 7:19 am

        The following is quoted from Scott Aaronson∗

        David Deutsch, of quantum computing fame, has argued that even mathematical statements are ultimately
        about physical reality—since mathematics is rooted in computation, and the laws of physics determine
        what is and isn’t computable [16].12 Whether or not you agree with this, it does suggest the following
        “physical process criterion” for mathematical truth:
        We should expect a mathematical question to have a definite answer, if and only if we can phrase
        the question in terms of a physical process we can imagine.

  4. October 17, 2010 10:06 am

    For me, it is inspiring to listen to audio recordings of Hilbert saying Wir mussen wissen, wir werden wissen (“We must know, we will know.”)

    Although Dick’s post asserts “(we) cannot imagine having a speaker today start this way”—and it is true that such lectures are not common—it is also true that such Hilbert-style sentiments appear in every decade and in every STEM discipline, both in speech and in print (indeed, I maintain a pretty large database of them).

    For example, just now I have added to that database an article that appeared today, in Science, by David Shaw and collaborators, titled “Atomic-Level Characterization of the Structural Dynamics of Proteins”.

    Although Shaw’s group is studying a class of protein-folding problems that (considered formally and adversarially) is NP-complete, they nonetheless make outstanding progress in practical instances, for the common-sense reason that Nature is not adversarial, but rather poses for us folding problems that have sufficient structure to render them tractable … even though it may be very difficult for us, at least initially, to appreciate the mathematical nature of this structure.

    In effect, the slogan of today’s synthetic, systems, and regenerative biologists is identical to that of Hilbert’s generation of mathematicians: “We must know. We will know.” And this unity extends also to the quantum level, for example in quantum chemistry, materials science, and quantum systems engineering. The point being, that nowadays in all of these STEM disciplines, it is widely held (and with good reason) that “For us, there shall be no ignorabimus.”

    Since Hilbert’s day, theoretical computer science has taught us two vital lessons that cast light on Hilbert’s “no ignorabimus” maxim. The first lesson is that progress generally is infeasible in the face of worst-case, adversarially posed problem instances (as we have appreciated since the work of Godel, Kolmogorov, and Chaitin).

    The second lesson is to examine very carefully the problems that Nature poses to us—both abstract and practical, both classical and quantum—because very often we will find that Nature does not pose problems adversarially, but rather generates them via dynamical processes that naturally provide us with the (oft-hidden) structures we need for solutions to be feasible.

    As David Shaw is quoted in the accompanying Science commentary: “I love this. It’s just the most fun I’ve ever had. It’s very satisfying.”

    Surely, no one can ask for more of math, science, and engineering than that.

    And so, if David Hilbert could see the progress we have made in recent decades, and that we are continuing to make, then IMHO he would be well satisfied that his guiding philosophy “wir mussen wissen, wir werden wissen” retains its vitality today.

  5. steve uurtamo permalink
    October 17, 2010 10:40 am

    > Can we explain the P=NP question in this way? Can we explain in this way any of the great results of theory?

    sure. the idea isn’t that you can explain it to the man on the street in 5 seconds, but that it can be broken down into simple pieces. and that can easily be done. all of the sweeping under the rug that is being done here can be explained more clearly, but it’s not the main point, and is only necessary if the listener is interested:

    “how much easier (if at all) is it to check to see if someone’s solved a hard problem correctly, than it is to solve it yourself?”

    “what’s a hard problem?”

    “you know, like figuring out if you can visit all the animals in a zoo without seeing one twice.”

    “so what’s an example of solving this?”

    “drawing the path on the map. and the problem of checking it is making sure that the drawn path follows the rules of the problem.”

    “sure, it’s way easier.”

    “but what about for *all* possible maps?”

    “uh, i dunno.”

    no need to explain P or NP. now, the subtlety may lie in the fact that P is a lot bigger than the linear time checking that i seem to have used to my advantage in adversarially phrasing the problem as if it has an obvious answer. but the main idea is there — is checking always a lot easier than solving, for some simply described class of problems? i think that all of the big questions and big results have commonsense explanations. otherwise nobody would be able to remember what they are.

    s.

  6. Stephan Mertens permalink
    October 17, 2010 11:16 am

    The lobby of the Mathematical Institute in Göttingen is commonly known as Hilbert space because (a) it shows a bust of David Hilbert and (b) ‘space’ and ‘room’ are the same word in German (‘Raum’)

  7. Anon permalink
    October 17, 2010 11:41 am

    Can the experts in TCS also create a list of 10/20 famous open problems in TCS. These might drive the directions for research in the next century.

    • October 17, 2010 6:52 pm

      Anon, you might want to take a look at Smale’s Problems, a list that Stephen Smale composed in 2000, at the invitation of Vladimir Arnold, then-president of the International Mathematical Union.

      Which of Smale’s problems qualify as natural problems for TCS? That is one of those questions regarding which a strictly uniform consensus is neither feasible nor desirable.

    • Ryan Williams permalink
      October 19, 2010 3:15 pm

      There is a nice list of famous open problems being formed here:

      http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science

      The nice thing is that the problems are ordered by “vote”: users vote on those that they like. For example, the current top 3 are “What’s the complexity of Matrix Multiplication?”, “Is Factoring in P?” and “Is Graph Isomorphism in P?”.

      I invite everyone to contribute their own personal favorites, and vote themselves (you can vote once you gather enough reputation on the site, but this is accomplished by simply answering one or two questions).

  8. October 17, 2010 8:04 pm

    ….the sixth asks “Axiomatize all of physics.”

    The axiomatization of even just Quantum Field Theory has not gone very well, as far as I know.

    • October 17, 2010 9:31 pm

      Mr.Arun,do you mean renormalization in Quantum Field Theory?

      • October 17, 2010 10:35 pm

        No, I mean that the axiomatic (or algebraic) approach has trouble with non-Abelian gauge theories, which are experimentally well confirmed and handled by physicists’ pragmatic methods.

        In this regard, the Clay Mathematics Institute’s Millenium prizes perhaps explain some of the problem (or opportunity):

        http://www.claymath.org/millennium/Yang-Mills_Theory/

        http://www.claymath.org/millennium/Yang-Mills_Theory/ and links on that page.

        Arthur Jaffe and Edward Witten explain: “On the other hand, one does not yet have a mathematically complete example of a quantum gauge theory in four-dimensional space-time, nor even a precise definition of quantum gauge theory in four dimensions. ” and

        “QFT has in certain cases suggested new perspectives on mathematical problems, while in other cases its mathematical value up to the present time is motivational.

        In the case of the geometric examples cited above, a mathematical definition of the relevant QFTs (or one in which the relevant physical techniques can be justified) is not yet at hand. Existence theorems that put QFTs on a solid mathematical footing are needed to make the geometrical applications of QFT into a full-fledged part of mathematics. Regardless of the future role of QFT in pure mathematics, it is a great challenge for mathematicians to understand the physical principles that have been so important and productive throughout the twentieth century.”

      • October 18, 2010 4:31 am

        Wang Xiuli, the phrase “axiomatic quantum field theory” is commonly associated with Arthur Wightman, whose ideas are described in the Wikipedia article on Wightman axioms.

        One of the many choices that I greatly admire in the Nielsen and Chuang textbook Quantum Computation and Quantum Information is that the foundations of quantum mechanics (in Chapter 2) are called “postulates” rather than “axioms.” Another admirable choice is that Nielsen-Chuang postulates omit the concepts of “spatial separation” and “relativistic invariance.” This is a very reasonable assumption in the context of quantum computation, and the resulting postulates are far simpler than the Wightman axioms.

        We have to keep in mind, though, that by the end of the 21st century it is very likely that textbooks describing both classical and quantum dynamics will begin with new postulates, that arise from, but are not identical to, the dynamical postulates of the 20th century. After all, such shifts have happened in every previous century, in every branch of mathematics and science, and we have no reason to believe that this evolutionary process has ended (in fact, the process seems to be accelerating).

        As von Neumann once reminded us: “In spite of the fact that quantum mechanics agrees well with experiment, and that it has opened up for us a qualitatively new side of the world, one can never say of the theory that it has been proved by experience, but only that it is the best known summarization of experience.”

        Moreover, under the natural isomorphism dynamics → complexity theory, and experiment → practical problem-solving, von Neumann’s principle applies also to theoretical computer science.

        This is good news for young people, because it means that the starting postulates of both classical/quantum physics and theoretical computer science are certain to evolve in directions that will create the new STEM enterprises upon which fresh career opportunities have always depended … more so in our crowded &challenging 21st century, than in any previous century.

      • October 18, 2010 6:00 am

        As von Neumann once reminded us: “In spite of the fact that quantum mechanics agrees well with experiment, and that it has opened up for us a qualitatively new side of the world, one can never say of the theory that it has been proved by experience, but only that it is the best known summarization of experience.”

        So, even the likes of von Neumann can be silly, because NO theory is ever proved by experience, epistemology does not seem to be the strongest point of mathematicians and even physicists.

      • October 18, 2010 6:48 am

        Mr.Sidles,thank you for the URL about axiomatization of Quantum Field Theory.By the way ,I am not a physicist.

        I do not think there is any difference between postulate and axiom.If postulate is only used in physics -like sciences, the postulate may be verified or falsified by experiments,while axiom can not be so if it is consistent.But if we use axiomatization in such a sense,then “axiomatize all of physics ” is meanless.I think it is a great difference between math and physics.

      • October 18, 2010 6:56 am

        We know from Model Theory,that if a theory(formalized sentence or a set of formalized sentences ) is consistent ,there exists a model for it.

      • October 18, 2010 7:56 am

        It is very interesting to study the incidence of “postulate” versus “axiom” in the literature (using arxiv’s full text search, for example).

        In the scientific and engineering literature, “postulate” is more common than “axiom” (by a considerable margin), and it commonly happens, that the statements given as postulates at the beginning of an scientific article or textbook, are pragmatically modified and/or experimentally proven wrong later on in that same article or textbook.

        In contrast, in the mathematical literature the word “axiom” is more common than “postulate”, and it is generally understood that statements given as axioms at the beginning of a mathematical work will be respected throughout.

        The computer science literature is a hybrid case: unlike the rest of the science and engineering literature, the word “axiom” dominates “postulate” in computer science usage (at least on the arxiv server’s full-text search). Is this because proving theorems is a more common goal in computer science and engineering than in other scientific and engineering disciplines?

        The quantum literature is even more intricately hybridized: the axioms/ postulates of quantum mechanics (as presented for example in the Nielsen/ Chuang textbook) have remained unaltered since the pioneering work of Stinespring, Choi, Lindblad, Kraus etc. in the 1970s. Surprisingly, however, the mathematical toolset of modern quantum system simulation does not strictly respect these postulates (dynamical trajectories on tensor network state-spaces are a good example).

        Pragmatically, the various disciplines associated to quantum system analysis and simulation skate over these contradictions, and thereby have sustained a Moore-type expansion, over many decades, both in their practical capabilities and in their volume of literature.

        The lesson for students in every STEM discipline, perhaps, is to respect the axioms and postulates of the existing literature … and yet be prepared to alter these axioms and postulates—at first pragmatically and later rigorously—as circumstances require and new opportunities and enterprises emerge.

        This is why I really liked the Hilbert quote that Dick Lipton selected “As long as a branch of science offers an abundance of problems, so long is it alive.” This provides young people with solid reasons to foresee that we are at the beginning of what will be the greatest century ever for the STEM enterprise.

      • October 18, 2010 1:04 pm

        Mr Wang Xiuli:

        What I meant is this, by Arthur Jaffe and Edward Witten, as they explain in detail the Yang-Mills open problem in the Clay Millenium Prizes:

        “…one does not yet have a mathematically complete example of a quantum gauge theory in four-dimensional space-time, nor even a precise definition of quantum gauge theory in four dimensions.”

        “QFT has in certain cases suggested new perspectives on mathematical problems, while in other cases its mathematical value up to the present time is motivational. In the case of the geometric examples cited above, a mathematical definition of the relevant QFTs (or one in which the relevant physical techniques can be justified) is not yet at hand. Existence theorems that put QFTs on a solid mathematical footing are needed to make the geometrical applications of QFT into a full-fledged part of mathematics.”

      • October 18, 2010 8:29 pm

        Mr.Arun,thank you for your clarification.

  9. October 18, 2010 3:20 am

    I’ve the debated the question “what does it mean for mathematics to be simple?” with friends before. Two reasonable sounding answers we arrived at are terseness, (how many characters do you use?) and comprehension time (how long does it take someone to “get it”).

    The first is an attractive way to claim that problems like the Poincaré conjecture/Perelman theorem are simple: “Every compact, simply connected 3-manifold is homeomorphic to the 3-sphere.” But good luck getting the “man on the street” to understand that.

    On the other hand, if you go by comprehension time then it would appear that the simplicity/complexity of a mathematical statement is highly dependent on the background of the listener/reader. This seems more true to me, but it throws a monkey wrench in Hilbert’s idea of a good problem being simple. Simple to whom? To the man on the street? To computer scientists? To engineers? To scientists? To mathematicians? Which specialty of mathematicians?

    Perhaps one failing of Hilbert’s comments is that he doesn’t more explicitly address the role of community in the welfare and health of a scientific discipline.

    • October 18, 2010 6:08 am

      The first is an attractive way to claim that problems like the Poincaré conjecture/Perelman theorem are simple: “Every compact, simply connected 3-manifold is homeomorphic to the 3-sphere.” But good luck getting the “man on the street” to understand that.

      This kind of simplicity is pure illusion, borderline cheating, it just ignore the HUGE amount of definitions and theories dangling in the shadow of the “simple” words compact, simply connected, 3-manifold, homeomorphic.

    • October 18, 2010 6:12 am

      Dear Bernstein,maybe,we can define simplicity by Kolmogorov Complexity and computational complexity.
      “Simple to whom? To the man on the street? To computer scientists? To engineers? To scientists? To mathematicians? Which specialty of mathematicians?”
      By Kolmogorov Complexity ,one can solve the problem,for KC specifies the knowledge needed to understand or comprehend the question,obviously,mathematicians knowledge is different from engineers in KC.And maybe we can evaluate one’s IQ by computational complexity,one who can find more efficient algorithm to solve problem is smarter than other ,or one who solve problems more quickly is smarter than other.Yes KC and CC may influence each other,so it is complicated problem in this aspect.

  10. October 18, 2010 10:14 am

    Apropos of nothing more than pure enjoyment, I did a quick study of the relative frequency and usage of “axiom” versus “postulate” in the recent math, science, and engineering literature.

    In doing so, MathSciNet led me to a wonderfully thought-provoking Annals of Mathematics article by Michael Freedman, titled “Complexity classes as mathematical axioms” (2009).

    Michael’s article begins with crisply-stated premise that “Complexity theory, being the metrical version of decision theory, has long been suspected of harboring undecidable statements among its most prominent conjectures … While the techniques of diagonalization and oracle relativization have produced important separation results, for nearly forty years the most interesting (absolute) separation conjectures, such as P≠NP, remain unproven, and with the invention of ever more complexity classes, analogous separation conjectures have multiplied in number. With no prospect in sight for proving these conjectures (within ZFC) and the suspicion that some are actually independent, we propose considering them instead as potential axioms and looking for what implications they might have in mathematics as a whole.”

    As Dick’s starting post said, “Areas survive and thrive exactly when they have a multitude of interesting problems” … and articles like Freedman’s are strong evidence (IMHO) that TCS is thriving.

    • October 18, 2010 8:53 pm

      hehe.Yes,it is an interesting pair of two terms.But I think the most important or fundamental question is the difference between physics and math,between the approaches of them.One just requires consistence ,and the other requires truth.One requires proof,and the other requires verification by experiments .The most important is not only just words only,but also,or rather,moral/spiritual differenc.

      • October 18, 2010 9:05 pm

        We know from model theory ,that interpreted correctly,there is at least a model for consistent theory .Therefore,consistence is in truth.Conversely,truth is in consistence.So,on the condition of correct interpretation,truth is equivalent to consistence,and the difference between math and physics is just the difference between the appoaches to truth or consistence.But,do we discuss physics or math or computer science?I feel that we are discussing scientific philosophy,may we return to more concret question or problem?

      • October 19, 2010 5:32 am

        Wang Xiuli, we are arming ourselves with the mathematical and informatic tools we need to investigate concrete physical questions like “Is the dynamical state-space of Nature a Hilbert space?” And concrete mathematical questions like “Are there languages in P that have no algorithm that provably recognizes them?”

        So definitely, we are not discussing philosophy … or are we?

      • Luke G permalink
        October 23, 2010 2:10 am

        I think saying “consistency and truth are the same thing” is a bit of a stretch given the usual meaning of the words. A consistent theory can prove “there exists X such that P(X)” and also prove for each individual X “not P(X)”. (This would be an omega inconsistent theory.) A specific example to think about is the theory of Peano Arithmetic plus the axiom “Peano Arithmetic proves 1=0”.

        The term for a system of axioms that only proves true theorems is “sound”. This is a much stronger property than being consistent.

        It’s true that all consistent theories have a model, but the model for unsound theories will be what’s called “nonstandard”.

  11. Greg permalink
    October 18, 2010 4:35 pm

    Technically, Hilbert’s 10th problem did not ask whether such a decision procedure to solve polynomials existed – but instead how to define it. In other words, Hilbert had assumed that such a decision procedure existed – and therefore he would no doubt have been very surprised by the modern proof that no such procedure even exists.

    The moral here of course is – when asking a question – be sure to verify your assumptions. Otherwise, the question you ask – might not be the right question.

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