My TEDxCaltech talk
A month ago, Caltech hosted a daylong event called “TEDxCaltech / Feynman’s Vision: the Next 50 Years”, which was attended by about a thousand people. Celebrity participants included Stephen Hawking, Carl and Michelle Feynman (Carl told me he’s a fan of the blog—hi Carl!), and Ondar, a Tuvan throat-singer who pretty much stole the show.
Videos are finally being posted on YouTube; my talk is here. My goal was to cover the P versus NP question, quantum computing, conceptual issues in quantum mechanics, and Feynman’s relation to all three, while also cracking crude masturbation jokes (in a talk like this, one has to bring out the heavy humor cannons), and to finish in 15 minutes. I don’t know how well I succeeded—but if I die tomorrow, then at least Stephen Hawking was in the audience when I made my case for P and NP being as big a deal as anything in physics.
Two explanatory comments:
- By far my most successful joke was a reference to “prime numbers, such as 3, 5, 1…” Before the lunch break, the emcee had told everyone to be back by 1:35, “which I’m sure you nerds will remember since it’s the first three prime numbers.”
- Yeah, I know the current upper bound on the matrix multiplication exponent is 2.376, not 2.736! It was correct on the slides I submitted, but got transposed when the slides were converted into “TED format.”
If you think my talk stinks, my only defense is that showing up to give it was already an accomplishment: my flight (from Tel Aviv to LA through Newark) was canceled because of a snowstorm, so I arrived at Caltech exhausted and barely conscious, via a 36-hour alternate route through Frankfurt and London.
I have to confess that I was skeptical of this event’s entire premise. Richard Feynman was famous for his contempt of pomp and authority; would he really have enjoyed a heavily-scripted day extolling him as a secular saint? In the end, though, the quality of many of the talks made the event more than worthwhile for me, even without counting Ondar’s throat-singing as a “talk.” I particularly enjoyed the cosmology talk of fellow-blogger Sean Carroll (yo, Sean), the Feynman stories of Lenny Susskind, a demonstration of the mind-blowing WorldWide Telescope by Curtis Wong of Microsoft, and a “Who Wants to be a Millionaire?” parody skit put on by the three “black hole bettors” (John Preskill, Kip Thorne, and Hawking, the last of whom wheeled into the auditorium to thunderous applause and the opening fanfare of Thus Spake Zarathustra). I understand that all the talks will eventually be on YouTube here.
Thanks to Michael Roukes, Mary Sikora, John Preskill, Ann Harvey, and the other organizers for putting this thing together and for inviting me.
Follow
Comment #1 February 16th, 2011 at 5:15 pm
Really nice talk!!! I enjoyed it a lot! The connection between Feynman and complexity/quantum-computing was genius! Made quantum computing to seem fun 😛 !!!
Comment #2 February 16th, 2011 at 6:18 pm
I loved the talk! In addition to being very inspiring, informative and funny it was suffused with an irreverence that captured the spirit of Richard Feynman better than many of the stories of Feynman’s remarkable genius.
For the record, Shtetl Optimized groupies abounded at TEDx Caltech. Scott was a scientist rock-star thronged by Casio calculator watch wearing women.
Comment #3 February 16th, 2011 at 6:27 pm
I can verify Steve E’s account. Scott’s talk was a huge hit, and women were swooning. Some of the men, also.
Seriously, the talk was great and it was nice to see someone tweak Feynman rather than beatify him.
Comment #4 February 16th, 2011 at 7:53 pm
Terrific post! Thanks to everyone for this wonderful effort.
As a helpful hint, for some imponderable reason there are many more on-line talks presently available at “http://tedxcaltech.com/” (talks by Wong, Susskind, Preskill, Thorne, Venter, and Marlow) than at the otherwise almost-identical site “http://www.tedxcaltech.com/”.
A very striking impression (so far) is that these talks are individually wonderful in their subject matter … and yet they almost never reference one another. Had Feynman himself given the final lecturer—following Craig Venter’s fabulous lecture!—he might have attempted to close these gaps.
Comment #5 February 16th, 2011 at 9:08 pm
Awesome talk! This is by far the coolest TEDx event I’ve heard of yet. I hope you had a memorable experience!
Comment #6 February 17th, 2011 at 12:10 am
Your talk was good given the time constraints. However, I think you were a bit unfair to Feynman about his challenge concerning answering math questions. As I understood his challenge had to be a single yes or no question (a specific exponent is a lot more than 1 bit of information).
Comment #7 February 17th, 2011 at 2:20 am
Cool talk. Loved it!
Comment #8 February 17th, 2011 at 6:07 am
Joshua: A lot of people raised that criticism after the talk, but I didn’t understand it. We could clearly approximate a question like “how fast can two matrices be multiplied?” by a small number of yes/no questions, each of which Feynman (by his assertion) could answer correctly:
Is there an n^2 matrix multiplication algorithm? No?
How about an n^2 log(n)^O(1) algorithm? No?
How about an n^2.1 algorithm?
How about an n^2.4 algorithm?
Comment #9 February 17th, 2011 at 8:49 am
Scott: while what you said it’s true, it’s obviously not in the spirit of Feynman’s challenge. Since any question can be translated in a series of one bit questions (just do a binary encoding of the right answer and ask bit by bit), his restriction would not restrict anything, being thus meaningless.
Comment #10 February 17th, 2011 at 9:25 am
Whoa, sorry! I just had to restore this post after a bizarre WordPress bug deleted it.
Maxwell daemon: OK, then just replace my original question by the four specific yes/no questions in my comment above. Do you believe that Feynman would have been able to intuit the answers to them?
Incidentally, the following approach:
just do a binary encoding of the right answer and ask bit by bit
doesn’t work for questions with many possible right answers, or many possible binary encodings of the same right answer. (That’s closely related to a big issue in complexity theory called “equivalence of search and decision”!)
Comment #11 February 17th, 2011 at 9:55 am
Cool. I conjecture that your last paragraph is just a conjecture. Am I right? Can you give an example of a natural search problem that we don’t know how to translate into decision problems?
About Feynman, I think he could intuit the answer to the first question (answering no, and don’t ask me to prove it), but not the other ones.
But consider the following decision problem: which is the BB(137)th bit in the binary expansion of \pi?
I don’t think Feynman could intuit the answer, by the same reason that he couldn’t answer your last three questions.
I’m at a loss trying to find a good definition of what would be a fair question to ask. But it certainly shouldn’t involve fine-grained detail.
Comment #12 February 17th, 2011 at 10:05 am
I don’t know what was the actual joke, but… 1 is not a prime number. The math police will leave you all alone now.
Comment #13 February 17th, 2011 at 10:22 am
Maxwell daemon: Good questions!
There are some problems, such as finding a Nash equilibrium, for which
1. The answer to the decision problem (“is there a Nash equilibrium”) is always YES—that’s Nash’s Theorem!
2. The search problem (“find me a Nash equilibrium”) is PPAD-complete, as proved by Goldberg, Daskalakis, and Papadimitriou.
So, the search and decision problems above can’t be polynomial-time equivalent unless FP=PPAD.
But more to the point, we don’t know of any decision problem (even a completely different one) whose solution would be necessary and sufficient to solve the Nash equilibrium search problem. However, you’re right that that’s just a conjecture: as far as I know, we don’t even have complexity-theoretic evidence that no such decision problem exists.
(Does anyone know if there exists a search problem for which we can give evidence that there’s no equivalent decision problem? I raised this question more-or-less explicitly in my recent paper The Equivalence of Sampling and Searching. I want to know the answer!)
Now, as for the BB(137)th bit of π: sure, we agree that’s an unfair question! I’d say that what makes it unfair is that (a) it’s of no mathematical interest, and (b) related to (a), the difficulty in answering it comes “merely” from astronomical calculation. (Well, more than astronomical: the value of BB(137) is probably independent of ZFC!) Whether there’s a super-fast matrix multiplication algorithm doesn’t suffer from either problem.
BTW: personally, I’m not at all sure that there’s no O(n^2) matrix multiplication algorithm, at least over some fields. I’d guess there isn’t, but not with any great strength of conviction.
Comment #14 February 17th, 2011 at 10:24 am
I don’t know what was the actual joke, but… 1 is not a prime number.
(bangs head against desk)
That was the joke.
(The emcee’s other mistake, of course, was omitting 2.)
Comment #15 February 17th, 2011 at 10:33 am
Scott says: “I’m not at all sure that there’s no O(n^2) matrix multiplication algorithm …”
Dick Lipton and Ken Regan’s Gödel’s Lost Letter and P=NP topic “Fast Matrix Products and Other Amazing Results” covers some of this material — the conjectured answer is “yes” … see e.g. Sara Robinson’s SIAM News article “Toward an Optimal Algorithm for Matrix Multiplication” (2005).
The geometric intuition is that raising/lowering one-forms/tangent vectors is O(n) per raising/lowering operation, *provided* that one is raising/lowering a basis-spanning set of one-forms/vectors, such that the individual raising/lowering operations can “help” one another.
Comment #16 February 17th, 2011 at 12:56 pm
“But more to the point, we don’t know of any decision problem (even a completely different one) whose solution would be necessary and sufficient to solve the Nash equilibrium search problem.”
I’m confused as to why this is so. If you were to index each strategy profile with an integer, couldn’t you specify the following decision problem:
Given a game G and natural numbers L (as in lower bound) and U (as in upper bound), does there exist a strategy profile P whose index is between L and U that is a Nash equilibrium?
In general, I would think that there aren’t any search problems without an associated decision problem. I.e., given a search problem S, consider the decision problem D:
Given a binary-encoding-with-blanks X of a candidate solution to an instance I of problem S (e.g., X = ‘100___01_01___01__0’), is there a way to fill in the blanks of X that accurately solves the search problem?
(What am I missing?)
Comment #17 February 17th, 2011 at 1:19 pm
Philip: Good question! Solving the decision problem that you state would suffice for finding a Nash equilibrium, but it might not be necessary (i.e., your problem might be strictly harder). One could imagine an algorithm that finds a Nash equilibrium, but not necessarily a Nash equilibrium within some specified interval in your favorite ordering scheme.
(And in fact, it’s known that many problems of the latter type are NP-complete, and therefore probably harder than the pure problem of finding a Nash equilibrium.)
Comment #18 February 17th, 2011 at 2:36 pm
Actually, since one variant of this, at LANL, has Feynman guessing any answer to within 10 percent, the matrix multiplication problem is easy: I’ll guess 2.2. Then 2.376 is at most 10 percent higher, while 2 is at most 10 percent lower. While there is no way Feynman would have guessed the 2.376 algorithm, a reasonable approach under the “10 percent” rule is to guess 10 percent above the lowest bound and in this case it would turn out to work. And since the game at Princeton involved guessing the answer without proof, the P/NP one is easy too: just guess “not equal”.
Since Feynman also tended to change the rules a bit in the Princeton version (for example, cheating on the Banach-Tarski paradox by switching to real physical oranges as a model of the sphere), one can also cheat by changing the rules in matrix multiplcation. In this case, I’ll guess 2.7. This is within 10% of the naive bound of 3. It is even closer than that to Strassen algorithm. And as for the Coopersmith-Winograd algorithm, well, “I thought you meant working on a real physical computer, where cache is important, and not some abstract device where huge constant factors don’t matter”.
But yeah, it is easy to come up with problems which are too hard to answer, like the tangent of 10^100 problem.
Comment #19 February 17th, 2011 at 3:47 pm
Just watched the video. Can’t help but wonder whether you’ve ever done stand up before. Quite apart from the fact that you had great delivery you simply look like a comedian. And I mean that as a compliment.
Comment #20 February 17th, 2011 at 4:10 pm
“Does anyone know if there exists a search problem for which we can give evidence that there’s no equivalent decision problem?”
Very interesting problem. If you put some money behind the question, I (and hopefully others) will dedicate this month of my work to it. Just notice that I’m a grad student, so my time isn’t worth very much.
Now for the Feynman questions, I’d also add the requirement that they are fundamental in some sense. That is, the question “Is there a matrix multiplication algorithm that attains the naïve lower bound?” would be a fundamental one, but asking about specific complexities between O(n^2) and O(n^3) would not.
Comment #21 February 17th, 2011 at 4:15 pm
“the value of BB(137) is probably independent of ZFC!”
¿why? I know that BB(n) is uncomputable, but independent of ZFC? You are asking a concrete question about a physical device that does not involve infinities in any way. Probably we won’t be able to say much more than it being a very large finite integer, but…
Comment #22 February 17th, 2011 at 6:27 pm
Maxwell daemon: Sure, I’m willing to offer you or anyone else $100 if (in my judgment) you solve the problem!
As for BB(137): yes, I completely agree that it’s a concrete number, whose value is independent of your beliefs about set theory. All I meant is that its value probably isn’t provable from the axioms of ZFC.
Why? Well, consider a Turing machine M that enumerates all possible ZFC proofs, halting when it finds a proof of the inconsistency of ZFC. Suppose M has n states. Then if you knew BB(n), you could determine (presumably) that M doesn’t halt, and therefore that ZFC is consistent. So if ZFC proved the value of BB(n), then it would also prove its own consistency, which is impossible by the Second Incompleteness Theorem.
Furthermore, I suspect that the n that one could extract from the above argument is a good deal less than 137! But I’m not sure … that would be a great project for someone.
Comment #23 February 17th, 2011 at 8:33 pm
Scott, interesting, my suspicion is in the exact opposite direction. ZFC is a very complicated axiomatic system. Handling all the axioms in a formal setting will take a lot of work. Note that you can save some effort for your Turing machine by removing Choice and Foundation since they are independent of the others. But even then, I expect that the resulting Turing machine would still have a lot more than 137 states.
Comment #24 February 17th, 2011 at 9:07 pm
Joshua: Sure, the first TM you came up with would have WAY more than 137 states! I meant that, with sufficient labor (which I wouldn’t wish on my worst enemy!), I suspect one could find some TM with fewer states whose non-halting is provably equivalent (perhaps very nontrivially so) to Con(ZFC). Maybe I’m wrong.
Comment #25 February 17th, 2011 at 9:10 pm
Ah, phrased that way, I just don’t have any intuition either way.
Comment #26 February 17th, 2011 at 10:20 pm
Scott, in your prediction at the end, are you implying that you think that ECT will hold up after all, or simply that there will be *some* crack in QM as we understand it today?
Comment #27 February 17th, 2011 at 10:33 pm
“King Nothing”:
Just watched the video. Can’t help but wonder whether you’ve ever done stand up before … you simply look like a comedian.
Aw, shucks. 🙂 I’ve heard that from other people, but no, apart from an ill-fated 15-year stint in the Catskills between high school and college, I have zero professional comedy experience. If I look like a neurotic, hyperactive, swaying-back-and-forth Woody Allen, it’s not because I’m trying to.
Comment #28 February 17th, 2011 at 10:44 pm
yfyk:
1 a prime number?
1 used to considered a prime number.
RO sez: 1 still should be considered a prime number. The usual definition is “A number is prime if it is only divisible by 1 and itself, unless it is 1”. This is an obviously stupid definition, excluding 1. The usual rational for the outrage is that otherwise most of the number theory theorems would be of the form “for any prime number p != 1, bla bla bla”. But so what? Are number theorists such lazy wads that they can’t say “!= 1”? Furthermore, many prime number theorems also don’t hold for p = 2, so some qualification us needed anyway. A simpler, cleaner definition is always better than complicated one.
Comment #29 February 17th, 2011 at 10:47 pm
Joshua:
Ah, phrased that way, I just don’t have any intuition either way.
My intuition mostly just consists of the observation that very small Turing machines can already exhibit extremely complicated behavior, so much so that BB(5) is still not known and BB(6) will plausibly never be known. (Furthermore, universal TMs can be as small as 2 states and 3 symbols, though admittedly—as far as is known today—only with a complicated input encoding.)
Actually, now that I think about it, I’m liking more and more this challenge of finding the smallest TM whose non-halting is provably equivalent to Con(ZFC). So: any takers?
I’m willing to offer a reward of $20,000 divided by the number of states in your TM.
Comment #30 February 17th, 2011 at 11:06 pm
Bram:
are you implying that you think that ECT will hold up after all, or simply that there will be *some* crack in QM as we understand it today?
Neither. If there were “some crack in QM as we understand it today,” that would almost certainly be the scientific event of my lifetime—but while I hope for it, I’m not holding my breath. Conditioned on such a crack, I have no idea whether it would restore the ECT, make the ECT even less likely than today, or neither.
My point was just that quantum computing research has, as a welcome byproduct, brought a torch of clarity into the dungeon of QM itself. To take a few examples, we now think of entanglement as a useful resource for multiplayer games, interference of amplitudes and the exponentiality of n-particle Hilbert space as the central features of QM (completely different from the central features that Bohr or Heisenberg would have identified), and infinite-dimensional Hilbert spaces as mostly-irrelevant complications.
My “prediction” that there’s a big advance in quantum foundations still to come is, frankly, just a hope—like with free will, I can’t give very good reasons to believe in it except that I couldn’t live with the alternative.
On the other hand, if there is such an advance, then I feel safe in predicting that the vastly cleaner picture of QM that’s come out of quantum computing and information will help us get to it.
Comment #31 February 17th, 2011 at 11:11 pm
Raoul:
1 still should be considered a prime number.
I disagree. The fundamental reason 1 isn’t considered prime is that if it was prime, unique factorization would fail.
And at the end of the day, we don’t care about the primes because they’re only divisible by themselves and 1; we care about them because they’re the multiplicative building blocks of the integers. The reason 1 isn’t prime is that it’s useless and redundant as a building block.
Comment #32 February 17th, 2011 at 11:53 pm
Scott,
That is a plausible argument. I disagree that unique factorization would fail; the statement of unique factorization would be more involved.
I think the issue is somewhat like where you put the 2 pi in Fourier and Inverse Fourier transforms. You have to put it somewhere.
My view is that definitions should be as simple as possible, and let the theorems be as they turn out. So what if 1 is redundant as a building block. (Lately I have been working in a fairly new branch of applied math, and I think a lot about how definitions should be worded.)
Your view is presumably that the totality of the subject is simpler if 1 is not prime. Fair enough.
If someone wanted to argue this forever, they might find a theorem about odd integers that is not true for 1, and ask who is in favor of removing 1 from the odds as well. (I tried to copy and paste a smiley face here, but it didn’t fly. Or, it didn’t smile!)
Comment #33 February 18th, 2011 at 12:35 am
Raoul, so is -1 a prime in your universe? And what happens when we generalize other rings? Especially those lacking unique prime factorization?
The key issue is that number theorists in the mid/late 19th century found that everything was much easy to generalize if one never considered units to be prime.
Note that prime has a special meaning when generalizing to other rings. “Irreducible” is the term used for capturing our intuition for what we normally call “prime”. The issue is that when one is in a ring that doesn’t necessarily have some form of UPF then one can have an irreducible p (in the sense of it having no non-trivial factorization) but one doesn’t get p|ab implying p|a or p|b. So we define something to be irreducible if all factorizations have one element in the factorization as a unit, and we define primes to be those that don’t do the weird divisibility split above.
The rings that easiest to see that these really are the definitions we want are Z[i], Z[x], R[x], and Z[(-5)^(1/2)] (the pesky fellow who shows this breakdown).
There’s a related reason we don’t want 1 to be prime that has to do with the behavior of ideals, but discussing that would get us further afield.
Comment #34 February 18th, 2011 at 5:52 am
Great talk! Scott, you made the distinction at the end between things that look like science and philosophy. Can you explain a little more what is this distinction?
Comment #35 February 18th, 2011 at 10:10 am
Gil: To me, a “scientific advance in QM” should have the following characteristics.
– It contains a surprising new idea.
– It has new mathematical content, beyond that of QM itself.
– It immediately opens up a large number of answerable (but nontrivial) technical questions, for those who are interested.
– It suggests new ideas for doable experiments (even if the outcomes of those experiments could be predicted from standard QM).
– It doesn’t just consist of adding extra structure or complications to QM, without new evidence from experiment that such structure is needed. (Of course, if there is such evidence from experiment, then the advance automatically qualifies as spectacular.)
Three previous examples of advances that meet these requirements are
(1) Bell’s Theorem,
(2) quantum cryptography, and
(3) quantum computing.
By contrast, most interpretations of QM conspicuously don’t meet the requirements. (Bohmian mechanics and the many-worlds interpretation arguably meet some of the requirements but not others.) On the arXiv, almost every week there are papers trumpeting some big new advance in understanding QM that turns out not to meet any of the requirements.
Comment #36 February 18th, 2011 at 12:30 pm
“Well, consider a Turing machine M that enumerates all possible ZFC proofs, halting when it finds a proof of the inconsistency of ZFC. Suppose M has n states. Then if you knew BB(n), you could determine (presumably) that M doesn’t halt, and therefore that ZFC is consistent. So if ZFC proved the value of BB(n), then it would also prove its own consistency, which is impossible by the Second Incompleteness Theorem.”
Wrong. The absence of a proof of inconsistency is not the same as a proof of consistency. If I recall correctly, it is perfectly possible that ZFC is not consistent but also that there isn’t a finite proof of this fact.
Comment #37 February 18th, 2011 at 1:10 pm
Maxwell: If ZFC is inconsistent then there is a proof — you just have to call out the inconsistency.
Comment #38 February 18th, 2011 at 1:48 pm
Maxwell daemon: As anonymous says, you don’t recall correctly here! 🙂 “ZFC is inconsistent” means exactly the same thing as “ZFC proves 0=1,” which if true is a finitely checkable statement.
“ZFC is consistent,” by contrast, if true not only can lack a ZFC proof but must lack one.
Comment #39 February 18th, 2011 at 7:23 pm
Scott, many people would add our still-evolving understanding of BRST quantization (hep-th/0201124) to your list of scientific advances in QM … certainly these methods meet all your criteria.
BRST methods provide a geometrically natural answer to a question that Feynman was first to ask in 1964: “Why are ghost particles necessary?”, or more broadly, “How is it that quantum field dynamics simultaneously respects (non-Abelian) gauge invariance, informatic causality, spatial locality, and general relativity?”
Feynman never found good answers to these tightly-knit QM questions, and (so far) neither has anyone else … BRST quantization is merely our present best-guess as to how to (provisionally) lash these various aspects of QM together.
Perhaps not coincidentally, the architects of BRST quantization include some of the most prominent of today’s QM freethinkers (here t’Hooft particularly comes to mind). Moreover, fundamental QM issues aside, for purely practical reasons quantum systems engineers take keen a interest in these geometric methods, as hep-th/0201124 discusses.
The point is that advances in our informatic appreciation of QM (which you reviewed) are being paralleled by our advances in our geometric appreciation of QM (which hep-th/0201124 reviews). Obviously, we are at present still rather far from merging these two understandings … and certainly, it is conceivable that the result of that union will not look much like present conceptions of QM.
Comment #40 February 18th, 2011 at 7:29 pm
which is the BB(137)th bit in the binary expansion of \pi?
6
Comment #41 February 18th, 2011 at 7:29 pm
I mean 0…
Comment #42 February 19th, 2011 at 12:22 am
Joshua Z,
You introduce a new dimension to the “is 1 prime?” debate.
I had viewed the issue as “is ugly-ifying a key (and elegant) definition worth it to slightly simplify a lot of theorems?”. I vote “no”. A lot of people vote “yes”.
You consider the equivalent question in more general rings. This approach might influence my vote. I am a little weak in number theory and algebra, so I need to think about that for a while.
Checking out
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#CITEREFHardyWright1979
I note Theorem 1 of Hardy & Wright (1979): “Every positive integer, except 1, is a product of one or more primes.”. Thus Theorem 1 in the most famous number theory book in the universe would be simpler if 1 was prime.
A related note: I enjoy razzing G.H. Hardy, and also Paul Halmos, because they say things like “applied math is bad math”. That doesn’t mean I don’t buy their books, which are great. At a meeting around 1988, I got to point out to Halmos a mistake in the proof he was presenting. That was fun. Without think too hard, I would rate Halmos and Knuth as the best mathematical writers of all time. According to his Wikipedia page, Halmos invented “iff” and the “end of proof” symbol, ∎ (Unicode U+220E)
Comment #43 February 20th, 2011 at 12:02 pm
Scott, as in this talk, elsewhere I recall you stating that QM is just probability on (potentially negative) amplitudes, (I think it was about the p-norms or something I didn’t quite understand), are you aware of anyone teaching QM that way?
I’d be really interested to see that.
Comment #44 February 20th, 2011 at 12:13 pm
Cody: I saw some guy teaching it that way here, but I don’t know if it’s any good.
Comment #45 February 20th, 2011 at 1:45 pm
Ha ha, I suppose that might be where I’ve seen you mention it in the past. At some point I fell behind in those lectures, I think due to time constraints and growing difficulty with the material–maybe it’s time I return to them finally! (If I remember correctly those lectures were quite enjoyable.)
Thanks for the direct pointer!
Comment #46 February 21st, 2011 at 1:22 am
Two comments on the ZFC / BB thread:
Scott, you may want to be specific about what you mean by “proof” of a TM whose non-halting is equivalent to Con(ZFC). In systems stronger than ZFC, we know ZFC is consistent, so any TM that doesn’t terminate satisfies your challenge! I assume you probably want to work over Peano Arithmetic or a even weaker system 🙂
Maxwell Daemon, as Scott says, if a system is inconsistent than there is a finite proof demonstrating this. I think what you’re thinking is that it’s possible for a system to be consistent but *untrue*. (By which I mean technically, omega-inconsistent or arithmetically unsound.) For example, it’s possible to have a consistent system that for all X proves “P(X)”, but also proves “there exists X such that not(P(X))” (note the quotes separating the meta-math from the statement in the system).
Comment #47 February 21st, 2011 at 10:35 am
Luke: Yeah, I meant a ZFC proof. Assuming Con(ZFC) is out of bounds. 🙂
Comment #48 February 22nd, 2011 at 12:05 pm
Raoul: what about the simple definition
“An integer is prime iff it has exactly two positive divisors”
and Theorem 1 of Hardy & Wright stated as
“Every positive integer is a product of zero or more primes” ?
Comment #49 February 22nd, 2011 at 3:49 pm
Raoul:
I think your conception of what’s “elegant” and “simple” is being obscured by the ineffective usage of language in the theorems and definitions. I note that you have no problem with the “positive” requirement in Theorem 1 of Hardy & Wright, but find “except 1” ugly. But if you consider that “positive” is the same as “natural, except 0”, then adding an “except 1” doesn’t seem too ugly anymore.
Following that line of reasoning, one could create a name for “natural, except 0 or 1”, say, “nezo” (Natural Except Zero or One). Then the definition of prime would not be seem too ugly anymore: “A number is prime if it has exactly one nezo divisor (itself)”. Theorem 1 of Hardy & Wright would be similarly simplified: “Every nezo is a product of one or more primes”.
If the idea of creating a new name for “natural, except 0 or 1” seems contrived, consider this: 0 and 1 they aren’t interesting when thinking about divisibility, because you can’t divide any number by 0, and you can divide _any_ number by 1. So, it seems likely that people have this “nezo” concept while thinking about divisibility and primes, even if they don’t explicitly name it. Maybe the failure to name it explicitly is what makes the definitions and theorems seem ugly, even though they contain beautiful and simple concepts.
Comment #50 February 22nd, 2011 at 5:00 pm
Scott: I stand corrected. After a somewhat long research I did recall what I wasn’t recalling correctly. It turns out it was a paper of yours: “Is P Versus NP Formally Independent?” http://www.scottaaronson.com/papers/pnp.pdf
Specifically, when you said that Con(ZF) implies Con(ZF + ¬Con(ZF)), and thus that ZF+¬Con(ZF) can not be trapped in an inconsistency, I thought that you had produced an example of an inconsistent theory without a finite proof of it.
But the fact that ¬Con(ZF) is false only means that the theory is lying, not that it is inconsistent. Is this it?
(Luke: at first I did not have in mind consistent but untrue, but now I think that’s the case)
But I’m still uncomfortable with your statement. Wasn’t that a Holy Grail of mathematical logic? A finitary (albeit very large) statement that is actually independent of ZF(C)? After all, until now there were only examples of problems that involved silly infinities, and those can be regarded as a curiosity at best.
Or that would just mean that the provability of BB(137) is equivalent to consistency, and thus not being bona fide independence?
Comment #51 February 22nd, 2011 at 5:28 pm
Maxwell daemon:
But the fact that ¬Con(ZF) is false only means that the theory is lying, not that it is inconsistent.
Exactly. Consistency doesn’t imply soundness, which is a stronger property.
But I’m still uncomfortable with your statement. Wasn’t that a Holy Grail of mathematical logic? A finitary (albeit very large) statement that is actually independent of ZF(C)?
Well, the Gödel sentences have always provided examples of “finitary statements” that are independent of ZFC. But many mathematicians consider those “unnatural,” since in “everyday” math we don’t typically ask metaquestions about the consistency of the theory we’re working in. So it’s an interesting challenge to find a finitary statement that arose independently from logic, computability theory, etc., which can nevertheless be proven independent of ZFC.
(We do have such examples for Peano Arithmetic, and we also have nonfinitary statements like the Continuum Hypothesis that are independent of ZFC.)
Now, I do not regard the values of BB(n) for large n as answering this challenge, for two reasons:
(1) The values of BB(n) in question can’t even be written down inside the observable universe! So evaluating them isn’t a “math problem” in the ordinary sense of something that a human (or at least computer) could feasibly check the answer to.
(2) The values of BB(n) are not something that mathematicians would think to study outside of logic / computability theory — which might be related to the facts that BB is uncomputable, and that BB(n) for large enough n encodes Con(ZFC)! 🙂
Comment #52 February 24th, 2011 at 9:31 pm
re: The spirit of Feynman’s challenge
Lots of you will enjoy this: http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-would-feynman-do.aspx
Comment #53 February 24th, 2011 at 10:34 pm
Great talk Scott… I wish you just reduce your oscillating frequency, you move a lot man! 🙂
greatly enjoyed the talk and the jokes. BTW, 1 is not a prime number (….. okay, now you can stop banging your head against the wall :D)