Ask Me Anything: Diversity Edition

With the fall semester imminent, and by popular request, I figured I’d do another Ask Me Anything (see here for the previous editions). This one has a special focus: I’m looking for questions from readers who consider themselves members of groups that have historically been underrepresented in the Shtetl-Optimized comments section. Besides the “obvious”—e.g., women and underrepresented ethnic groups—other examples might include children, traditionally religious people, jocks, liberal-arts majors… (but any group that includes John Sidles is probably not an example). If I left out your group, please go ahead and bring it to my and your fellow readers’ attention!

My overriding ideal in life—what is to me as Communism was to Lenin, as Frosted Flakes are to Tony the Tiger—is people of every background coming together to discover and debate universal truths that transcend their backgrounds. So few things have ever stung me more than accusations of being a closed-minded ivory-tower elitist white male nerd etc. etc. Anyway, to anyone who’s ever felt excluded here for whatever reason, I hope this AMA will be taken as a small token of goodwill.

Similar rules apply as to my previous AMAs:

Only one question per person.
No multi-part questions, or questions that require me to read a document or watch a video and then comment on it.
Questions need not have anything to do with your underrepresented group (though they could). Math, science, futurology, academic career advice, etc. are all fine. But please be courteous; anything gratuitously nosy or hostile will be left in the moderation queue.
I’ll stop taking further questions most likely after 24 hours (I’ll post a warning before closing the thread).

Update (Sep. 6): For anyone from the Boston area, or planning to visit it, I have an important piece of advice. Do not ever, under any circumstances, attempt to visit Walden Pond, and tell everyone you know to stay away. After we spent 40 minutes driving there with a toddler, the warden literally screamed at us to go away, that the park was at capacity. It wasn’t an issue of parking: even if we’d parked elsewhere, we just couldn’t go. Exceptions were made for the people in front of us, but not for us, the ones with the 2-year-old who’d been promised her weekend outing would be to meet her best friend at Walden Pond. It’s strangely fitting that what for Thoreau was a place of quiet contemplation, is today purely a site of overcrowding and frustration.

Another Update: OK, no new questions please, only comments on existing questions! I’ll deal with the backlog later today. Thanks to everyone who contributed.

This entry was posted on Saturday, September 5th, 2015 at 2:05 pm and is filed under Ask Me Anything. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

185 Responses to “Ask Me Anything: Diversity Edition”

Hanan Cohen Says:
Comment #1 September 5th, 2015 at 2:49 pm
I am studying to be a Librarian. (I think we under-represented here).

How do you think quantum computing might change libraries and librarianship?
Orin Says:
Comment #2 September 5th, 2015 at 2:56 pm
From your wonderful “The Ghost in the Quantum Turing Machine” I didn’t find your examples of indexical paradoxes compelling. For example, in the “experimenter flips a fair coin and depending on the result you are copied into a 1000 identical rooms” example, you assert that the result is so counterintuitive as to constitute a paradox, however I have never related to this. It has always seemed perfectly natural and non-paradoxical that the odds are 1000:1 rather than 50/50. This is immediately seen in a practical frequentist sense that if you were to enroll in this experiment you would be irrational to bet on anything but the unfair odds. The scenario is functionally equivalent from the perspective of any subject of the coin not being fair. I’m wondering if you could comment on this example, because I found the other “paradoxes” you presented to be analogous, and as a result wasn’t persuaded to your way of thinking. There just don’t seem to be any paradoxes here at all, just maybe a failure of intuition or imagination in some people, or maybe rather a mistaken theory of personal identity (ie that clones are p-zombies or something). Thanks.
Oleg S Says:
Comment #3 September 5th, 2015 at 3:07 pm
Do you think quantum computers will have significant advantage over the classical ones for practical simulation of the human brain?
SkepticalAboutSocialJustice Says:
Comment #4 September 5th, 2015 at 3:08 pm
Is Laurie Penny still planning to contribute to a piece on this site about shy female nerds, or has that been abandoned?
Scott Says:
Comment #5 September 5th, 2015 at 3:08 pm
Hanan #1: I eagerly look forward to the day when people regularly borrow quantum states from their local library, and then on returning the states, are charged a fee depending on how destructive the measurements were that they made. (Unlike books, movies, etc., quantum states can be fundamentally unclonable, meaning that it could actually matter into the indefinite future how many copies of a given resource state the library had on hand. But by using amplification, one should be able to let library patrons learn something useful from a state, by making a measurement that damages the state by only an exponentially small amount. So in principle, the same state could be checked out of the quantum library exponentially many times—though in practice it would probably succumb to vandalism or environmental decoherence much much sooner.)

More seriously, libraries have changed pretty dramatically even just in my lifetime, from book repositories with card catalogs to places to go online, grab a coffee, and take the toddlers to storytime. I expect that they’ll continue to change, but still for reasons having much more to do with classical than with quantum computing.
Scott Says:
Comment #6 September 5th, 2015 at 3:26 pm
Oleg #3: If the simulation of the brain is at the neural level or higher, then it’s far from obvious where a QC would give you an advantage—maybe you could use the adiabatic algorithm instead of backprop to optimize the synapse weights? (But we couldn’t tell you today how much speedup, if any, you’d actually get that way.) We know that a QC doesn’t much help for evaluating a threshold function, unless the threshold is close to its minimum or maximum values (like the AND or OR functions, but not like the MAJORITY function).

If, on the other hand, you were trying to simulate the detailed molecular structure—the proteins inside a neuron, the sodium-ion channels, etc.—then it’s very easy to believe that a QC would help. But from the standpoint of today’s neuroscience, it’s not so easy to pinpoint why you’d need to go down to that level in order to reproduce what’s important about cognition. If you believed the Penrose-Hameroff “Orch-OR” theory, then of course you would need to go down to that level—but keep in mind, Penrose and Hameroff also believe that there are uncomputable quantum-gravity effects there, which not even a QC could simulate! So, the case where QCs seem most likely to be of game-changing importance in simulating the brain, is the case where quantum-level effects turn out to be vastly more important than conventional neuroscience says they are, but Penrose and Hameroff are also wrong.
Gene Chase Says:
Comment #7 September 5th, 2015 at 3:26 pm
Do you regard consciousness as emergent behavior? [I’m an under-represented minority conservative Christian who thinks that consciousness is God-given.]

I know in QCSD you say “granting consciousness to a robot seems strangely equivalent to denying that one is conscious oneself.” (p 41). You say that consciousness as emergent behavior perhaps is a “reductionist’s dream” (p. 53). Your dream? You say that there is a temptation to say that because QM is mysterious, it must have a part someday in explaining consciousness (p. 157).

BTW, I’ve been a lurker here for years, outclassed by those who contribute / argue here. I’m an MIT Math grad, 1965. I enjoyed your QCSD immensely, and this week assigned reading Chapter 9 to one of my honors students, a double major in Math & Physics, who is studying Complex Analysis independently with me because after taking a course in QM, he realized that he needed Complex Analysis. Chapter 9 is BEAUTIFUL.
Scott Says:
Comment #8 September 5th, 2015 at 3:31 pm
SkepticalAboutSocialJustice #4: No, Penny and I never abandoned that idea (which morphed into a general “advice for shy nerds” post)! But she’s moved back to London, and the ball’s probably in my court to get it started, and as often happens, my promising to do something was a “kiss of death” that ensured months of procrastination. We’ll do it eventually—sorry for the delay.
Thomas Says:
Comment #9 September 5th, 2015 at 3:40 pm
Do you, by any chance, have something to remark about depression, besides the “usual” (it’s terrible, it’s an illness etc.)? And it’s perfectly fine to say “no”.
wolfgang Says:
Comment #10 September 5th, 2015 at 3:53 pm
In March Maldacena et al. published a paper about a fundamental limit on the rate of growth of chaos in complex systems.
I remember that I asked you if this would imply limits on a quantum computer, but I don’t remember an answer; so let me use this opportunity to ask again.
Scott Says:
Comment #11 September 5th, 2015 at 3:54 pm
Gene #7: I regard the nature of consciousness as one of the great “vertiginous questions,” like why the universe exists, the asking of which in every generation is part of what makes us thinking beings, and which are entitled to respect on that count—even if we can’t point to any research program that seems to have any hope of making progress on these questions.

If someone is certain that consciousness is not emergent, then I try to remind that person how you can change someone’s personality in predictable ways by knocking out specific brain regions; and how current scientific understanding seems to present no obstacle whatsoever to building an AI that would invent all the same arguments for its having a God-given soul that humans have invented for why we do; and the laughable absurdity of nearly every concrete proposal for how a soul could influence the physical brain, and all the other standard arguments for Dennett-style eliminative materialism.

If, on the other hand, someone is certain that consciousness is emergent, then I ask that person the usual chestnuts about whether they would agree to be painlessly euthanized, if promised that their brain would then be perfectly simulated on a computer; and exactly what counts for this purpose as “running the simulation”; whether they’d be content to live on as patterns on construction paper, or as a giant lookup table caching their responses to every possible question; whether it matters if anyone actually consults the lookup table, etc.

Either way, if I succeed in making the person doubt whatever conviction they started with, even if just for a second, I feel like I’ve discharged whatever wisdom I have to offer about these things. If they want more wisdom, I send them to read one of my favorite novels of all time, The Mind-Body Problem by Rebecca Newberger Goldstein.
Scott Says:
Comment #12 September 5th, 2015 at 4:03 pm
Orin #2: So then, would you agree that the following approach would “work” to win the lottery? Build a machine that picks one of the million possible numbers at random, and that creates a billion copies of you if the number happens to be the jackpot. The overwhelming majority of copies of you will find themselves in the jackpot-world. (We’ll assume you’re so altruistic toward your doppelgangers, that you don’t mind if only “one” of them gets to enjoy the jackpot.) There’s nothing counterintuitive, in your mind, about the ability to manipulate probabilities like this? (Note that a similar trick could be used to solve NP-complete problems, or really any time you’re facing a difficult decision.)

(On the other hand, I’ve often wondered whether the indexicality section should’ve simply been omitted from GIQTM, since people’s intuitions do wildly diverge about these matters, and I think most of the rest of the essay stands without that section.)
Scott Says:
Comment #13 September 5th, 2015 at 4:11 pm
Thomas #9: The most perceptive things I’ve read about depression in the last year have almost all been on the other Scott A.’s blog. I’d strongly recommend his writings about cognitive behavioral therapy, the relative effectiveness of various antidepressants (including unusual foreign ones), etc., even if he weren’t an actual psychiatrist in his day job.
Scott Says:
Comment #14 September 5th, 2015 at 4:38 pm
wolfgang #10: I dug up our email exchange, and the meat of my response was this:
So, while it looks like an interesting paper, and it might turn out to have implications for QC, my answer would be no, I don’t see right now why it would imply any new limit on QC.
Andre Says:
Comment #15 September 5th, 2015 at 6:00 pm
What are your thoughts on using tools from statistical physics to approach problems in complexity theory?
Tony Says:
Comment #16 September 5th, 2015 at 6:03 pm
Yesterday I was bored at work and I wrote a simple Python program that tries to find a formula for a given numbers series. So, you give 2,4,8,16,32 and the program will generate millions of random math formulas and return the one that matches the series: in this case 2^n
I tried many integers series and it was really quick finding the right formula. Then I tried the first 10 prime numbers and after 3 billion formulas I stopped without success, hehe. Do you know of any large scale project similar to this to get formulas by brute force?
Garrett Says:
Comment #17 September 5th, 2015 at 6:13 pm
When are you going to come out to the Pacific Science Institute in Maui and learn to surf?

(I’m guessing surfers are an underrepresented minority here. But we’re not bitter about it.)
Scott Says:
Comment #18 September 5th, 2015 at 6:28 pm
Andre #15:
All for it! There have been major victories over the last decade in rigorously understanding (e.g.) the phase transitions and structure of the solution set in random k-SAT. Now, it’s fair to say that very little of the progress on these statistical physics questions, has led to progress on complexity-theory questions that don’t themselves have a “statistical physics flavor.” But some of the work of Allan Sly might be a partial exception to that, and we can hope for more exceptions in the future.
Scott Says:
Comment #19 September 5th, 2015 at 6:30 pm
Tony #16: The Encyclopedia of Integer Sequences.
Scott Says:
Comment #20 September 5th, 2015 at 6:32 pm
Garrett #17:
I can’t wait to visit Maui! How does next summer look?
Nicholas K. Zieve Says:
Comment #21 September 5th, 2015 at 6:49 pm
Hi Scott,

My dad suggested that I would count as underrepresented… As a member of the food service industry, what’s your opinion on the balance between food waste, food safety, public perceptions, and associated cost-benefit ratios?

Darn it, I have another question. Well, maybe next time.
Daniel Seita Says:
Comment #22 September 5th, 2015 at 6:50 pm
Do you support the Iran nuclear deal?
Female Professor Says:
Comment #23 September 5th, 2015 at 6:59 pm
How do you think gender bias play in the role of academic hiring especially in computer science? If a university makes a spousal hire under pressure (e.g. when other person has another job offer) what kind of complications may the spouse face in the departments after joining? What is your general advice on job searching/re-searching for academic couples?
James Gallagher Says:
Comment #24 September 5th, 2015 at 7:10 pm
Are there any non-trivial quantum processes in biology?
Scott Says:
Comment #25 September 5th, 2015 at 7:39 pm
Daniel #22:
I’d say the truth is that no one, on either side, really knows yet whether this deal is good or not, and anyone who feels absolutely certain on ideological grounds is fooling themselves. We’ll find out the truth in a decade or so, and then (whatever it is) it will be obvious in retrospect.

I’m naturally thrilled for my Iranian friends and colleagues, many of whom despise the Ayatollahs as much as I do (but no one asked them their opinion…), and who can finally envision a reasonable future for their country. And we can all hope that the coming liberalization of Iran’s economy leads eventually to a successful reprise of the 2009 uprising, rather than simply to more wealth for the Ayatollahs.

On the other hand, it’s certainly a striking feature of the deal, as I understand it, that the Iranian government can continue to do essentially anything it wants besides enriching too much uranium—e.g. building ICBMs, giving long-range missiles to Hezbollah to fire at Israel, killing Israelis and non-Israeli Jews in terrorist attacks around the world (through its proxies)—without the possibility of a return of sanctions. To put it differently: Iran can still do things such that, conditioned on its doing them, it would pretty obviously also be building nuclear weapons to whatever extent it could do so without getting caught—yet even catching Iran doing those other things won’t trigger a return of sanctions.

So maybe there’s something to be said for the argument that, while even a bad deal might be preferable to a war, the US should’ve held out for a better deal.

In the end, though, the deciding consideration for me—and I’m embarrassed to admit I don’t have a better one—is that I respect the competence of President Obama and the people working for him, particularly Ernest Moniz. And I believe them that, if there were a feasible way to get a better deal, then they would’ve figured it out, and that the people Monday-morning quarterbacking them simply don’t know all the relevant facts. On that ground, I nervously, reluctantly support the historic gamble that the President I voted for has taken.
Bob Strauss Says:
Comment #26 September 5th, 2015 at 7:45 pm
Hi, Scott, I’m a general-interest science writer (I run the dinosaurs site at about.com) and avid reader (yes, my library includes Quantum Computing Since Democritus, which is great except for the vast impenetrable thickets of math that defy all my attempts at comprehension, yet which I continue to read and reread in the vain hope that some sort of enlightenment will penetrate my skull). My question is: What is your gut feeling about the existence, or nonexistence, of intelligent alien civilizations? Are we alone in the universe, and if not, why haven’t we heard from anybody? Or more concisely, what’s your view of the Fermi Paradox?
Yitzhak Zaradsky Says:
Comment #27 September 5th, 2015 at 7:56 pm
Do you think that the USA is a police state (or is turning into one)?

Great initiative by the way. Thanks Scott.
Scott Says:
Comment #28 September 5th, 2015 at 7:58 pm
Nicholas #21:
My guess would be that restaurants do throw away too much food—in the sense that, if we could “go full Asperger’s” on the problem, minimizing waste and maximizing safety with no consideration given to existing regulations or social niceties, we’d find tons of low-hanging fruit here. (Or rather: fruit on the ground that’s still perfectly good to eat? 😉 ) One obvious step would be smaller portion sizes (or at least, more choice of portion sizes); another would be greater use of digital ordering systems to minimize botched orders that then need to be thrown away and replaced. But I don’t want to pontificate more about this, since I have zero experience in the food-service industry. Readers with actual knowledge of these matters are welcome to chime in.

(Incidentally, I hope I didn’t offend anyone with the phrase “going full Aspberger’s”—if it wasn’t clear from context, I mean it as a term of high praise.)
Scott Says:
Comment #29 September 5th, 2015 at 8:00 pm
James #23:
Yes. The FMO complex in photosynthesis and the internal compasses of European robins are two well-known examples.
James Gallagher Says:
Comment #30 September 5th, 2015 at 8:14 pm
THAT’s not what I meant. I want YOU to say whether you BELIEVE these phenomena to be true macroscopic quantum processes at high temperature. Max Tegmark posted a well regarded paper at the end of the last century arguing that the brain was too warm and wet for anything quantum to be possible.

So, seriously, what is your gut feeling about quantum biology?

(My feeling is that slighly less able people in biolgical sciences are interpreting their data badly compared to the more clever guys and gals in pure physics)
Scott Says:
Comment #31 September 5th, 2015 at 8:21 pm
Bob #26:
I like to tell people that my favorite solution to the Fermi Paradox—much less macabre than “all the aliens killed themselves out in nuclear wars”—is, “once a civilization reaches a certain stage of development, its inhabitants choose to spend all their time thereafter playing video games, and completely lose interest in the physical world.” 🙂

The truth, of course, is that we have no idea. And as Carl Sagan once said, it’s excellent epistemic practice, in situations of such massive uncertainty, to learn not to think with one’s gut. We do know that unicellular life arose remarkably quickly in the history of the earth, whereas intelligent life took billions of years longer. And we know that life did arise on the one body in our solar system whose temperature seems hospitable to life (at least from our limited perspective), and that there must exist trillions of other planets whose temperatures are similarly hospitable. So, does that suggest that life is common but intelligent life is rare? Alas, we can’t even say that with any confidence. If we had even one other case study of life arising—for example, on Mars—that would already be enough to start thinking about it like Bayesians and plugging some numbers into the Drake equation. But our actual situation is that we have only the one case study (earth), and it’s hopelessly contaminated by selection bias.
Scott Says:
Comment #32 September 5th, 2015 at 8:33 pm
James #30: Yes, these are real, nontrivial quantum-mechanical processes—and I don’t think anyone knowledgeable disputes that, including Max Tegmark. (The paper of his you reference was about the speculation that large-scale quantum coherence could be relevant to the brain—it had nothing to do with these lower-level biological processes.)

No, the processes I mentioned are not “macroscopic,” for reasonable definition of that term. But your question didn’t specify macroscopic!

To sum up: there’s no serious dispute that, at a microscopic scale, biology sometimes exploits quantum effects in remarkably clever ways. But, as Tegmark pointed out, there appear to be massive obstacles to quantum mechanics playing a more macroscopic role in biology.

And from now on, a clarification: “one question per person” also means “no followup questions.” Sorry, these things take a lot of time. 🙂
Ian Says:
Comment #33 September 5th, 2015 at 8:36 pm
Sorry to bring up DWave but …

I was wondering if you could imagine and then articulate some reasonable rationales for why people work at DWave systems, aside from those involving the engineering challenges being worthwhile in and of themselves.

I’m guessing the majority of people working there are smart, thoughtful, and informed. Since all the evidence to date seems to indicate that there really is likely to be no practical value of the system whatsoever, either now or in the future, what do you imagine they tell themselves to stay motivated?

Do they know something we don’t?
Scott Says:
Comment #34 September 5th, 2015 at 8:54 pm
Female Professor #23: You ask three extremely complicated questions! To keep things manageable, let me tackle only one of them:
I hesitate to offer advice—me, the fount of wisdom about such things!—but I guess I do have one thing to say. That’s that you should clarify the status of your relationship before going on the job market together. For some couples, that might mean getting engaged; for others it might mean something different. But you should resist the temptation to “let the job market sort out your love life for you,” using offers at the same place as a way of committing to each other or offers at different places as a way of breaking up. One reason, of course, is that presumably no one wants to feel like their life partner is only staying with them out of professional convenience. But a second reason is that, if you do decide to go on the market together, then it helps if you can clearly explain to prospective employers that you’re a package deal, with no hedging or waffling of any kind. I.e., that as far as they’re concerned, you might as well be one person that does twice the teaching and research for twice the salary in twice the office space, and they can either take or leave that mega-person.
Bob Strauss Says:
Comment #35 September 5th, 2015 at 8:59 pm
Scott #31, not a followup question, just a comment. My feeling is that advanced civilizations, if they exist, would be using a communications system of which we can’t even conceive, and (for all we know) may even be operating on a nano scale of technology that renders them essentially invisible. My problem with the Fermi Paradox is that it seems foolish to base our assumptions about the existence or nonexistence of other civilizations on our present level of technology, which is still, assuming an indefinite future, in the Stone Age.

Thanks for answering, and I love your blog!

Bob
Scott Says:
Comment #36 September 5th, 2015 at 9:05 pm
Ian #33:
If you take a broader view than just D-Wave, then I don’t think there’s any great mystery here that needs solving. Like, do you have any idea how many hundreds of thousands of talented people work at startups most of which will fail? Some of them do so because they genuinely believe in the startup, or because they’re emotionally committed, having already invested so much. Others might take a more jaundiced view, but reason: hey, we’re accumulating patents and paving the way for others who will come after us (two activities admittedly in some tension 🙂 ), and in the meantime, I’m having fun and drawing a salary. And even if the project as a whole fails—or “works,” but is no better than simpler existing solutions, etc.—well, my piece of the project (which is what I spend all my time thinking about) is going to be awesome!
Tristram Says:
Comment #37 September 5th, 2015 at 9:10 pm
I’m a mathematician teaching a course in complexity theory using Arora-Barak (most of section 1) and parts of Garey-Johnson. What ideas would a computer scientist consider important in such a course that I might not emphasize enough?
Scott Says:
Comment #38 September 5th, 2015 at 9:21 pm
Bob #35: So, if there are billions of civilizations out there, with different origins, technologies, ethical systems, etc., you’re willing to believe that not one of them is interested in contacting just-emerging civilizations via radio (which it would know would be likelier to succeed than Zorkian voodoo-waves)?

The truth, I’d say, is that our failure to detect any alien radio signals (or engineered solar systems, etc.) does put an upper bound on either the number of advanced civilizations or on their diversity, and that bound is orders of magnitude more stringent than if we hadn’t looked. On the other hand, because 10²² stars is quite a large number, the bound is still consistent with there being many advanced civilizations of diverse kinds in our observable universe.
Scott Says:
Comment #39 September 5th, 2015 at 9:26 pm
Tristram #37:
Hmm … the pervasiveness of universality? The non-obviousness of so many different-looking problems turning out to be polynomial-time equivalent, the ease with which it “could’ve been otherwise”? The irrelevance, for most purposes, of the low-level encoding details—the fact that notions like computation and polynomial time have an autonomous mathematical reality to them, independent of Boolean circuits or Turing machines or the other technical devices that we use to formalize those notions?
Jay Says:
Comment #40 September 5th, 2015 at 9:55 pm
Do you think Watson™ qualifies as processing semantic? Deep learning?

[I’m an under-represented minority conservative Pastafariam who thinks that consciousness is Pasta-given]
[those who pretend we’re a majority on this blog or I just asked two questions are evils]
Alex B. Aible Says:
Comment #41 September 5th, 2015 at 10:25 pm
Hi Scott,

I remember reading a post by you a long time ago in which you stated that Cantor’s Diagonalization Argument was one of your favorite “proofs.” While recognizing that I am the “merest of amateurs,” his Argument has always been incomprehensible to me. (In fact, I bought QCSD but when I ran into your account of “professional infinity,” I could not continue.) I consider combinatorics to be an incontrovertible science, so if you would point out the flaw in the following six-line summary of the “Diagonalization Counterargument,” I would be filled with such peace, I could return to my QCSD.

1. The complete set of distinct binary numbers $p$ of length $n$ can only be contained in a $2^n$ by $n$ matrix.

2. The rows of such a $2^n$ by $n$ matrix can be arranged in any linear order, so there exists a set $O$ of such arrangements that contains $2^n$! distinct members.

3. There can only be a diagonal of length $n$ in an $n$ by $n$ matrix.

4. Every $n$ by $n$ matrix that contains $n$ of the given $p$ must be a component of a non-empty proper subset of the members of $O$.

5. It is not possible to formulate a valid thesis about the consequences of flipping the diagonal of an $n$ by $n$ matrix that contains $n$ of the given $p$ unless we assume we are flipping this diagonal when the $n$ by $n$ matrix is a component of a member of $O$.

6. If we flip the diagonal of any $n$ by $n$ component of any member of $O$, we corrupt this member of $O$ by reducing the number of distinct $p$ it contains.

Many thanks,

Alex Aible
Scott Says:
Comment #42 September 5th, 2015 at 10:29 pm
Yitzhak #27:
It’s hard for me to pinpoint what actual question of fact is at issue here—other than what emotional attitude one is trying to convey to listeners about the US or its government.

On the one hand, yes, the Snowden documents show that the NSA has been doing way more mass surveillance than is healthy in a democracy. And in a separate development, the rise of militant political correctness—as enforced by social-media lynch mobs—has meant that, while the First Amendment is still on the books, you can’t have a normal career if you venture outside a remarkably narrow range of allowed opinions. If you consider the great public intellectuals of the past, from anywhere on the political spectrum—Mark Twain, Bertrand Russell, George Orwell—and you read what kind of stuff they were willing to write, it seems obvious that none of them could survive a day in the age of Twitter. So yes, that worries me.

On the other hand, if you ask: is the US a police state in the sense that the USSR was a police state, in the sense that North Korea is?—then the answer is an obvious, unequivocal “no.”
Scott Says:
Comment #43 September 5th, 2015 at 10:34 pm
Jay #40:
Sorry, this is yet another one of those questions about words, where I have a hard time pinpointing the actual thing at issue. It seems much more interesting to me to ask what Watson does, how it does it, and what it doesn’t do, than how to classify it in some AI taxonomy.
Futurist Says:
Comment #44 September 5th, 2015 at 10:41 pm
Isn’t there an alternative to your freebit theory of freewill?

Instead of pixie dust from the big bang sprinkled into brains (?!?), what about the two-state formalism of quantum mechanics? There’s the ket state describing the big bang with no pixie dust, and a bra state at the end of time controlled by some “superagent” with “freewill”. If historical records of some 21st century human were to survive until the end of time, this “superagent” can use Its “freewill” to adjust Its bra to pick out a particular life history for this human. This human would be under the delusion of operating under its own freewill but is really a puppet controlled retrocausally by puppetmaster strings according to the “freewill” of this “superagent”.

This could also explain the collapse of the wavefunction. The ket never collapses. Its the bra operating retrocausally which is responsible for all the collapses.

This is something like the plot of the novel “Timelike infinity” by Stephen Baxter describing the religion of the “Friends of Wigner”, except that history can’t actually be changed because the final bra is always fixed once and for all (in pseudotime? out of time?) .

What are the flaws of this metaphysical philosophy?
Scott Says:
Comment #45 September 5th, 2015 at 10:47 pm
Alex #41: I agree with your statements 1-4, and don’t understand your statements 5 and 6. But more to the point, I fail to understand how any of this constitutes a “counterargument” to Cantor’s diagonal proof. Like, why are any of these points even relevant to the diagonal proof? Yes, for any finite n, it’s possible to list all the n-bit binary numbers (the list has size 2ⁿ, as you pointed out)—but the list of all infinity-bit binary numbers (i.e., real numbers in [0,1]) isn’t even denumerably infinite; that’s what Cantor’s proof shows. You’d do better to engage with the actual diagonal proof and identify which step you don’t agree with.

Though the truth is that, once you see it, you can barely even break it into “steps”—all Cantor’s proof is saying is that, if you made a denumerable list of integer sequences S₁,S₂,… then of course you could straightforwardly construct a new sequence S that’s not in the list, by choosing S to differ from each S_i in one place. Like, how could that not be the case? It’s not a question of arguments and counterarguments; you either see it or you don’t.
Me Says:
Comment #46 September 5th, 2015 at 11:04 pm
As a layperson who occasionally likes to do some (recreational) “research”, i often experience the problem of rather than making a formal mistake, examining a very complicated and interesting looking structure which later turns out to be a completely trivial fact in disguise. Does this happen to professional mathematicians as well and if so, how can you make sure a new idea or a new angle of view of has any substance behind it?
Silva Says:
Comment #47 September 5th, 2015 at 11:05 pm
Hi Scott, I was born and live in a developing country (Brazil), so I guess I am eligible, but my question has nothing to do with it.

In your QCSD you said “Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p, which is a real number in the unit interval [0,1]. That’s randomness.”

I am also simpleminded, but since this is a AMA I can’t help asking: What is this real number p referring to into the physical world?

Of course, quantumly a complex number (amplitude) refers to something that has a physical bearing. Sure nature keep this number to herself, but there seems to be a physical “thing” out there that gives us randomness. So in the end what I am asking is if there is a one-to-one correspondence from p to something in nature, or this kind of model of randomness is just an useful approximation when we do not have enough information about a system, since in the end there is only quantum randomness?
The Ultimate Reductionist Says:
Comment #48 September 5th, 2015 at 11:13 pm
How would you deal with internet trolls who viciously fanatically agree with me on one issue but disagree just as viciously fanatically on another?

Off the top of my head example:
internet trolls who agree that bankers throughout the world are destroying the world’s economy by printing money, but giving it only to themselves, but buying up real physical wealth & services with that fraudulent money, & who agree with me that we need to go to war against these financial terrorists just like war against ISIS

but then who launch into some idiotic Israel-blaming Jew-blaming Zionist-obsessed rant?

RT News YouTube channel is full of them.

I’m just an atheist with a brain (I hope).
Jonathan Paulson Says:
Comment #49 September 5th, 2015 at 11:16 pm
Can you give some non-geometric intuition for Grover’s algorithm? In particular, how does the classical proof that you need O(n) queries (i.e. you might have to look at every index of the array) “go wrong” in the quantum mechanical setting?
Annon Says:
Comment #50 September 5th, 2015 at 11:35 pm
Scott,
I have an acute learning disability, particularly related to symbolic reasoning(dyslexia/dysgraphia), I score below 5% on such tests, and in the 99.99% on others. I have very strong visualization skills, strong verbal abilities, but letters swim by me like so many minnows in the sea!
I’ve managed to work my way into a phd in CS, but my LD can be a scourge to many my professors that I deeply admire and I hoped to learn from(we share many mutual acquaintances, several of whom you hold in high esteem).
I’ve managed to secure my position, am academically on track and am productive, but frankly that’s far my original objectives.
My question is simple: How would you recommend to learn mathematics if you could not read or write?
Alex B. Aible Says:
Comment #51 September 6th, 2015 at 12:11 am
Scott #45: What is it about statements 5 and 6 that you don’t understand? The counterargument does indeed recognize that you can “straightforwardly construct a new sequence S that is not on the list…” but it points out that any time you do this, you unavoidably reduce the number of S in the $2^n$ matrix which contains the $n$ by $n$ matrix (by creating a redundant S) so that the “diagonalization argument” is (at best) meaningless.

Thanks,

Alex
Amin Says:
Comment #52 September 6th, 2015 at 12:42 am
What sounds like a reasonable resolution to the Israeli-Palestinian conflict, from where we stand right now?
Quin Says:
Comment #53 September 6th, 2015 at 1:00 am
Hello Scott. I have a question regarding the Turing halting problem. I understand that if you have a machine that either halts when the code should go on forever, or goes on forever whenever the code halts, but why could we not create a program that halts whenever the code has the potential to go on forever, and goes on forever whenever the code definitely halts? As in, why can’t we classify codes that sometimes do one thing and sometimes the other under one the halting or non-halting outcomes? Also, wouldn’t the halting problem also suggest that it would be impossible to create any code that has the ability to both halt and go on forever with different inputs? I’m almost definitely misinterpreting some part of the problem, but I’m wondering why we can’t simply rephrase the initial question to allow for these kind of programs.
Ajit R. Jadhav Says:
Comment #54 September 6th, 2015 at 1:48 am
Scott,

I will ask you more than one question. Take any one of them; we will save the rest for the next edition of AMA.

1. If you like to listen to music, what kind is it? Any concrete examples?

2. Do you do any regular physical exercises (apart from lecturing in a hall)? Which ones?

3. If you were to be an engineer of one of the three old or traditional branches, viz. civil, mechanical, and electrical (as in electrical power, not electronics)), what field(s)/topic(s) you think might have interested you more than others?

Best,

–Ajit
[E&OE]
Rahul Says:
Comment #55 September 6th, 2015 at 2:02 am
Mitchell Feigenbaum once said that writing down a differential equation for a particular system is not have to done work on the problem. Where does decision making arise in a system governed by a differential equation? Is the algorithmic way of thinking naturally amenable to the differential equation technique of modelling a system?
Nick Says:
Comment #56 September 6th, 2015 at 3:04 am
In chapter 18 of QCSD, you discuss various puzzles involving anthropic reasoning. These include the Doomsday Argument, according to which we will probably witness the end of the world because, assuming exponential population growth, most people who ever live will witness it, and we are probably part of “most people”. (Accurate summary?)

At some point in the discussion, a “student” says, “It seems as though there’s a tension between wanting to be right yourself and wanting to design policies that try to maximize the number of people who are right.” This strikes me as a the crux of the issue relating to that particular argument, but all you say in response is “That’s interesting.”

It’s not clear to me why you didn’t go into more detail in the book, since it really is an interesting problem, but in any case, how do you think that tension can be resolved?
Futurist Says:
Comment #57 September 6th, 2015 at 3:05 am
As it appears Scott Aaronson has gone to bed for the night, let me try to partly answer my last question.

The “superagent” can only select from among the possible life histories of the 21st century human if historical records about that person manage to survive for all eternity even in the face of heat death in an accelerating universe. Nevertheless, I still claim this is only a complication and not a flaw because our technological descendants might still find a way the preserve information despite that.
JR Says:
Comment #58 September 6th, 2015 at 3:21 am
I am a visual artist from a depressive country where it is cold, dark and rainy most of the time. (Does that qualify as a minority?)

I am interested in figuring out how two-dimensional images could be described and compared mathematically. And I don’t mean pixel-to-pixel comparison, which is trivial, but a model that could take in account several parameters at the same time (resemblances in patterns, shades, contrasts, color values, etc). As I have looked at this, the problem lies perhaps in the syntactic density of pictures: there is no “natural” starting point for the mathematical model to be build on, ie. everything would have to be compared towards everything, which is perhaps a bit like raising yourself into air from your hair. What would be your advice?
Roland Says:
Comment #59 September 6th, 2015 at 3:25 am
Scott, you have to go into profit driven software development now (now choice, sorry!). What are you going to do?
Joel Says:
Comment #60 September 6th, 2015 at 4:10 am
Some interesting questions being posed!

Since the Fermi paradox has already been talked about, I wonder how you feel about the following argument:

When we estimate the expected number of nearby civilizations, shouldn’t we condition on our own existence?
We know that life on earth has been evolving for 3-4 billion years, and recently that process produced a species capable of some technology. It seems to me that in order for that to happen, our planet must have been pretty much left alone by whatever alien civilizations that may or may not have existed in our neighbourhood during that period. (If they had colonized earth, or used it for raw materials, or built a Dyson sphere around Sol, complex life on earth would clearly have dwindled or never gotten the chance to evolve in the first place.)
Whether or not hypothetical aliens would leave planets with indigenous life alone is hard to say, but it is at least not obvious that they would.

So given that humans exist on this planet, shouldn’t that factor in to lower our estimate on the number of nearby civilizations?
Haim Says:
Comment #61 September 6th, 2015 at 4:28 am
I guess that logicians are another underrepresented group here, so let me ask a question as a member of this strongly oppressed group:

Do you think that independence results will ever play a significant role in computer science?
eli Says:
Comment #62 September 6th, 2015 at 6:34 am
Do you visualize difficult things when trying to understand them? I’ve found that a lot of maths and cs problems that I couldn’t understand become amenable when I close my eyes and try and see and visualize them clearly. I don’t think I’d understand a lot of these things without visualization. Thanks for your time.
Scott Says:
Comment #63 September 6th, 2015 at 7:14 am
Futurist #44:
Of course there are lots of alternatives to the freebit picture—the simplest (and most popular) being simply to deny that there’s any libertarian free will that has any connection to unpredictability!

But I confess that, while I’ve enjoyed talking with Yakir Aharonov (and he’s one of the few physicists I know who also worries about libertarian free will), the two-state formalism has never appealed to me. The formalism seems naturally suited to dealing with postselected quantum experiments: that is, to situations where the experimenter imposes a final condition, by discarding all runs of the experiment that don’t match that condition. While it’s not logically necessary even for such experiments, that’s indeed where the formalism has mostly been used.

The extension of the two-state formalism to the entire universe strikes me as either
(a) an error, or
(b) a radical proposal for a physical theory that would have radical new observable consequences.

Or to put it simply: either your signals from the future cause an observable deviation from the usual rules of QM, or they don’t. If they don’t, then I’d happily dispense with them, since QM is confusing enough as it is without needing to muddy the waters further by talking about “signals traveling backwards from the end of time” that nevertheless have no observable consequences.

If, on the other hand, your signals do cause an observable deviation, then the usual question arises: why haven’t we observed it yet? And from a more fundamental standpoint: if we knew anything about which final state was being postselected (and if we didn’t, what’s the point of even postulating one?), then it’s not hard to show that we could exploit that knowledge to send superluminal signals, solve NP-complete problems in polynomial time, and do other crazy things. From long experience, many of us have learned to treat these abilities as signs of sickness, of a theory that should be discarded.

What’s different about the freebit picture is that there I can tell you, extremely clearly, that I’m not proposing any change whatsoever to the normal rules of QM: initial state, unitary evolution, Born rule, you name it. It’s a very conservative picture in that respect. All I’m doing is writing 80 pages to try to shift the way you think philosophically about the initial state (and, in the process of trying to convince you, seeing whether I can convince myself).
Scott Says:
Comment #64 September 6th, 2015 at 7:29 am
Me #46:
Happens to me all the time! The only (partial) solution I know is to install an inner skeptic—like an annoying person in the back of the seminar room—that constantly asks, from the very beginning, whether the thing you’re studying is trivial for some reason, whether it has any meat over and above what you already knew, whether you’re just going around in circles. You’d be amazed by how many people put off or avoid asking such questions! And when you do realize something is trivial, quickly move on, try something else (possibly a new twist on the trivial idea), in your hunt for nontriviality.
klas2iop Says:
Comment #65 September 6th, 2015 at 7:33 am
ZFC axioms contain only a few axioms vs the number of theorems which can be prooven from them. It keeps generations of scientists busy to write all the more interesting ones down. Can you say something about why so few premisses generate such a large and rich mathematical content so fast?
Scott Says:
Comment #66 September 6th, 2015 at 7:48 am
Silva #47:
That’s an ancient philosophical question. Logically, we could imagine a universe in which classical randomness appeared in an irreducible way, in the most fundamental laws of physics. That is, it would make perfect mathematical sense to imagine a universe with laws like, “under such-and-such conditions, flip this bit from 0 to 1 with probability 1/e.” The only issue is that in that case, philosophers could always say the randomness merely represented our ignorance of local hidden variables. That is, you could always imagine that right next to the bit you see, there’s a second bit you don’t see that’s been 1 with probability 1/e since the beginning of time. And the first bit gets flipped if and only if the second bit is 1.

In our actual world, as far as anyone knows, the only place where probabilities ever appear in fundamental physics is in quantum mechanics (that is, as the absolute squares of amplitudes). And this has the extremely interesting consequence that, via Bell’s theorem, one can rule out any local hidden-variable account of where the probabilities are coming from. Even there, however, philosophers can still choose to push the randomness into nonlocal hidden variables (as happens in Bohmian mechanics).

I confess to a fondness for mathematical questions about which kinds of hidden-variable theories are and aren’t compatible with quantum mechanics; I’ve even written two papers about such questions. FWIW, though, if we agree that the hidden variables are truly “hidden”—that is, that no future physical theory will ever let us access them directly, and that their only role is as a metaphysical bookkeeping device to account for probabilities—then my strong preference is to lop them off with Occam’s Razor, and just call randomness randomness.
rob Says:
Comment #67 September 6th, 2015 at 7:55 am
Scott,

You have a gift for opening and encouraging discussion on almost any meaningful subject, including topics that are very emotion-laden for some. Thanks.

My question is this: Outside of the field(s) of science, what are the questions you personally have about human existence, which you believe may someday be answered?
rob
Jonathan Paulson Says:
Comment #68 September 6th, 2015 at 8:01 am
Alex #51: Your counter-argument works for the finite case where there are many more rows (sequences) than columns (sequence indexes). In this case, the argument that the constructed sequence is new (the constructed sequence is different from the ith sequence at index i) does not hold, because we run out of columns quickly.

But in the infinite case, this argument that the constructed sequence is new *does* work.
Scott Says:
Comment #69 September 6th, 2015 at 8:06 am
Ultimate Reductionist #48:
Um, the same way you’d deal with trolls if there didn’t happen to be something they fanatically agreed with you about?

Leaving aside the issue of trolls, it’s always perfectly fine to acknowledge your areas of agreement (it’s even been known to help in getting people to listen to you…), while remaining resolute in the areas where you disagree.
I’m very far from an expert on the financial system—much of what I know I learn from my brother, who’s currently working as a federal regulator trying to rein in reckless banking practices (even though he’s a Zionist Jew 🙂 ). And I’d be the first to agree that strong regulations are almost certainly needed in this sector. But it still seems to me that even the first part of what you said—the part not about the Zionist conspiracy—is a pretty serious mischaracterization of how the banking system works. At least I hope it is. 🙂 Maybe someone who understands better can comment in more detail.
Scott Says:
Comment #70 September 6th, 2015 at 8:14 am
Jonathan #49:
Classically, you’re adding 1/n probability mass onto the marked item with each query. So it takes ~n queries until you’ve got a constant probability of having found it. But quantumly, Grover’s algorithm lets you add ~1/√n amplitude onto the marked item with each query. So then you get constant amplitude, and therefore constant probability, after ~√n queries. (In more detail, you get a ~t/√n amplitude, and therefore a ~t²/n probability of having found the marked item, after t queries.)
It assumes you’re looking at array indices one at a time; it doesn’t consider the possibility that you’re querying multiple indices in superposition. So the whole notion of “adding 1/√n amplitude onto the marked item with each query”—i.e., the thing Grover’s algorithm does—doesn’t even make sense in the model considered in the classical proof.
Scott Says:
Comment #71 September 6th, 2015 at 8:21 am
Annon #50:
I don’t know; it sounds difficult. I would probably focus heavily on mental images (as Stephen Hawking famously does, and as Steven Rudich, a brilliant theoretical computer scientist who went blind in middle age, also does). But, in any case, you clearly can read and write! You have a learning disability, I have ADD, many of us have mental issues that we can nevertheless learn to compensate for.
John Sidles Says:
Comment #72 September 6th, 2015 at 8:33 am
Scott stipulates “I’m looking for questions from readers who consider themselves members of groups that have historically been underrepresented in the Shtetl-Optimized comments section … but any group that includes John Sidles is probably not an example.”

Amin asks (#52) “What sounds like a reasonable resolution to the Israeli-Palestinian conflict, from where we stand right now?”

Check your privilege Under a strict reading of Scott’s stipulation, Shtetl Optimized readers whose Middle East relatives are growing-up under immanent daily threat of attack, and whose family members deploy to combat service in that theatre, are not privileged to ask peace-related questions on Shtetl Optimized.

The world wonders Is it permissable to supplement Amin’s question by asking: “Whatever might be the obstructions to realizing the hopes of Arab-Israeli peace projects, how can the complexity/QIT communities concretely help to dissolve those obstructions and realize those hopes?”

PS This question is inspired by a peace-fostering STEAM tradition that extends through many decades from The Bulletin of the Atomic Scientists (founded 1945) to NeuroBridges (founded 2014).
TeenWolf Says:
Comment #73 September 6th, 2015 at 8:35 am
The girl I like introduced me to her father and family. Two days later I sent her mail that it will be nice to catch up. A week later she got back essentially stating she was busy and did not know when it would be a good time to catch up and good luck to all my endeavors. It has been 3 months. Would an effective quantum algorithm help me communicate with the past to alter the future? https://en.wikipedia.org/wiki/Quantum_mechanics_of_time_travel
Scott Says:
Comment #74 September 6th, 2015 at 8:46 am
Amin #52:
We’ve discussed this in detail in previous AMAs. I remain a firm supporter of a two-state solution, even though alas, it seems to have receded further and further as a realistic possibility, due to developments on both sides.
Scott Says:
Comment #75 September 6th, 2015 at 9:02 am
Quin #53:
Just the way you’ve phrased things above, involves such a thick tangle of confusions that I’m afraid I won’t be able to untangle it before breakfast. 🙂 The prerequisite to understanding this is going to be to learn to talk about it more clearly.

For starters, when we talk about the halting problem, there are two programs in play, not one: there’s the machine M for which we want to know whether it halts or not (say, when run on a blank input), and then there’s the hypothesized machine P that takes as input a description of M, and that reliably decides whether M halts.

The trick, in Turing’s proof, is to construct M via a modification of P itself, in such a way that P(M) has to accept if it rejects and reject if it accepts, so the only consistent possibility is that P(M) never halts and produces any output—which means, contrary to assumption, that P doesn’t decide the halting problem. There are hundreds of books and lecture notes (including mine!) that go through this more carefully.

I don’t understand what you mean by “has the potential to go on forever”—a given deterministic Turing machine, on a given input, either goes on forever or it doesn’t! But I can tell you that, yes, it’s certainly possible in practice to solve the halting problem in many instances—i.e., to write infinite-loop-detectors that will tell you “this program definitely halts”, “this program definitely runs forever”, or sometimes “I don’t know” (and whose output will always be correct). All Turing’s proof tells you is that there’s no way to completely eliminate the “I don’t know” case.
jonas Says:
Comment #76 September 6th, 2015 at 9:18 am
As a nerdy white male who makes up much of the comment section of this blog, I come to this party uninvited, but ask a question anyway.

Where should we build the gravity wave detector instruments, on earth, or in space?
Scott Says:
Comment #77 September 6th, 2015 at 9:29 am
jonas #76: In space.
Scott Says:
Comment #78 September 6th, 2015 at 9:52 am
Ajit #54:
Walking to the office, chasing after a toddler, looking after a toddler in a swimming pool, lifting a toddler. If you ask, “is that actually enough exercise? combined with a mediocre diet, wouldn’t such a ‘routine’ cause you to develop a bulging fat stomach?”—to ask such questions is to answer them.
F. Marshall Says:
Comment #79 September 6th, 2015 at 9:59 am
Hi Scott! I’ve been reading the blog since the last AMA and many time thought of what I’d ask you if you ever decided to do another one, so thanks for the chance!

I wouldn’t call myself a minority, but I don’t see a lot of Brazilian undergrads in the SO threads, so I guess I qualify to ask.

I’m very passionate about theoretical computer science (especially computability and algorithmic information theory). Despite being surrounded with excellent professors, none of them research these things (the big thing with theoretically incline people here is combinatorics). I want to go into Academia and become a CS professor myself, so I guess my question is: where to begin? Do you know of any yet unproved results in these areas that a undergrad with too much time on his hands might be able to tackle?
CamelCaseEnthusiast Says:
Comment #80 September 6th, 2015 at 10:11 am
Forgive me if my question reeks of some common misconception, but will quantum computers be better at chess than classical computers?
Scott Says:
Comment #81 September 6th, 2015 at 10:36 am
CamelCase #80: You could use the Farhi-Goldstone-Gutmann quantum algorithm to evaluate chess game trees, which would give you a square-root advantage over classical game-tree evaluation. So yes, absolutely, that could give you an advantage—though since it’s “only” a quadratic speedup rather than an exponential one, it’s also possible that it would be swamped by error-correction and all the other overheads involved in building a QC.
Joshua Zelinsky Says:
Comment #82 September 6th, 2015 at 10:49 am
The truth, of course, is that we have no idea. And as Carl Sagan once said, it’s excellent epistemic practice, in situations of such massive uncertainty, to learn not to think with one’s gut. We do know that unicellular life arose remarkably quickly in the history of the earth, whereas intelligent life took billions of years longer. And we know that life did arise on the one body in our solar system whose temperature seems hospitable to life (at least from our limited perspective), and that there must exist trillions of other planets whose temperatures are similarly hospitable. So, does that suggest that life is common but intelligent life is rare? Alas, we can’t even say that with any confidence. If we had even one other case study of life arising—for example, on Mars—that would already be enough to start thinking about it like Bayesians and plugging some numbers into the Drake equation. But our actual situation is that we have only the one case study (earth), and it’s hopelessly contaminated by selection bias.

I think this underestimates how much we can learn from our single sample. In particular, our star has a moderate lifespan. Imagine for a moment that in order for intelligent life to arise, many different specific unlikely steps need to occur after life has arisen (say mitochondria, multicelled life, nerves and a few others). In that case, we’d expect to find ourselves arising very late around a star with a long life-span, like say a red dwarf with a lifespan in the trillions of years, and all the more so when such stars are much more common than stars like the sun. The reasonable conclusion then is either a) something will arise preventing much life arising in a few billion years (such as life from a handful of planets spreading out and actively colonizing) or b) That there is not a long chain of needed unlikely steps to go from life to intelligent life.

Two essays on the Fermi problem I think address a lot of the relevant issues are http://lesswrong.com/lw/lls/astronomy_space_exploration_and_the_great_filter/ and http://lesswrong.com/r/discussion/lw/mj5/astronomy_astrobiology_the_fermi_paradox_i/ (the first of which I’m the author of).

Alas, there’s no question yet, and I’m clearly not from a diverse set, so I’ll pass on a question from my wife: “We all know that Scott is firmly on the latke side of the latke v hamentashen debate. How does he feel about latke v. flanken”?
anon Says:
Comment #83 September 6th, 2015 at 10:52 am
Scott, I’m a physicist but strongly inclined towards math and obsessed (like you? 😉 ) by computation/complexity. I’m curious about the world of mathematicians with which I’m not too familiar.
Somebody says that a mathematician is “burned” after age 40. I do not see this problem for physicists. Do you agree? Do you feel your mathematical innovative vein fading? Is it really that math ability fades or we are just too busy at some point? With kids, family and departmental meetings/conferences 😉 we cannot stay up 3 nights in a row on a specific problem as we did when young..or not? Thanks and great blog.
Greg Kuperberg Says:
Comment #84 September 6th, 2015 at 11:10 am
Of course, quantumly a complex number (amplitude) refers to something that has a physical bearing. Sure nature keeps this number to herself…

My answer: Actually, the amplitude doesn’t have a physical bearing, it has a statistical bearing. Nature “keeps this number to herself” in the same sense that a coin that has been flipped doesn’t know the probability that it is heads. (“If it has a 55% chance of being heads, where is that number stored???”)

What is physical is that “nature” follows these alternate laws of statistics that people had never realized were true, until the 20th century.
undergrad Says:
Comment #85 September 6th, 2015 at 11:26 am
Hi Scott! I’m a freshman in college who lurks around here, even though I hardly ever understand anything. I’m majoring in computer science and am trying to decide if doubling in math is a good idea. I worry that not doing math in college will lock me out of the kind of theoretical territory you cover here. (On the other hand, I’d like to keep the “liberal arts” in my liberal arts education.) Do you think forgoing math will detract significantly from my undergraduate CS education, and if so how/to what extent? Thank you, and thanks for this initiative! And also thank you tons for the explainers you do in your posts for people who have no idea what’s going on.
David Speyer Says:
Comment #86 September 6th, 2015 at 11:48 am
A comment on classical intuition for Grover’s algorithm: (question #49, answer #70): Suppose that we perform a bunch of classical queries, each of which moves the *amplitude* of detecting the marked item by some small amount c. Since we are working classically, we don’t pay attention to the phase of our modifications, so the amplitude behaves like a random walk with step size c, and moves c√n after n queries. In Grover’s algorithm, we make sure all the phases line up, so the amplitude moves basically in a straight line, and thus changes by c n.

I can give a fully classical analogue of this. Classical search is like opening a perfume bottle on one side of a room and waiting for the scent to waft to the other (the perfume molecules carry out a random walk), Grover’s algorithm is like setting up a fan.

Disclaimer: Neither a minority nor a quantum expert.
Douglas Knight Says:
Comment #87 September 6th, 2015 at 12:44 pm
Scott, your chess answer doesn’t sound right to me. First, asymptotically, the speed-up of FGG should beat the slow-down of error-correction, shouldn’t it?

Second, Groverish things like FGG beat classical exhaustive search, but that’s not the right benchmark. People generally believe that exhaustive search is optimal for SAT, but not for chess. Actually existing chess programs are not very close to exhaustive search.

As you’ve said before, the question of whether quantum computers will have extensive applications is exactly this question: whether Groverish advantages can be merged with existing classical heuristics (or new quantum heuristics). But this is a very difficult question to answer without a QC to test on, in part because it’s a question about heuristics. Indeed, algorithms address different questions. FGG address how much time it takes to play a perfect game, while heuristics attack the different question of how to play best given limited time.
Orin Says:
Comment #88 September 6th, 2015 at 12:45 pm
Scott,

“There’s nothing counterintuitive, in your mind, about the ability to manipulate probabilities like this?”

Not at all! You’re functionally changing the odds by literally copying billions of people based on the results of the toss!
Observer Says:
Comment #89 September 6th, 2015 at 12:46 pm
Europe is being invaded. Israel and other countries would take military action, if necessary, to protect their ethnic identities. Should European countries do the same?
wolfgang Says:
Comment #90 September 6th, 2015 at 1:11 pm
@Scott #update

>> Do not ever, under any circumstances, attempt to visit Walden Pond

I see what you are doing here. You just want to make sure that the next time you visit there are less people – playing the minority game with the help of your blog 😎
Vadim Says:
Comment #91 September 6th, 2015 at 1:40 pm
Hey Scott, just wanted to second your Walden Pond suggestion. Went there last summer hoping to walk around and just be outside for a while. Succeeded insofar as I got to walk around outside, at the Brandeis campus.
Crab Says:
Comment #92 September 6th, 2015 at 1:55 pm
Hi Scott, did recent advancements in AI since your post on the technological singularity in 2008 (vast improvements on ImageNet, word2vec, prospects to leverage memristors for hardware neural nets, various findings in neuroscience) update your belief on the feasibility of near-term AGI (let’s say within 20 years)? Thanks.
Scott Says:
Comment #93 September 6th, 2015 at 2:13 pm
wolfgang #90: I take umbrage at your attributing such base motives to me. I was just trying to be a Good Samaritan, and help the wardens a bit in their goal of clearing the park out.
Greg Kuperberg Says:
Comment #94 September 6th, 2015 at 2:26 pm
Somebody says that a mathematician is “burned” after age 40.

“It is a sobering thought that when Mozart was my age, he had been dead for two years.” — Tom Lehrer
Scott Says:
Comment #95 September 6th, 2015 at 2:55 pm
Douglas #87: Yes, of course the Grover speedup asymptotically wins over error-correction (which is “only” a polylogarithmic overhead). But the overhead, in practice, will be by many thousands or millions, making it hard for me to estimate (e.g.) how deep in the game tree you’d need to search before you start to see an advantage for chess.

And yes, of course the question is how well you do compared to the best classical pruning algorithms, not how well you do compared to brute force. But one thing we’ve learned is that the Grover speedup usually CAN be layered on top of clever classical pruning heuristics (and indeed, the quantum walk framework can often take care of such things automatically).
Scott Says:
Comment #96 September 6th, 2015 at 3:01 pm
Crab #92: AGI in 20 years? Eh, I guess Google’s recent deep learning victories make me consider it marginally more likely than I did a few years ago, but still massively unlikely. Honestly, I’ll be impressed if in 20 years the US has a rail system that’s up to 1950s standards.
Alexander Vlasov Says:
Comment #97 September 6th, 2015 at 3:25 pm
Scott #31 – it is a comment – I met quite reasonable papers about consideration of Fermi paradox and all that using multiverse (both stringy and quantum) idea…
Silva Says:
Comment #98 September 6th, 2015 at 5:02 pm
Thanks Scott for your clarifying answer! Also thanks Greg Kuperberg for his great points.

If it has a 55% chance of being heads, where is that number stored???

But couldn’t we say that the bias of a coin in in a way “stored” into the physical properties of the coin? (like its shape, or the coin having more mass on the “head” side, etc).

In my original comment I used big words like “physical bearing” and “nature” in an intuitive way, but of course I might be stepping outside my confort zone which is CS/TCS, so I am not exactly sure what I am talking about 🙂

I am wondering about your point of amplitudes not having “physical bearing”, since there is this notion that (quantum) randomness is a resource that we can use for computation. I usually think of a “resource” as something physically available (like time and space) for computation. But again, I am not sure what I mean by “resource” and we maybe that’s more of a philosophical point anyway.
Scott Says:
Comment #99 September 6th, 2015 at 5:56 pm
TeenWolf #73:
Dude. Based on some classical experience in this field, I humbly recommend a classical, causal, and future-oriented approach (to wit: quickly moving on to the next girl).
Greg Kuperberg Says:
Comment #100 September 6th, 2015 at 6:01 pm
But couldn’t we say that the bias of a coin in in a way “stored” into the physical properties of the coin?

The physical properties of a coin do tell something about what its bias would be if you flipped it many times, in the future. However, if you have a covered coin in front of you that someone flipped, by some method, no, it doesn’t know the probability that it is heads. That numerical probability is statistical knowledge; if you ask the coin, all it can tell you is that it is either heads or tails.

I am wondering about your point of amplitudes not having “physical bearing”, since there is this notion that (quantum) randomness is a resource that we can use for computation.

Just like any other kind of randomness (except more so), quantum randomness is a statistical resource that you can use for computation. All that’s meant by a “resource” is that it is a form of help, it can help get you to the answer.
Scott Says:
Comment #101 September 6th, 2015 at 6:10 pm
undergrad #85:
I would phrase it in more positive terms: the more math courses you can fit in, the better outfitted for CS your brain will be. In my case, I took enough math at Cornell to be a math/CS double major, but I couldn’t get a math degree because I was the Engineering rather than Arts school. (Why? Because in the arts college you had to take 3-4 semesters of a foreign language, which seemed like a huge waste to me at the time…)

I would particularly focus on linear and abstract algebra, real and complex analysis, combinatorics, probability, and possibly representation theory and logic. Other things, like topology and differential geometry and algebraic geometry, might have less immediate connections to CS, but are also great fun and will sharpen your skills.

One warning: some of your math courses will be poorly taught. But counterintuitively, it might not matter that much! How much you learn probably has less to do with the lectures than with you, and with your private struggle against the problem sets.
Scott Says:
Comment #102 September 6th, 2015 at 6:23 pm
Rahul #55:
I don’t know—I tend to wonder more about whether differential equations are amenable to the algorithmic way of thinking! 🙂 I can tell you that, in the 50+ TCS papers I’ve written, I can’t remember having ever once needed a differential equation for anything (though I have needed integrals and partial derivatives, and once even Lebesgue measure). Of course, this might simply reflect my personal biases and training: maybe if I were better at differential equations, I’d realize there were things I could do with them. Indeed, I have very, very occasionally seen differential equations in TCS papers (I think they were about statistical physics, or maybe algorithmic approaches to population genetics).

However, I suspect the more fundamental issue is that in TCS, even when we think about reals or complex numbers (say, in probability, quantum computing, and algebraic computing), we almost always leave time discrete. For that reason, we’re much, much more often thinking about discrete-time iterative processes than we are about differential equations.
John Sidles Says:
Comment #103 September 6th, 2015 at 6:51 pm
Tony asks “Do you know of any large scale project […] to get formulas by brute force?”

The indispensably entertaining Mathematical Intelligencer published an article by mathematicians Martin Mohlenkamp and Lucas Monzón titled “Trigonometric identities and sums of separable functions” (2005), in which they derive novel trigonometric identities by brute-force search methods.

Subsequent articles by Mohlenkamp, often with Gregory Beylkin, extend this work to practical computations in quantum chemistry (see e.g, arXiv:0708.2896 [math-ph]). In particular, Mohlenkamp’s review “Musings on multilinear fitting” (Linear Algebra and its Applications, 2013) reads enjoyably as a student-friendly companion to Ulrich Schollwöck’s magisterial (and lengthy) survey “The density-matrix renormalization group in the age of matrix product states” (Annals of Physics,2011).

Scott too has published in this area: “Multilinear formulas and skepticism of quantum computing” (Proceedings of the ACM/STOC, 2004):

“[This article’s] goal is to refine vague ideas about a breakdown of quantum mechanics into specific hypotheses that might be experimentally testable in the near future.”

Aphoristic conclusions “Multilinear state-spaces: they’re not just for numerical work anymore.” Alternatively: “Multilinear state-spaces: mutual grounds for quantum skeptics and quantum optimists.” Or even “All roads lead to multilinear state-spaces.”
Scott Says:
Comment #104 September 6th, 2015 at 7:04 pm
klas2iop #65:
This is a lot like wondering: how can the mere 26 letters of the English alphabet possibly generate the immense richness of the English language, Shakespeare and Nabokov and Lady Gaga and all the rest? Or: how could the three primary colors, and various mixtures thereof, generate the complete works of da Vinci and Picasso? Or: how could the relatively-simple rules of baseball and basketball and football (both kinds) generate gameplay that’s kept hundreds of millions of people enthralled for generations? (OK, fine, I’ve wondered myself about the last one. 🙂 )

The answer, in all these cases, is that the word “generate” is possibly too strong. You could think of the ZFC axioms (and, what you could also have mentioned, the rules of first-order inference) as the mathematician’s palette. But then she can use that palette to paint whatever she wants on a giant canvas. The ZFC axioms say nothing about which questions we should find interesting (Fermat’s Last Theorem, P vs. NP…), or which higher-level structures (complex numbers, group representations…) we should introduce to study those questions. The axioms and inference rules do “determine what’s provable,” but only, you might say, in the uninteresting sense that the spectrum of colors “determines what’s paintable.”

And indeed, just like a painter is probably thinking less in terms of red, blue, and yellow than in terms of people, scenes, and emotions, 99% of the time a mathematician isn’t thinking at all about the axioms, but only about the higher-level structures being painted on the canvas.

Actually, this analogy extends quite far: just like there are avant-garde artists who paint with goat blood or whatever, and avant-garde musicians who play unusual instruments (warning: probably NSFW), so too there are avant-garde mathematicians who see how much more they can do if they change or extend the ZFC palette, or how much they can still do if they restrict it. But, just like in the other examples, most mathematicians are so engrossed in trying to use the palette to express their ideas about other topics, that they have little time to worry about the palette itself.
Greg Kuperberg Says:
Comment #105 September 6th, 2015 at 7:33 pm
I’m majoring in computer science and am trying to decide if doubling in math is a good idea.

My answer: There is a certain fearlessness which is extremely valuable both for its own sake, intellectually; and for a technology career in the 21st century. There are a lot of software engineers (maybe most of them) who head for the exit when they hear the word “theorem”; and there are a lot of mathematicians who crumble at the sight of a block of code. People who aren’t afraid of either one are especially well-prepared to understand things and accomplish things.

What is valuable is not so much the specific material — although some topics are more stimulating than others for this purpose — but the combined way of thinking. On the math side, I personally would recommend discrete mathematics and algebra courses, as well as CS theory courses where theorems are proven. A class in probability is also helpful. As Scott says, just about any topic in mathematics is relevant to CS in principle. Analysis is closer to applied mathematics, and the first wave of uses of computers in science and mechanical engineering. That is still very important and if it interests you, so much the better. However, discrete mathematics is more relevant to the new wave of technology, things like data compression, encryption, network routing, etc.

I also highly recommend the web site Project Euler, as a great introduction to the synthesis of computer programming and mathematics.
Scott Says:
Comment #106 September 6th, 2015 at 7:41 pm
F. Marshall #79:
Two years ago, I had a fantastic visit to Rio (my first to Brazil), where I had the pleasure of spending time with Ernesto Galvao and other Brazilian QC researchers. So I would say that Brazil does have a good presence in QC—and certainly in dynamical systems and certain other areas of math, at the world-renowned IMPA (which Dana visited, although I missed it). I don’t know which part of Brazil you’re in, but it’s possible that you could find a world-class research community down the street, if not in TCS then in something allied to it that would also interest you.

On the other hand, it’s fair to say that Brazil currently has little to nothing in classical TCS—a property that it shares with many other countries that are strong in other parts of science! So, if you’re serious about TCS, that will probably mean going to grad school abroad, as Ernesto Galvao did, and as my good friend Fernando Brandao did as well.

What can you do in the meantime? Soak up all the math and CS you can at your university in Brazil. (At the time I was an undergrad at Cornell, there was no one there doing quantum computing, but it didn’t hurt me—I learned about math and AI and classical TCS, and started doing quantum computing on my own and over the summers.) Study TCS books, like Arora-Barak, or Gems of Theoretical Computer Science. Do the exercises. Check out the latest papers every week on arXiv and ECCC—and if you find something that interests you, see if there are open problems that you could try tackling. Shoot the authors an email if you have thoughts or questions about their paper that might interest them. Oh, and also: try to find a summer research position abroad doing something TCS-related. Email people whose work interests you to see if they have openings. (Sorry, I don’t at the moment. 🙁 ) And if you have a convenient opportunity to attend a TCS-related conference or workshop (say, one happens to be in Brazil), seize it, and talk to people there.

When you apply to grad school, people will try to take into account not only how much you’ve done related to TCS, but also how much opportunity you’ve had to do it. And if you’ve done a lot despite little opportunity, that will obviously command attention.
Alex B. Aible Says:
Comment #107 September 6th, 2015 at 8:42 pm
Jonathan Paulson #68:
Your response is incomprehensible to me. There are from the start (when $n$ = 2) “many more” columns than rows in a $2^n$ by $n$ matrix and this initial disparity increases explosively. If I were to ask you exactly when the matrix becomes “infinite,” or exactly what the first “new” number is, you would have no answer. If I asked you to describe a single finite “portion” of an infinite “new” number, you would have no answer. You are doing what Infinitists always do, claiming that, after a “mysteriously” sufficient number of finite repetitions, a “magic” land suddenly appears where scientific logic falls away, allowing us to dance in absurdaholic transport with pixies and unicorns.
Alex B. Aible Says:
Comment #108 September 6th, 2015 at 8:58 pm
Jonathan Paulson #68:

This is a correction of my post #107. It should read as follows: Your response is incomprehensible to me. Although there are from the start (when $n$ = 2) “many more” rows than columns in a $n$ by $2^n$ matrix, this initial disparity increases explosively. If I were to ask you exactly when the matrix becomes “infinite,” or exactly what the first “new” number is, you would have no answer. If I asked you to describe a single finite “portion” of an infinite “new” number, you would have no answer. You are doing what infinitists always do, claiming that, after a “mysteriously” sufficient number of finite repetitions, a “magic” land suddenly appears where scientific logic falls away, allowing us to dance in absurdaholic transport with pixies and unicorns.
Scott Says:
Comment #109 September 6th, 2015 at 9:02 pm
anon #83:
As a 34-year-old with a time-consuming toddler (not to mention departmental meetings and conferences…), of course I worry about whether my best results are behind me.

If you ask them, most mathematicians will say that “math being a young person’s game” is a pernicious myth, and will point to counterexamples like Wiles proving FLT at 40, or Euler and Erdös writing hundreds of papers in old age. The trouble is, even if it were statistically the case that most mathematicians peaked in their 20s or early 30s, the social and emotional pressure for saying otherwise would be so immense that most mathematicians would do so, or at least would find clever ways to deflect the question!

Aaronson’s Law: The smartest person in the world, asked about anything other than the exact subject of their expertise, will 90% of the time say something warm, uplifting, tactful, witty, and false over something cold, boring, arrogant, maladroit, and true.

OK, but even after accounting for Aaronson’s Law, I still don’t know the ground truth about this. I’m privileged to know many older mathematicians who are absolutely fearsome, who run rings around me. (On the other hand, those mathematicians often did their best work when younger.)

Turning to personal experience, it’s absolutely true that I look back with disbelief at how productive I was able to be in grad school—how I could just throw my soul into a problem for months, skipping meals and whatnot, until I understood everything about it. That happens much less often today!

But this still doesn’t answer your question: is the issue “merely” that I’m now married with a kid, and have department meetings and students and emails and AMA blog sessions eating up my day, 🙂 and also that I’m much less hungry to “prove myself” than I was then? Or have I additionally gotten dumber? I don’t know. It’s extremely encouraging that, on the rare occasions when I do throw myself completely into research, I feel all the juices flowing and it’s just like it was in grad school. What I can’t tell is whether, if you magically removed all my other responsibilities in life, I’d be able to throw myself into research-mode as regularly as I did back then. But I’d love for someone to give me a few months to test that question. 😉

Of course, even if I couldn’t do now what I did in grad school, there’s a silver or even a gold lining—something extremely rewarding I can do today that I couldn’t do then—and that’s to mentor phenomenal students. I guess I’m far from the first academic to have discovered this particular route to continuing relevance, after one may have “passed one’s own peak.” More broadly, a lot of how the typical mathematician’s work changes as she ages is less diminution than evolution: it becomes less about conquering specific problems and more about noticing weird connections between problems (or advocating new directions for the field), less about solitary achievement and more about teamwork and mentorship. These are certainly all trends that I’ve noticed in my own case.

Three other miscellaneous remarks:

– Whatever the truth about these matters, I doubt there’s a significant difference between math and theoretical physics. Modern experimental physics is a different kettle of fish, requiring skills like managing large teams and attracting funding.

– That the Fields and Nevanlinna are only awarded to mathematicians under 40 is an absurdity. Even if it were true that many or most mathematicians peaked in their 20s or 30s—why on earth should anyone be penalized for peaking later?

– I speculated years ago that the typical career arc might be slightly different for female mathematicians than for male ones, with women peaking a bit later (on average). If so, then the restriction of the Fields and Nevanlinna to people under 40 would be a particular injustice.
Greg Kuperberg Says:
Comment #110 September 6th, 2015 at 9:26 pm
As a 34-year-old with a time-consuming toddler (not to mention departmental meetings and conferences…), of course I worry about whether my best results are behind me.

You could simply ask whether major victories are in your future, instead of trying to compete with your own past. After all, what did Shirley Temple do after her last big Hollywood hit at age 12? At age 61, she became US Ambassador to Czechoslovakia; and she did lots of other things in between.

Or, I guess you could do what Michael Jackson did: keep trying to top yourself decisively, and fade into a miserable hell of megalomania and insecurity. 🙂
John Sidles Says:
Comment #111 September 6th, 2015 at 9:42 pm
anon wonders (#83) “[Is] a mathematician ‘burned-[out]’ after age 40?”

Supercentenarian STEAM-Jeopardy

Answer The oldest Austrian male ever recorded, he published his final mathematical article at age 104, and died at age 110.

Question Who was the algebraic topologist Leopold Vietoris?

————

Ongoing news Engineer Simon Ramo (the “R” in TRW), who was born in 1913, last year became the oldest person to receive a US patent … at age 101.

Talk about lifelong learning … 🙂
Scott Says:
Comment #112 September 6th, 2015 at 9:46 pm
Alex Aible #107, #108: You seem to be adopting Kronecker’s position, that Cantor’s results are all invalid because reasoning about infinite sets is nonsense. This particular debate happened more than a century ago, and—speaking as someone who spends most of his time on “tame,” finite, combinatorics-style math—I’d say that Cantor’s side unequivocally won.

The reason it won is, firstly, that it’s hard to find any principled way to admit all the infinitary reasoning used in the “ordinary” parts of math—real analysis, topology, etc.—that also prohibits Cantorian reasoning. If you want the one, you’re more-or-less stuck with the other. But secondly, far from being a curse, Cantor’s way of thinking had a huge impact even on “tame, finitary” parts of math—e.g., Gödel’s and Turing’s theorems are all about the limits of finitary procedures and formal systems, but it’s nearly impossible to tell the story of Gödel and Turing without also telling the story of Cantor. (I’ve tried.)

In sum: if you reject the reasoning used in Cantor’s diagonal proof because “only finite processes are valid,” then you’re completely crippled in your ability to go further in math—even the parts of math dealing with finite processes only—and that fact trumps any a-priori philosophical consideration.
Scott Says:
Comment #113 September 6th, 2015 at 9:52 pm
Nick #56:
That depends entirely on whether I’m only trying to resolve this tension in my own mind, or whether I’m trying to maximize the number of people for whom the tension is resolved. 😉
Philip White Says:
Comment #114 September 6th, 2015 at 9:54 pm
klas2iop #65: First, you should understand that technically, ZFC has infinitely many axioms; there are not that many axiom schemas in ZFC, but don’t let that deceive you, as a schema is just a sort of “template” for (infinitely many) other axioms.

On the other hand, NBG (von Neumann-Bernays-Godel) is an equivalent system that can be formalized with (by my count) just 20 axioms (5 logical, 7 class existence, and 8 other). According to my logic text, the term NBG was coined by Elliot Mendelson (or at least that’s what he says–he is the author of the book).

Anyway…to understand why logic is so rich, one must understand first-order logic a little bit. Basically, first-order logic has two inference rules: modus ponens, and universal generalization. Even *without* the full power of NBG (or ZFC), one can use merely the five logical axioms to form a predicate calculus, and explore the vast power of this simple deduction system.

So: the short answer is, the five logical axioms and the two inference rules of first-order logic seem to have something to do with the power of logic. I would imagine careful study of these could lead to some greater insights than I’ve provided.

(Caveat: I’m not a professional logician. But you might enjoy “Introduction to Mathematical Logic” by Mendelson, I highly recommend it!!)
Scott Says:
Comment #115 September 6th, 2015 at 9:54 pm
JR #58:
Look into all the work that’s been done (including spectacular recent successes) on using neural nets / deep learning for image clustering and classification. That would seem like the obvious place to start.
Scott Says:
Comment #116 September 6th, 2015 at 10:01 pm
Roland #59:
Well, I guess the answer is “go into profit-driven software development”! 😉

More seriously: like many CS academics, I get recruited from time to time by Silicon Valley companies, so I could accept one of those offers. Or, were I feeling more adventurous, I could try to round up some friends who knew more than I did and form a startup—maybe something to do with machine learning, or crypto, or educational games. But I’d need to put a lot more thought and real-world investigation into it first.
Scott Says:
Comment #117 September 6th, 2015 at 10:14 pm
Joel #60:
Yes, although this seems like another instance of a principle we’ve already discussed: that the very fact that we haven’t yet made contact should tend to lower our estimate on the number of nearby civilizations, relative to what it would’ve been had we been thinking about it in some hypothetical Bayesian vacuum. What it adds, I guess, is that this would still be true even if we hadn’t been doing SETI searches and whatnot—since we’d expect at least some nearby aliens, had they existed, to have tried to reach us, if for no other reason than to pillage and enslave us. And with that, I guess we’ve come full circle back to Enrico Fermi’s original argument in the Los Alamos cafeteria.
Scott Says:
Comment #118 September 6th, 2015 at 10:50 pm
Haim #61:
I’d say that independence results already have played a significant role in computer science: Gödel’s Theorem very obviously, but also Cohen forcing, which almost certainly inspired Solovay and others in their constructions of relativized worlds in complexity theory. More broadly, I’d say that theoretical computer science started life as a branch of mathematical logic; among the founders of TCS, Gödel, Church, Turing, Kleene, Post, Cook, Levin, Rabin, and probably others all had independence results at the center of their thoughts.

Having said that, I confess that independence results sometimes feel more like part of TCS’s past than like part of its future. One possible explanation is that, by the 1970s, complexity theory had already gotten about as far as it could using methods borrowed from logic (with the Baker-Gill-Solovay relativization barrier providing one formalization of that idea). Going further requires rolling up one’s sleeves, leaving the realm of metamathematical questions that could plausibly be independent of ZFC (but that, if they can be answered at all, can probably be answered by yet another diagonalization 🙂 ), and tackling meatier, mathier problems that past experience leads one to expect should “merely” be hard in the sense that Fermat’s Last Theorem or the Poincare Conjecture were hard, and not in the sense that the Continuum Hypothesis is hard.

Of course, maybe this is completely wrong! Maybe P vs. NP or some other such question will turn out to be provably independent of ZFC or other strong formal systems. If so, that would obviously be a revolutionary development, and would decisively answer your question. 🙂 But I wouldn’t put my money on it.

One final remark. If you take a broader view of what “independence results” mean than just “independence from powerful systems like PA or ZFC,” then one thing we’re constantly doing in TCS is stepping back, codifying the techniques that worked to answer a whole bunch of questions, and then asking whether those techniques can possibly suffice to answer some other question. And often we can prove that the answer is “no,” meaning that new techniques are needed. That’s exactly what happened with relativization, natural proofs, algebrization, and hundreds of developments in other parts of TCS, from cryptographic protocols to quantum query complexity. In that sense, you could argue that independence results are completely pervasive in TCS and will remain so for the foreseeable future.
Scott Says:
Comment #119 September 6th, 2015 at 11:03 pm
eli #62:
Yes, constantly. I’m almost completely reliant on visualization; often there’s a single PowerPoint slide or whiteboard scribble that makes something completely clear to me, where no amount of verbal explanation had helped. (Other times, I stare at the image and am still lost—maybe because my visual vocabulary remains too different from the other person’s, because they’re attaching deep meanings to each box and arrow that they’ve so fully internalized, that they no longer remember what it was like to see the things drawn as just boxes and arrows.)
TeenWolf Says:
Comment #120 September 6th, 2015 at 11:19 pm
Scott #99 It is difficult for autistic people to take that step easily. Such a nice girl:(

But seriously is communicating with the past allowed in quantum communication? Does it affect present and the future without affecting past?

Information is different from other things physical. It does not have mass. There is nothing about transferring some energy to the past (communication) as long as a similar energy can be brought back to the present and future (changing information about the future).
Scott Says:
Comment #121 September 6th, 2015 at 11:31 pm
rob #67:
This is a toughie for the following reason. If something is “answered” (meaning, to every competent person’s satisfaction), then doesn’t the very fact that it was answered make it part of “science,” at least if “science” is understood in the broadest sense (encompassing psychiatry, archaeology, textual analysis, and any other field that tries to definitively answer any question of fact)?

When I try to come up with counterexamples, the best I can do is moral questions: is slavery wrong? should women have the vote? These questions were once open and have since been answered—but, it would seem, not by science. (Science at best played a supporting role, by undermining certain arguments for what today we recognize as the wrong answers.)

Now, as I alluded to in this post, there are certainly moral questions for which I believe that the right answer is different from the answer that’s commonly accepted today, even among educated people. So, you could take any of those as examples of currently-“open” questions about human existence that I believe (hope?) may someday be answered. For obvious reasons, I’m circumspect about posting a list of all my heterodox moral beliefs (if I had nothing to fear, then they wouldn’t really be heterodox…), although if you read the archives of this blog, I’m sure you can infer what many of them are. But, in any case, these moral questions don’t feel to me like fair examples of what you asked for, since they’re all things where I think I already know the answer! 🙂
Scott Says:
Comment #122 September 6th, 2015 at 11:43 pm
TeenWolf #120:
Quantum mechanics, as most physicists currently understand it, is surprisingly boring and conservative in regards to time. Yes, there are channels of one-way communication allowed from the past to the present: they’re called memories and records. And those very same channels can be used for one-way communication from the present to the future. But at least in standard QM, there are no closed timelike curves (i.e., communication from future to present or from present to past), or anything else that contradicts our everyday understanding of time.

(Relativity, of course, does contradict our everyday understanding of time, and GR even opens up the theoretical possibility of closed timelike curves—though some of us suspect there are deeper principles that prevent that possibility from being realized in the actual world.)
eli Says:
Comment #123 September 7th, 2015 at 12:02 am
My question about visualizing was mostly about images you generate in your mind, not external things drawn, just like closing your eyes and trying to visualize.
Scott Says:
Comment #124 September 7th, 2015 at 5:20 am
eli #123: Yes, I think in images internally as well. I focused on externally drawn images just because they’re sometimes crucial pieces of evidence for how someone else is thinking, which can immediately show me whether or not the other person is representing something internally the same way I am.
RubeRad Says:
Comment #125 September 7th, 2015 at 10:31 am
Yay, I’m a ‘traditionally religious’ (confessional Presbyterian) minority! … but I have nothing to ask.

Thx Gene Chase for your great question and thx Scott for your response. Looking into Mind/Body Problem…
Scott Says:
Comment #126 September 7th, 2015 at 2:57 pm
Observer #89:
“Being invaded” strikes me as an overly emotive way of putting it. What’s happening, for the most part, is that certain European countries democratically adopted legal immigration policies that are now leading to huge, rapid changes to their demographics. I believe that this is an extremely serious issue for the future of Europe, as politically incendiary as it is among my fellow liberals to say so. But no, “military action” isn’t the answer—against whom would one declare war, anyway?

Many of the immigrants, of course, are coming to escape hellish conditions in their original countries, work hard jobs, and build better lives for their families. Regardless of what one thinks about the host countries’ capacity to absorb them, it’s impossible not to feel sympathy for anyone in that position. And a few of the immigrants, or their children, will become great scientists or other luminaries, even though they would’ve had no hope of doing so in their countries of origin. In those cases, the fact that the people were allowed to immigrate has to be counted as a gift to humanity.

At the same time, there’s nothing inherently evil about a given country wanting to maintain a certain culture and demographic makeup, or at any rate, to prevent them from changing super-rapidly. We know this to be true, because even the most hardened social-justice warriors will agree about it if we vary the example. Consider, for example, the liberal outrage over the gentrification of ethnic neighborhoods (as too many affluent whites move in), or the lack of international outrage about Japan’s policy of keeping its country almost exclusively for ethnic Japanese, even as it suffers a population implosion.

The more immediate problem, of course, is that some small but nontrivial minority of the recent immigrants to Europe are openly contemptuous of the liberal, democratic, pluralistic values that allowed them to settle there in the first place. We see this, for example, in the thousands of European Muslims—many of them second- or third-generation—who flocked to Iraq and Syria to join ISIS and partake in its divinely-sanctioned rapes and murders. We also see it in the systematic rape, enslavement, and torture of thousands of teenage British girls in Rotherham and elsewhere in England (England!) over nearly two decades. The horrific details—including the Labour politicians who refused parents’ pleas to crack down on the Pakistani sex-trafficking rings because doing so might be seen as racist—have to be read to be believed. This is to say nothing, of course, of the honor killings and other violence inflicted by European Muslims on other Muslims, as the timid authorities have looked the other way.

Many of my fellow liberals, it seems to me, are callously indifferent to the human costs of these realities on the ground, for the wretched, dishonorable reason that “they seem like the sort of things that fit into the Right’s narrative.”

There’s a general principle at stake here, which is inarguable when stated explicitly, but which can’t be stressed enough: the fact that racist xenophobes are concerned about some issue, does not imply that the issue isn’t real, or that everyone else is morally obliged to ignore the issue merely in order to spite the xenophobes. It’s to Western liberals’ eternal shame that so many of them today seem more exercised about a scintilla of possible residual racism or sexism in a nerdy white male scientist, detected via electron microscope, than they are about the men who are right now gleefully raping and enslaving teenage girls by the thousands under the banner of God.

Indeed, something stronger is true: the more my fellow liberals refuse to address these sorts of problems, or even acknowledge their existence, the more they cede the field by default to the right-wing xenophobes, and thereby inadvertently strengthen the right among the broader public. I’ve noticed this liberals-shooting-themselves-in-the-foot dynamic in many other cases. For example, if you’re angry about the blatant misogyny of the “pickup artists” and “red-pillers” and “manospherians,” it would seem obvious that the right way to drain that particular swamp is to offer better solutions to the problems that they’re trying to address. But somehow, all we hear from the social-justice side are ever-more-deafening claims that any nerdy males with social-anxiety issues must be entitled neckbeard virgin shitlords living in their parents’ basements—with the shamers evidently failing to grasp that all they’re accomplishing for their trouble is to drive the nerds into the arms of the red-pillers, by proving to the terrified nerds the red-pillers’ basic contention that the other side will despise them no matter what, and that therefore the nerds have nowhere else to turn.

So, OK, what’s to be done about Europe’s immigration crisis? While I obviously can’t pretend to any special expertise, it seems clear to me that a humane approach would involve two basic ingredients. First, the more insular immigrant communities that are already in Europe need to be inculcated in modern liberal-democratic values, starting in the schools at an early age. Crucially, that doesn’t mean abandoning their religion or culture; it just means accepting the basic ground rules of a pluralistic society—just like we rightly demand of American evangelical Christians, and of others liable to believe themselves in possession of a Law that trumps human laws. Secondly, it seems to me that immigration policies could be designed much more intelligently, to favor high-skilled, industrious people of any race or religion who embrace pluralistic democratic values. As a prerequisite, this would mean hiring immigration officers who think less like bureaucrats than like talent scouts and detectives.

Beyond that … well, I don’t know! But I’m thrilled to say that a week from now, one of my heroes, Ayaan Hirsi Ali, will be speaking at MIT, and she’s likely to address exactly these sorts of questions. It’s to MIT’s credit that they’re allowing her to speak at all, at a time when some universities have cancelled her appearances for being too “divisive.” If hearing AHA in person gives me any new thoughts about these difficult questions, maybe I’ll find enough courage to blog about them.

(and here, I’d almost made it through the entire AMA without getting into any real hot water…)
John Sidles Says:
Comment #127 September 7th, 2015 at 7:46 pm
Scott commends (#126) “One of my heroes, Ayaan Hirsi Ali, will be speaking at MIT”

Scott commends (#11) “One of my favorite novels of all time, The Mind-Body Problem by Rebecca Newberger Goldstein.”

Scott deprecates (#126) “Hardened social justice warriors […] who refuse to address these sorts of problems [as cultural integrity in the face of immigration], or even acknowledge their existence.”

It’s a pleasure to agree with Scott that (1) Ayaan Hirsi Ali is a modern-era hero, and (2) Rebecca Goldstein’s books are terrific, and (3) liberals (of every nation) need to face-up more honestly to social justice issues.

Lessons in discourse We can take a lesson from climate-change dialog, by seeking out (what we individually conceive to be) the strongest social-justice literature … not the weakest!

Evolving ideals Fortunately Hirsi Ali and Goldstein stand ready to help us, first with Hirsi Ali’s opinion-piece in The Washington Post, titled “The Islam reformers vs. the Muslim zealots” (March 27, 2015), which draws upon her most recent book Heretic: Why Islam Needs a Reformation Now (2015) to assert the desirability and feasibility of reform Islam. For this advocacy Hirsi Ali is being vigorously assailed on all sides … not least by hard-line opponents of reform Christianity and reform Judaism.

Spinoza’s path Readers of Rebecca Goldstein’s Betraying Spinoza: The Renegade Jew Who Gave Us Modernity (2009) will be saying to themselves “Hmmmm … Hirsi Ali is treading very much the same path as Baruch Spinoza” … which indeed is an isolating and even physically hazardous path.

Further reading For broad historical perspectives on Spinoza’s path (and hence Hirsi Ali’s path), Shtetl Optimized readers would do well to look beyond Goldstein’s account — Goldstein is a novelist, not a historian — to the more scholarly accounts of historians like Jonathan Israel and Leszek Kolakowski.

Generally speaking, Kolakowski’s accounts of the origins of Spinozism are shorter, livelier, more broad-ranging, and rather more controversial than Israel’s. Particularly commended to under-represented Christian Shtetl Optimized readers Gene Chase (#7) and RubeRad (#125) are Kolakowski’s essays “The Idolatry of Politics” — which was the NEH’s Jefferson Lecture in the Humanities for 1986 — and “Dutch seventeenth-century non-denominationalism and Religio Rationalis: Mennonites, Collegiants and the Spinoza connection” (2004).

Conclusion When Baruch Spinoza sought shelter for his physical person and for his radical (and still-evolving) ideas, the seventeenth-century Dutch Mennonites and Collegiants bravely sheltered both. Kudos to the modern-day Dutch for sustaining this tradition, by providing shelter to the person and to the radical (and still-evolving) ideas of Ayaan Hirsi Ali.

Correlations It’s unsurprising that welcome of immigrants and celebration of liberal ideals alike are correlated to the number and vigor of a nation’s Spinoza Societies … the Middle East in particular stands in need of them.
Alex B. Aible Says:
Comment #128 September 7th, 2015 at 8:53 pm
Scott #112:

What I believe at this point is that neither Cantor himself nor any of his adherents (to include Scott) was aware of the flaw in his argument. (It appears—in the absence of evidence to the contrary—that Cantor set up his proof on an infinite $n$ only to preclude any objection that it might not apply after some limit.) I posted a summary of the counterargument here in the hope that someone would describe either an established or novel way around it. No one, so far, has done so.

I emphatically did not reject the argument on “a priori philosophical” grounds but rather because it simply does not work, not for an $n$ of any size, finite or infinite. In fact, there are “mainstream” Infinitists who do not believe that finite logical processes suddenly change when we “reach” infinity—I have never heard anyone claim that after “enough” finite iterations 2 + 2 = 7—and I surely believe the counterargument, as a finite logical process, does not change either.

Of course, I realize that the counterargument will not become part of any canon (except the one which is permanently aimed at the heads of “amateur crackpots” like myself) but if anyone is interested in reading the actual article, it can be found on the rarely viewed “Alex Aible’s blog.”

Thanks,

Alex
John Sidles Says:
Comment #129 September 7th, 2015 at 9:27 pm
As a followup to (#127), I have just added to my BibTex database, under the keyword “heresy”, Ayaan Hirsi Ali’s outstanding article (as it seems to me) in this month’s Foreign Affairs:

A Problem From Heaven: Why the United States Should Back Islam’s Reformation

Like Christians and Jews centuries ago, Muslims today must critically evaluate their sacred texts in order to reform their religion. That is not an unreasonable request, as history shows. Of course, history also shows that the path to religious reform can be bloody.

By the mid-seventeenth century, Europe had been ravaged by a century of warfare between Roman Catholics and Protestants. But the result was to create the room for the genuine freedom of thought that ultimately made the Enlightenment possible.

One of the most important of these freethinkers was Baruch Spinoza, a brilliant Jewish Dutch philosopher. For Spinoza, the Bible was a collection of loosely assembled moral teachings, not God’s literal word.

Spinoza was excommunicated from the Jewish community, and a council of the Dutch Reformed Church called his Theological-Political Treatise “the vilest and most sacrilegious book the world has ever seen.” One of Spinoza’s contemporaries, Adriaan Beverland, was even jailed and then banished from the provinces of Holland and Zeeland for questioning the notion of original sin.

Yet both men died in their beds. And it is their ideas that prevail in the Netherlands today.

Two conclusions (1) It’s good to see Ayaan Hirsi Ali’s increasing appreciation of the historical roots of her struggle. (1) It’s dismaying that Hirsi Ali’s article shows no historical appreciation that Spinoza’s chief patrons and protectors, the brothers Johan de Witt and Cornelis de Witt, did not “die in their beds,” but rather were torn limb-from-limb and cannibalized (yikes!) by a Dutch mob of right-wing royalists.

Is it any wonder that Spinoza’s works were published clandestinely, and that his seal-ring said caute (latin for “caution”)?

Personal note Once upon a time, playing “hooky” from an American Chemical Society meeting in Washingon DC, I traveled to the nearby Library of Congress, acquired a library card, presented myself to the librarians as a Spinozist, and (having done my homework beforehand, so as to know which volumes to request) was granted access to Thomas Jefferson’s personal copies of Spinoza’s (then-banned) Opera Posthuma, with a view to inspecting these works for marginalia.

Alas, it eventuated that Jefferson was disinclined to mark-up Spinoza’s then-scarce volumes (except for writing his name on the title pages).

None-the-less, the librarians were thrilled to have a scholarly reason to touch Jefferson’s personal books … as was I.
Anonymous85 Says:
Comment #130 September 7th, 2015 at 11:00 pm
Alex Aible: What do you think Cantor’s argument is trying to show? Can you state in your own words what we’re even talking about?

(I tried to understand your counterargument, but ran into the problem that I didn’t know what you’re trying to argue against, because there are several different ways to present Cantor’s proof.)

One way of stating Cantor’s theorem is simply saying that there is no bijection between a set and its power set. This theorem is true for finite sets as well; there’s no special rule that applies only to infinite sets.

Do you agree that there’s no bijection between a finite set and its power set?
jemand Says:
Comment #131 September 8th, 2015 at 7:30 am
Thinking about people from Mexico or south of that who want to immigrate to the US: Are there “democratically adopted legal immigration policies” or “immigration officers who think less like bureaucrats than like talent scouts and detectives”?
Ronald de Wolf Says:
Comment #132 September 8th, 2015 at 10:47 am
Re John Sidles, comment#129: the lynching of Johan and Cornelis de Witt by a royalist mob had nothing to do with Spinoza and very little to do with religious disagreements. It was part of the power struggle between the royalists (Orangists) and the more republican burghers. The de Witt brothers were blamed (scapegoated) for the disastrous war of 1672 when the Netherlands were nearly overrun by a joint attack from France, Britain, Munster and Cologne.
Callous Liberal Says:
Comment #133 September 8th, 2015 at 11:35 am
It’s become an accepted truth that the appalling abuse scandals in the UK (where I live), such as those in Rotheram, were untackled for so long “because doing so might be seen as racist”.

For what it’s worth, my suspicion is that the problem was at least as much one of the authorities failing to treat seriously complaints coming from very damaged and disadvantaged (and thus very unreliable) children, as it was one of them turning a blind eye to what Muslim men were getting up to. (A quick look at e.g. UK prison population statistics shows that the police do not, in general, have a tendency to ignore Muslim criminality.)

Once the scandal came to light, it’s actually quite convenient for the authorities to frame the ensuing discussion around “the all-pervading awfulness of political correctness” rather than “our complete incompetence”.
Scott Says:
Comment #134 September 8th, 2015 at 11:40 am
jemand #131: Yes, the US does have a more-or-less democratically-adopted legal immigration system. (My wife, Dana, was just naturalized as a US citizen last week, after waiting 5 years, filling out like 300,000 forms, getting blood tests, paying fees, and then passing an absurdly easy test about American history, geography, and government.)

On the other hand, pretty much everyone in the US, of every political persuasion, agrees that our immigration policies badly need reform, they just disagree about how and in which direction. 🙂

I guess I’m with the majority of Americans who think that any comprehensive reform plan ought to include a path to assimilation, amnesty, and citizenship for the millions of undocumented immigrants who are already here, but also tighter controls to disincentivize further illegal immigration. I also believe it would be economically wise to actively recruit people with strong technical skills to the US, and that getting a visa, a green card, and then citizenship should be made as fast and easy as possible for them. Having recently seen the process firsthand, I can assure you that that’s not currently the case.

Now, regarding the ‘illegals’: one should note that, outside the fantasies of Donald Trump, almost all of them come to the US to work very hard jobs for little pay and to support their families. They have no clear ideological equivalent to radical Islamism, which could be exploited to justify violence against the host country. And then, of course, there’s the point that, out of all ethnic groups, they’re among the genetically closest to the original inhabitants of what’s now the US.
jonathan Says:
Comment #135 September 8th, 2015 at 12:25 pm
Scott:

I guess I’m with the majority of Americans who think that any comprehensive reform plan ought to include a path to assimilation, amnesty, and citizenship for the millions of undocumented immigrants who are already here, but also tighter controls to disincentivize further illegal immigration.

Isn’t this inconsistent? i.e. if it is wrong to deport people already here, why is it not wrong to prevent further immigration? And if it is right to prevent further immigration, why is it not also right to deport those already here?
John Sidles Says:
Comment #136 September 8th, 2015 at 12:41 pm
Reflections upon Ronald de Wolf’s comment #132 …

——
Dismal questions The question “Why were Johan and Cornelis de Witt lynched?” is intricately entangled with a dismal class of questions that includes “Why was Socrates executed?” and “Why was Jesus martyred?” and “Why was Lincoln assassinated?” and “Why was Martin Luther King assassinated”, extending all the way to “Why were Theo van Gogh, Naji Salim al-Ali, and the Charlie Hebdo cartoonists assassinated?”.

Dismal conclusions On purely phenomenological grounds, we can conclude that “In all cultures and epochs, it’s mighty dangerous to espouse peaceful actions that are grounded in radical philosophical ideas and radical political reform.”

The futility of the Enlightenment Not only is this advocacy very dangerous, it can be (even worse?) politically futile, as Spinoza admirers Albert Einstein and David Ben-Gurion alike discovered

On Spinoza’s Ethics
by Albert Einstein [*]

How I love this noble man
More than I can say with words.
Still, I fear he remains alone
With his shining halo.

Such a poor small lad
Whom you’ll not lead to freedom
The amor dei leaves him cold
Mightily does this life attract him

Loftiness offers him nothing but frost
Reason for him is poor fare
Property and wife and honor and house
That fills him from top to bottom

You’ll kindly forgive me
If Münchhausen here comes to mind
Who alone mastered the trick
Of pulling himself out of a swamp by his own pigtail

You think his example would show us
What this doctrine can give humankind
My dear son, what ever were you thinking?
One must be born a nightingale
Trust not the comforting façade
One must be born sublime

[*] Note Rebecca Goldstein gave a lecture on this poem, titled “Why Did Einstein Write a (Bad) Love Poem to Spinoza?”. But it’s not such a bad poem, is it? Perhaps Goldstein would do well to reflect upon Pope’s maxims:

“Those oft are Stratagems which Errors seem,
Nor is it Homer Nods, but We that Dream.”

and

“Some people will never learn anything, for this reason, because they understand everything too soon.”

and even the Quaker maxim

“If there is neither vision to create unrest, nor spiritual power to communicate unrest to others, the inner light must be moonlight.”

Summary The ongoing struggle against terror and terrorism is intimately entangled with ongoing struggle — now in its fourth century — of the “Radical Enlightenment” against the “Moderate Enlightenment” (to use Jonathan Israel’s terms).

Conclusion Peace workers like Ayaan Hirsi Ali, who presently accept patronage and protection from agencies of the Moderate Enlightenment, have to consider whether their evolving commitment to peace is calling them instead (and calling the public too) to the performatively Spinozist agenda of Radical Enlightenment.

More broadly, can we advocate a radically reformed Islam, without calling too, for completion of the radical reforms of Christianity and Judaism, that were so effectively advocated by the seventeenth century Mennonites, Collegiants, and Spinozists (per #127)? This is a mighty tough question for moderately enlightened agencies and their moderately enlightened supporters.
Questions Says:
Comment #137 September 8th, 2015 at 12:47 pm
“Isn’t this inconsistent?”

Yeah, and what is your point exactly? Consistency matters here? Why?
Scott Says:
Comment #138 September 8th, 2015 at 12:52 pm
jonathan #135: I agree that it’s a difficult moral question, and maybe the distinction makes more sense under (neo-)Kantian than utilitarian ethics. For me, though, the decisive consideration is that deporting the people who are here would involve perpetrating a grievous harm against millions of children who have already grown up in the US as ‘Americans,’ and who bear no responsibility for their parents’ decision to come here illegally.

By analogy, I know people who think that the state of Israel should never have been founded, but who agree that now that it exists, it would be extremely wrong to destroy it. And of course, there are many, many people who think the US should never have been taken from the Native Americans, but that now that it was, destroying the US and expelling all the non-Native inhabitants is an inappropriate remedy. Regardless of whether one agrees or disagrees with these positions, they strike me as intellectually consistent.
TeenWolf Says:
Comment #139 September 8th, 2015 at 1:52 pm
I looked at your paper. Seems like P=PSPACE is a possibility since CTCs could exist. There is nothing like that for NL=PSPACE. right?
Scott Says:
Comment #140 September 8th, 2015 at 2:24 pm
TeenWolf #139: Even if CTCs existed, it wouldn’t mean P=PSPACE. It would “merely” mean that, under my and Watrous’s assumptions, the physical world could efficiently solve PSPACE-complete problems (not that the complexity class P could solve them).

NL≠PSPACE is a proven theorem, which follows by combining Savitch’s Theorem (PSPACE=NPSPACE) with the Nondeterministic Time Hierarchy Theorem (which implies NL≠NPSPACE).

And sorry, but I’m not taking any more questions!
jemand(#131) Says:
Comment #141 September 8th, 2015 at 2:54 pm
Thanks for your quick answer (#134). My question was meant also in the direction: Fences – bad, but necessary? Many in Europe demand them. Some say its pure egoism.
HoS Says:
Comment #142 September 8th, 2015 at 6:47 pm
I feel like I need to stand up for Walden Pond here! You knew that someone would very deliberately ignore your directive, right?

I took a red-eye from CA to Boston several years ago, and took a rental car from the airport straight to Walden. It was quite early in the morning and it was a Friday I believe, but it was just wonderful. I had no idea people swam there, but had fortunately packed a swimsuit. Floating in the middle of the pond, with some birds landing near me occasionally was a memorable, unexpected experience. Walking around afterwards on a sunny August morning was terrific as well.

I was there again in October of last year. No swimming this time, but the fall colors were amazing. (Yes, I did realize both times that strange parking rules were posted, but was not personally impacted.)

Sorry to hear about Lily’s disappointment, and Thoreau must be laughing in his grave, no doubt, but you are a local, go on a weekday next time Scott! Alternatively, there are so many ponds around there, you guys should just use a different one. Thoreau would understand.

Btw, I am female and not-white and love math(s) and work as a researcher/engineer and am a regular reader, but am evidently too late to ask a question. Next time.
Alex B. Aible Says:
Comment #143 September 8th, 2015 at 8:02 pm
Anonymous85 #130:

My counterargument is directed only at Cantor’s diagonalization argument, and I will summarize this counterargument in my own words for you yet again.

Cantor shows that he can always create a $n$ by $n$ matrix whose rows consist of $n$ distinct binary numbers $p$ of length $n$ in such a way that there is a diagonal occupied by a distinct binary number $p$ of length $n$ that is not present in any row of the matrix, so there is no bijection between the rows of the matrix and the set of natural numbers. Fine.

However, the complete set of distinct binary numbers $p$ of length $n$ can only be contained in a set of $2^n$ by $n$ matrices, none of which has a diagonal but each of which necessarily consists of a set of $n$ by $n$ matrices—and a non-empty proper subset of these $2^n$ by $n$ matrices must contain the $n$ by $n$ matrix where Cantor has established his diagonal.

So what can Cantor do now? If he does nothing, then there is a bijection between the set of rows of every member of the set of $2^n$ by $n$ matrices and the set of natural numbers (which, it can be assumed, he does not want). If he actually flips the diagonal of his $n$ by $n$ matrix (for whatever reason), then he creates a redundant row in the $2^n$ by $n$ matrix that contains his $n$ by $n$ matrix, so that there is (duh!) no bijection between the set of rows of the corrupted $2^n$ by $n$ matrix and the set of natural numbers.

Either way (or so it seems to me), the exercise adds up to nothing.

Alex
Anonymous85 Says:
Comment #144 September 8th, 2015 at 8:39 pm
Alex Aible:

That’s not Cantor’s argument; Cantor never creates a matrix, he shows you that *any* n by n matrix you provide will not contain all numbers of length n. This is actually a trivial statement when n is finite; of course you can’t use only n rows to list out all numbers of length n, because there are 2^n such numbers! (Or 10^n, if you’re working in base 10). As you correctly note, you can indeed list out all numbers of length n using 2^n rows. But that’s not really relevant to Cantor’s proof.

Anyway, what I asked you is not what you think Cantor’s argument is, it’s what you think Cantor is trying to prove. In mathematics, we make a clear distinction between a statement and its proof. You keep contesting the proof, but my question is: what is the statement? What are we trying to prove or disprove here?
D J W Says:
Comment #145 September 8th, 2015 at 9:16 pm
Alex Aible: Perhaps an example-based presentation of Cantor’s theorem might help.

Theorem: Any mapping f: S -> P(S), from the elements of a set S to subsets of S, must miss (fail to map to) at least one subset of S.

The proof is the cute observation that the set X_f = {all s in S such that s is not a member of f(s)} is one such missed subset. It might not be obvious that X_f must be a missed subset, so let’s try some examples. As Anonymous85 mentioned, it has no dependence on the finiteness or infiniteness of S.

—————————————————————————————
Let’s apply it to S = {1,2,3} and the mapping:

f: 1 -> {1}, 2 -> {2}, 3 -> {3}

Then if you work it out, X_f = {}, which indeed is a subset of S that f does not hit.
—————————————————————————————
Now let’s alter the mapping to hit {}, and see what the theorem gives us then. Say:

f: 1 -> {}, 2 -> {2}, 3 -> {3}

Then X_f = {1}. Which is indeed a subset of S missed by the new f.
—————————————————————————————
Let’s try adding that back in while keeping {}. Say:

f: 1 -> {}, 2 -> {1}, 3 -> {3}

Then X_f = {1,2}, which is again missed by the new new f.
—————————————————————————————
Let’s do an infinite set. Say S = the positive integers and f(s) = {s}, that is:

f: 1 -> {1}, 2 -> {2}, 3 -> {3}, 4 -> {4}, …

Then X_f = {}.
—————————————————————————————
Now let’s add that in, but *without* replacing anything else, by shifting everything over:

f: 1 -> {}, 2 -> {1}, 3 -> {2}, 4 -> {3}, …

Then X_f = {1,2,3,4,…}.
—————————————————————————————
So let’s add that in too, shifting everything over again.

f: 1 -> {1,2,3,4,…}, 2 -> {}, 3 -> {1}, 4 -> {2}, …

Then X_f = {2,3,4,….}.
—————————————————————————————
The point is that given a mapping from elements to subsets, this is a completely mechanical way to construct an subset missed by the mapping. So any mapping from elements of a set to subsets of that set must miss at least one subset. And that’s all that Cantor’s theorem claims.
Dan Haffey Says:
Comment #146 September 8th, 2015 at 9:57 pm
Tony #16: Eureqa is a notable project along those lines.
Alex B. Aible Says:
Comment #147 September 8th, 2015 at 10:14 pm
Anonymous85 #144:

Go to Wikipedia and type “Diagonalization Argument” in the search bar. The article should answer most of your questions.

Alex
Anonymous85 Says:
Comment #148 September 8th, 2015 at 11:04 pm
Alex Aible:

Based on the wikipedia article, it seems the statement you disagree with is

“Let T be the set of all infinite sequences of binary digits. Then there is no bijection between T and the set N of natural numbers.”

Is this correct? If so, can you please provide a bijection between T and N?
yme Says:
Comment #149 September 9th, 2015 at 12:10 am
Alex B. Aible #147:

How will reading a Wikipedia article (presumably not written by you) help us learn what you think Cantor is trying to prove?

I know what I think he’s trying to prove. But I also think that he succeeds in proving it. You don’t. One possible reason for this difference of opinion is that we don’t even agree about what he’s trying to prove. So it would be helpful if you answered the question yourself, rather than referring us to Wikipedia.
John Sidles Says:
Comment #150 September 9th, 2015 at 3:08 am
Dick Lipton’s weblog Gödel’s Lost Letter and P=NP has discussed Cantor’s diagonal proof upon at least three occasions:

• “Cantor’s Non-Diagonal Proof” (April 18, 2009)
• “Are The Reals Really Uncountable?” (January 20, 2010)
• “Does Cantor’s Diagonalization Proof Cheat?” (June 11, 2010)

Executive summary The short answers to the latter two questions amount to “yes” and “no” … still there is plenty more to be said.

Infinite jests Lipton provides a link to a cogent-yet-hilarious essay by the logician WIlliam Hodges that begins:

I dedicate this essay to the two-dozen-odd people whose refutations of Cantor’s diagonal argument have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments.

A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument — what had it done to make them angry with it?

So I started to keep notes of these papers, in the hope that some pattern would emerge. These pages report the results.

Further reading Shtetl Optimized readers who enjoy Hodges’s essay and Lipton’s GLL essays — who enjoy in particular the good-humored historical, cultural, and philosophical contexts that Hodges’ and Lipton’s essays provide — will find much to enjoy too in Michael Harris’ recent book Mathematics Without Apologies (2015).
Callous Liberal Says:
Comment #151 September 9th, 2015 at 4:34 am
“Cantor shows that he can always create a $n$ by $n$ matrix whose rows…”

No he doesn’t. Back to Wikipedia for you!
Giorgio Camerani Says:
Comment #152 September 9th, 2015 at 6:32 am
Unfortunately I’ve discovered this new AMA only now.

Since the previous AMA (which I discovered later as well) I wanted to ask you how strongly you believe in the ETH (same strength as P != NP or less?).

I’ll wait the next AMA to know the answer (can I book for it, in order to avoid the risk of arriving later for the 3rd time?).
jonathan Says:
Comment #153 September 9th, 2015 at 8:40 am
An amusing note on Cantor’s argument that I just thought of:

Suppose that the diagonal of the list of numbers is 0.99999…., and that this is also one of the numbers on the list. Now add 1 to each digit in the diagonal number to obtain 1.00000…

But since 1 = 0.99999…, this number is already on the list!
fred Says:
Comment #154 September 9th, 2015 at 8:49 am
John #150

sadly, my struggles with Cantor’s proof type of issues is even more fundamental.

Doesn’t the manipulation of real numbers implicitly require infinite resources in general?
Some reals can be described in a compact manner (pi, e, 0.9999…), but most of them would require an infinite amount of memory to describe, no?
Similarly, even just subtracting (sorting) two reals seems to require a program that never terminates, in general.

Then I don’t understand why it seems okay to brush all this under the rug with “sure, subtracting two reals could take an infinite amount of time, but let’s assume we can do it”, but it’s not okay (*) to say “sure, figuring if a program ever halts could take an infinite amount of time, but let’s assume we can do it”?
In other words, it seems to me that once you assume you’re using real numbers as a tool, the implicit processing power necessary would let us do the very type of things Cantor/Godel/Turing want to disprove.

(*) maybe some branches of complexity theory do assume this, I’m not sure.
David B Says:
Comment #155 September 9th, 2015 at 10:53 am
Sorry about your Walden experience. As Yogi Berra said, “Nobody goes there anymore, it’s too crowded.”
yme Says:
Comment #156 September 9th, 2015 at 11:28 am
fred #154: “Doesn’t the manipulation of real numbers implicitly require infinite resources in general?”

Yes.

But where do you think it’s being swept under the rug?

Cantor’s argument just shows that, for every list of real numbers, even an infinitely long list, there exists a real number not on it. That’s not the same as saying that it’s possible, in practice, using only a finite amount of memory and time, to work with an infinitely long list of real numbers, and to construct a real number not on it.

So, it’s not really like saying, “let’s assume we can determine whether an arbitrary program halts or not”. It’s more like saying, “let’s assume that every program either does or does not halt, even if we can’t always determine which is the case”.
Scott Says:
Comment #157 September 9th, 2015 at 11:33 am
Giorgio #152: Alright, I’ll answer, since you’ve been waiting a long time and your question has a straightforward answer.

Yes, I believe ETH (and I’ve used it as a hardness assumption in two papers), but not with anywhere near the strength of conviction that I believe P≠NP. If a 2^O(√n) algorithm for 3SAT were discovered tomorrow, I would still conjecture that P≠NP.
Scott Says:
Comment #158 September 9th, 2015 at 11:58 am
jonathan #153: Yes, the fact that 0.9999…=1 is a well-known complication in the proof that the reals are uncountable; see Wikipedia for some standard ways of getting around it. This is why it’s a bit simpler to prove the version of Cantor’s theorem stating that the set of sets of positive integers is uncountable.
Giorgio Camerani Says:
Comment #159 September 9th, 2015 at 12:28 pm
Scott #157: Thanks for answering! Recently, I was partially surprised to learn that Ryan Williams believes SETH is false (http://www.imsc.res.in/~vraman/exact/ryan.pdf).
John SIdles Says:
Comment #160 September 9th, 2015 at 12:33 pm
Fred #150, you will find in Wilfred Hodges’ article “An editor recalls some hopeless papers“ (Bulletin of Symbolic Logic 1998, as cited in Dick Lipton’s essays of #150) the following lucid discussion of the foundational points that you raise:

This may be the moment to mention a passage in Wittgenstein’s book Remarks on the Foundations of Mathematics [1956], where he claims (if I follow him right) that Cantor’s argument has no deductive content at all.

The theme of Wittgenstein’s book is that mathematical statements get any meaning they may have from rule-governed activities that involve them. He singles out Cantor’s argument because it would appear to have no relation to any imaginable activity.

Except for one, namely the activity of writing out lists of complete decimal expansions of real numbers. This is of course a daft activity, doomed to failure. Ah, says Wittgenstein, that’s what Cantor’s theorem must amount to:

Surely—if anyone tried day-in day-out ‘to put all irrational numbers into a series’ we could say: “Leave it alone; it means nothing; don’t you see, if you established a series, I should come along with the diagonal series!”

This might get him to abandon his undertaking. Well, that would be useful. And it strikes me as if this were the whole and proper purpose of this method. It makes use of the vague notion of this man who goes on, as it were idiotically, with his work, and it brings him to a stop by means of a picture.

None of our authors showed any knowledge of Wittgenstein’s critique, or any sympathy with it.

Wittgenstein’s analysis, and Hodges’ sympathetic discussion of it, illuminates attempts “to bring to a stop” activities as various as peace-making, philosophizing, slave-freeing, rights-asserting, gender-equalizing, and even D-Wave-praising.

These “halting attempts” are both effective and illuminating when they conducted with the gentle humor and acute scholarship that Wilfred Hodges’ essay so admirably exemplifies.

Conversely, when halting attempts (of any kind) rely upon less friendly methods, ranging from cherry-picking, sardonicism and abuse, all the way to exile, imprisonment, torture, execution, and terror, then the inspiring lesson of history (per my comments #72,103,127,129,136) is that halting attempts are futile (in the long run if not always in the short run).

Conclusion A very great virtue of Shtetl Optimized has been to serve as a forum in which quantum optimists and skeptics can each collegially persuade the other of the futility of their respective faiths. On the grounds that (as seems to me nearly certain) both faiths are producing plenty of good research, we can be glad that the practice of collegiality burns no bridges, but rather continually cultivates the best efforts and best arguments of all academic faiths.

Confection Literary-minded Shtetl Optimized readers will find these themes warmly echoed in the “Benny Russell” episodes of the TV series Deep Space Nine.
Jay Says:
Comment #161 September 9th, 2015 at 12:40 pm
yme, would you agree that we shall modify your statement for “for every *countable* list…”
Greg Kuperberg Says:
Comment #162 September 9th, 2015 at 1:14 pm
There is a weaker version of (strong) ETH that is easier to believe: That there are CircuitSAT problems with n inputs and poly(n) gates, that can only be solved with Omega(2^n) classical work, basically nothing better than exhaustive search. However, what makes ETH interesting is its reducibility properties, and this more conservative version is rather less interesting in this respect.
TeenWolf Says:
Comment #163 September 9th, 2015 at 1:55 pm
@Scott 157
I think there are NP complete problems with complexity $2^{\sqrt{n}}$.
Scott Says:
Comment #164 September 9th, 2015 at 1:58 pm
TeenWolf #163: Yes, it’s easy to construct such problems by padding. The ETH says that 3SAT requires 2^Ω(n) time (and as a consequence, that hundreds of other “natural” NP-complete problems do)—not that all NP-complete problems require 2^Ω(n) time.
Jay Says:
Comment #165 September 9th, 2015 at 2:09 pm
Greg, isn’t that trivial unless one restrict the set of gates allowed for CircuitSAT?
Sniffnoy Says:
Comment #166 September 9th, 2015 at 2:16 pm
fred #154:

You’re conflating different notions of “can be done”.

Turing showed that there is no algorithm for telling you whether a given Turing machine halts on a given input or not; it “can’t be done” in that sense. However, that doesn’t mean there is no fact of the matter about whether a given Turing machine halts on a given input or not; we can still talk about the result, even if for a particular case we can’t determine it. (And, indeed, some computer scientists do study “infinite-time Turing machines”.)

Similarly with real numbers — no, you can’t store one in a computer; the idea of adding two algorithmically therefore doesn’t even quite make sense. But that doesn’t mean we can’t consider them, and say that yes, there is a fact of the matter about the sum of these two given real numbers, regardless of whether it’s something we can compute.
yme Says:
Comment #167 September 9th, 2015 at 2:21 pm
Jay #161:

Yes, certainly.

I said “list”, unqualified, because it seems to me that the informal idea of a list doesn’t include uncountable sets. I figure that most people think of a list as being the sort of thing that has a first item, a second item, a third item, etc.
TeenWolf Says:
Comment #168 September 9th, 2015 at 3:18 pm
Scott 163 you are being silly there. Check PalGD’s answer here http://cs.stackexchange.com/questions/9813/are-there-subexponential-time-algorithms-for-np-complete-problems

3SAT is special

Padding is not necessary since there are natural problem classes
Scott Says:
Comment #169 September 9th, 2015 at 3:33 pm
TeenWolf #168: Thanks for the link, but I never said there were no natural subexponential examples. Certainly, if ETH holds, then many “natural” NP-complete problems (not all of them) require 2^Ω(n) time. In particular, this includes anything that you can reduce 3SAT to via a reduction with linear blowup.
fred Says:
Comment #170 September 9th, 2015 at 3:54 pm
Sniffnoy #166
Thanks!
TeenWolf Says:
Comment #171 September 9th, 2015 at 4:31 pm
Also for $NL\neq PSPACE$, I was actually thinking there may be a physical obstruction that may explain
fred Says:
Comment #172 September 9th, 2015 at 4:32 pm
Sniffnoy #166

About considering an infinite number of steps as a useful abstraction, there’s also the Zeno paradox (still the source of a lot of debates it seems), but I’m not clear if there’s any useful connection to Cantor’s proof and such.
From the wiki:

“This presents Zeno’s problem not with finding the sum, but rather with finishing a task with an infinite number of steps: how can one ever get from A to B, if an infinite number of (non-instantaneous) events can be identified that need to precede the arrival at B, and one cannot reach even the beginning of a “last event”?”

But I guess no-one really knows whether this tells us anything about moving from point A to point B in “real” physical space, or whether motion in a discrete medium is any less mysterious than motion in a continuum. 🙂
Alex B. Aible Says:
Comment #173 September 9th, 2015 at 10:40 pm
Anonymous85 #148:

This is an expanded summary of my objection to the argument:

1. The complete set of distinct binary numbers $p$ of length $n$ can only be contained in a $2^n$ by $n$ matrix.

2. The rows of such a $2^n$ by $n$ matrix can be arranged in any linear order, so there exists a set $O$ of such arrangements that contains $2^n$! distinct members.

3. There can only be a diagonal of length $n$ in an $n$ by $n$ matrix.

4. Every $n$ by $n$ matrix that contains $n$ of the given $p$ must be a component of a non-empty proper subset of the members of $O$.

5. It is not possible to formulate a valid thesis about the consequences of the existence of a diagonal of an $n$ by $n$ matrix that contains a $p$ that is not present in the rows of the $n$ by $n$ matrix unless we assume the $n$ by $n$ matrix is a component of a member of $O$.

6. For the diagonalization argument to succeed, it must demonstrate that there is no injective function from the set of rows of at least one uncorrupted member of $O$ and the set of natural numbers.

7. The diagonalization argument fails to do this because:

A. If we do not flip the diagonal of an $n$ by $n$ component of a member of $O$, there is a bijection from the set of rows of this member of $O$ and the set of natural numbers.

B. If we do flip the diagonal of an $n$ by $n$ component of a member of $O$, we corrupt this member of $O$ by reducing the number of distinct $p$ that it contains.

I would like to know the answers to the following questions from those who support the argument:

1. Can we suppose that the argument fails when $n$ is an element of “big $N$” but succeeds when $n$ is infinite? If so, what is the reason?

2. If the argument succeeds because $n$ is infinite, then exactly what role does Cantor’s construction (i.e., of the diagonal of an $n$ by $n$ matrix that contains a $p$ that is not present in the rows of the $n$ by $n$ matrix) play in the result?

Alex
Ajit R. Jadhav Says:
Comment #174 September 10th, 2015 at 2:14 am
Scott # 78:

Hmmm… Looks like you fully qualify to be an Indian. …. You eat mediocre food; talk, argue and sometimes even philosophize. You don’t do any regular physical exercises; don’t mind developing a pot belly right in the 30s (or at least don’t find it so disconcerting that you will immediately hit a gym); and you are a dad. Further, your views often align with those of the Democrats; you like mathematics but work in computer science; and you plan to remain in the USA. … What more could anyone possibly ask for? … In fact, you *are* an Indian.

–Ajit
[E&OE]
Aviti Says:
Comment #175 September 10th, 2015 at 8:11 am
Nicholas #21 and Scott #28, “about food wastage”
I think there is a big problem particularly in peoples` minds about what is good to eat and what not. This leads to supermarkets always overstocking, and people`s behavior of buying only the section which is full. [Actually, that one is easily observable in your local supermarket, wherever you are, and I lifted that from some youtube documentary about food wastage].
Another angle is food wasted in the farm. Think about third world countries: large percentage of food produced goes to waste before reaching the market due to poor infra. This is also exacerbated by lack of simple food processing industries. For example, at the moment I live in a first world country. I can get first rate fruits at an expensive price. But I know that in my country (third world), similar fruits are rotting in the farm for want of infra. People toiled to care for the plant, and they cannot get a return for want of selling.
I also second the idea given by Scott #28. That, different portions to cater for different needs. That idea of electronic pre-ordering is cool.　Except that, who will deal with the chaos in the supply and demand satisfaction? I can see, there is a possibility to hike costs with this procedure. But maybe this is just my tired mind refusing to see the solution to this.
By the way, this AMA is so cool. I will keep reading all the other responses.
Vitruvius Says:
Comment #176 September 10th, 2015 at 5:00 pm
On the subject of the fantasies of Donald Trump, which you raised in #134, Scott, you may wish to consider this essay by Rex Murphy, one of Canada’s senior public-affairs observers.

Further, you may wish to note that there are no remaining descendants of the “original inhabitants” (as you referred to them in #134) of the US, as they were all replaced c. 1000 to 700 years ago by modern Amerindians, as explained in “The genetic prehistory of the New World Arctic” in Science magazine, as reported in this essay at the BBC.

Of course, that’s just my opinion, you may not, I’ve been wrong before. (And to those Americans opposed to foreigners meddling in their affairs, my apologies.)
James Gallagher Says:
Comment #177 September 10th, 2015 at 5:15 pm
re #110 Scott (may be #109?) re age 40 and academic burn-out.

I think you will get one or two more second-winds, where, armed with much more powerful abilities/experience/knowledge than you had as a younger man, you will have a chance to make major contributions. Einstein was 35 when his greatest work, General Relativity, was published, Schrödinger was 40, Planck was 43. More recently, Yitang Zhang was in his late 50s when he published his remarkable contribution to the Twin-Prime conjecture.

PS. I wonder if you can arrange all the comments posted above about Cantor’s argument in a such way so that along the diagonal you’ll get a consensus
fred Says:
Comment #178 September 11th, 2015 at 8:37 am
DJW #145

“Theorem: Any mapping f: S -> P(S), from the elements of a set S to subsets of S, must miss (fail to map to) at least one subset of S. ”

If there are n elements in S, then you only have n mappings, and obviously that’s not enough to map all the possible 2^n subsets of S, no? (2^n – n subsets are missed)

But I’m not clear how that’s just the same thing as Cantor’s proof.
fred Says:
Comment #179 September 11th, 2015 at 8:58 am
Scott #169

What I still don’t get is that if we consider the 2 problems:

(1) I give you m “unrelated” keys, and you have to find the one that opens a lock
E.g. I give you the m numbers {4,11,293,…45} and ask if 57 is in the set.

(2) I give you n elementary building blocks, and they can be combined to generate 2^n possible keys, and then you have to find the one that opens a lock.
E.g. I give you the n numbers {3, 5, 9,..} and ask if any subset of these sums up to 57.

What N!=NP is saying is that if m=2^n, then (2) is just as hard as (1), i.e. it really doesn’t help that the keys are composed from n sub-elements?
Scott Says:
Comment #180 September 11th, 2015 at 9:33 am
fred #178: In some sense, yes, that’s exactly what P≠NP is saying. But with one important caveat: we know that it can help somewhat that “the keys are composed from sub-elements” (as you put it). For example, we know that 3SAT is solvable in ~1.3ⁿ time rather than 2ⁿ. P≠NP merely says that, for NP-complete problems, the structure isn’t going to help so much as to enable a polynomial-time solution.
Raoul Ohio Says:
Comment #181 September 11th, 2015 at 3:42 pm
MIT is either first or last:

http://arstechnica.com/security/2015/09/mit-is-tops-in-bad-security-at-major-universities/
aviti Says:
Comment #182 September 11th, 2015 at 7:49 pm
undergrad#85, It happened to me 15 years ago. Being an engineerin major, I learnd too few Mathematics. Result is that now almost everything in CS, TCS, Mathematics, Physics passes above my head. I have to learn everything from scratch.
D J W Says:
Comment #183 September 12th, 2015 at 9:21 pm
Fred #177 – You can reason about 2^n versus n for finite sets, but for infinite sets obviously that no longer makes sense. Proving the way above also works for infinite sets, and that’s the entire reason Cantor’s theorem is interesting. It shows that the set of all subsets of S is “larger” than S even if S is already infinite, revealing that there are different “sizes” of infinite sets.

X_f is a missed subset regardless of whether S is finite or infinite – you may like to ponder for yourself why this must be the case, and take a look at the last few examples I gave where S = the positive integers (and hence S is infinite).
Serge Says:
Comment #184 September 16th, 2015 at 6:47 am
Scott #112:

You seem to be adopting Dedekind’s position, that Cantor’s results are all invalid because reasoning about infinite sets is nonsense.

I suppose you meant Kronecker? Dedekind actually discovered the definition of infinite sets. He co-invented set theory with Cantor, whom Kronecker kept bullying by calling him a “corrupter of youth”. Cantor had to spend much of his life in a psychiatric asylum, partly because of Kronecker’s persecution. On the other hand, Dedekind figured among Cantor’s best friends.
Scott Says:
Comment #185 September 16th, 2015 at 7:19 am
Serge #184: D’oh! D’oh! Fixed. My historical apologies to poor Dedekind. My memory is getting worse and worse.