More on this book
Community
Kindle Notes & Highlights
Well, by similar logic one could say that any mathematical proof has to be written on paper, and therefore physics should go below math in the hierarchy. Or one could say that math is basically a field that studies whether particular kinds of Turing machine will halt or not, and so CS is the ground that everything else sits on.
the strange thing is that physics, especially in the form of quantum probability, has lately been seeping down the intellectual hierarchy, contaminating the “lower” levels of math and CS. This is how I’ve always thought about quantum computing: as a case of physics not staying where it's supposed to in the intellectual hierarchy! If you like, I’m professionally interested in physics precisely to the extent that it seeps down into the “lower” levels, which are supposed to be the least arbitrary ones, and forces me to rethink what I thought I understood about those levels.
“supposing you got all the previous lessons right, here's a new test you're still going to fail. Go and learn, my child.”
Wrong claims are a fertile source of research ideas.
Immanuel Kant wrote an entire treatise demolishing it: On the Common Saying: “That may be right in theory but does not work in practice.”
Church–Turing Thesis: “Anything that is efficiently computable in the physical world is computable in polynomial time on a standard Turing machine.”
I would think that any world in which we could solve NP-complete problems efficiently would not look much like our world. For NP-intermediate problems like factoring and Graph Isomorphism,
The holographic bound says, informally, that the maximum number of bits that can be stored in any finite region is proportional to the region's surface area, at roughly the rate of one bit per Planck area, or 1.4 × 1069 bits per meter squared.
Why should the maximum number of bits grow like the surface area, rather than the volume?
A Different Universe.
A nuclear fission reactor is also unlike any naturally occurring system in many ways. What about a spacecraft? Things don't normally use propulsion to escape the earth. We haven't seen anything doing that in nature. Or a classical computer.
Gottesman said, supposing the errors were correlated in such a diabolical fashion and that Nature should undergo so much work to kill off quantum computation, why couldn't you turn that around and use whatever diabolical process Nature employs to get access to even more computational power? Maybe you could even solve NP-complete problems. It seems like Nature would have to expend enormous amounts of effort just to correlate qubits so as to kill quantum computation.
It could be that quantum computing is impossible for some fundamental reason. But I'm still waiting for an argument that really engages my imagination nontrivially. People are objecting to this or to that, but they aren't coming up with some fully imagined, alternative picture of the world in which quantum computing wouldn't be possible. That's what's missing for me, what I keep looking for and not finding.7
Puzzle: If you observe 500 black ravens, what basis do you have for supposing that the next one you observe will also be black?
“computational learning theory.”
If you have 500 ravens, each either white or black, then in principle there are 2500 hypotheses that you have to consider.
Fundamentally, because the universe itself is not maximally complicated. We could well ask why it isn't, and maybe there's an anthropic explanation, but whatever the answer, we accept as an article of faith that the universe is reasonably simple, and we do science.
This is all talk and blather, though. Can we actually see what the trade-offs are between the number of hypotheses we consider and how much confidence we can have in predicting the future? One way we do this was formalized by Leslie Valiant in 1984.
His framework is called PAC learning, where PAC stands for “probably approximately correct.” We aren't going to predict everything that happens in the future, nor will we even predict most of it with certainty, but with high probability, we'll try to get most of it right.
So what's the goal? We're given m examples xi drawn independently from the distribution D, and for each xi, we're given f(xi); that is, we're told whether each of our examples is or isn't grammatical. Using this, we want to output a hypothesis language h such that
This goes against a belief in the Bayesian religion, that if your priors are different then you'll come to an entirely different conclusion. The Bayesians start out with a probability distribution over the possible hypotheses.
You don't need to start out with any assumption about a probability distribution over the hypotheses. You can make a worst-case assumption about the hypothesis (which we computer scientists love to do, being pessimists!), and then just say that you'd like to learn any hypothesis in the concept class, for any sample distribution, with high probability over the choice of samples. In other words, you can trade the Bayesians’ probability distribution over hypotheses for a probability distribution over sample data.
The upshot is that this intuitive trade-off between the compressibility of past data and the predictability of future data can actually be formalized and proved; given reasonable assumptions, Occam's Razor is a theorem.
our goal in science is always to come up with hypotheses that succinctly explain past observations, and thereby let us predict future observations.
An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani, MIT Press, 1994.
if Shor's algorithm doesn't involve these “parallel universes,” then how is it factoring the number?2 Where was the number factored, if not using these exponentially many universes?
3SAT is NP-complete,
How the Mind Works by Steven Pinker
The Fabric of Reality: The Science of Parallel Universes – and Its Implications (London: Penguin, 1998).
Gems of Theoretical Computer Science by Uwe Schöning (Springer, 1998).
how you apply Bayesian reasoning where you have reason about the probability of your own existence, which seems like a very strange question. It's a fun question, though – which you can almost define as a question where it's much easier to have an opinion than to have a result.
philosopher John Leslie.
Let's call it the Dice Room. Imagine that there's a very, very large population of people in the world, and that there's a madman. What this madman does is, he kidnaps ten people and puts them in a room. He then throws a pair of dice. If the dice land snake-eyes (two ones), then he simply murders everyone in the room. If the dice do not land snake-eyes, then he releases everyone, then kidnaps 100 people. He now does the same thing: he rolls two dice; if they land snake-eyes, then he kills everyone, and if they don't land snake-eyes, then he releases them and kidnaps 1000 people. He keeps doing
...more
Bostrom, in his book about this,
Feynman won the Nobel Prize in Physics for showing that BQP PP, though he didn't state it that way. Anyway, the proof easily generalizes to show that PostBQP PP, because you just have to restrict your summation to those paths where you end up in one of those states you postselect on. You
John Leslie, The End of the World: The Science and Ethics of Human Extinction, Routledge, 1998.
whether there's free will or not. If you want to know where I stand, I’ll tell you: I believe in free will. Why? Well, the neurons in my brain just fire in such a way that my mouth opens and I say I have free will. What choice do I have?
they wanted to prove that they were Nietzschean supermen who were so smart that they could commit the perfect murder and get away with it. So they kidnapped this 14-year-old boy and bludgeoned him to death. And they got caught – Leopold dropped his glasses at the crime scene.
Ambrose Bierce that makes the point very eloquently:
“There's no free will,” says the philosopher; “To hang is most unjust.” “There is no free will,” assent the officers; “We hang because we must.”
Newcomb's Paradox So let's put a little meat on this philosophical bone with a famous thought experiment. Suppose that a super-intelligent Predictor shows you two boxes: the first box has $1000, while the second box has either $1000000 or nothing.
Then, we found one student that the program predicted exactly 50% of the time. We asked him what his secret was and he responded that he “just used his free will.”
If free will depends on an inability to predict future behavior, then it would follow from that free will somehow depends on our being unique: on it being impossible to copy us. This brings up another of my favorite thought experiments: the teleportation machine.
I think there's a big difference between the case where you take someone apart then put them together on the other end, and the case where you look inside someone to figure out how to build a copy, build a copy at the end and then kill the original. There's a big difference between moving and copying. I’d love to get moved, but I wouldn't go for the copying.
block-universe argument. The idea is that somehow special relativity precludes the existence of free will.
The Free Will Theorem,7 which got a fair bit of press.
wrote a review8 of Steven Wolfram's book9 a while ago where I mentioned this, as a basic consequence of Bell's Theorem that ruled out the sort of deterministic model of physics that Wolfram was trying to construct.
Actually, since I first wrote this chapter, the basic observation behind the Conway–Kochen “Free Will Theorem” has been used to great effect in quantum information science, to get protocols for generating so-called Einstein-certified random numbers. These are numbers that are physically guaranteed to be random, unless Nature resorted to faster-than-light communication to bias them, or did something equally drastic seeming (e.g., sent information backward in time).
S. Wolfram, A New Kind of Science, Wolfram Media, 2002.
Carl Sagan made: we're all time travelers – at the rate of one second per second!
