Student Projects

This is a place for interested students to post links to their project reports and/or presentations.

Posted in Uncategorized | 4 Comments

Class #13: The Singularity and Universe as Computer

(Participation is optional.  For additional discussion about Newcomb’s problem and free will, please post in thread #12b.)

Feel free to post any thoughts you’ve had related to the topics discussed in class #13:

  • The concept of a “technological singularity” and what exactly we should interpret it to mean
  • What the fundamental physical limits are on intelligence
  • Whether it’s useful to regard the universe as a computer, what that statement even means, and whether it has empirical content
  • Whether any of the following considerations are obstructions to thinking of the universe as a computer: quantum mechanics; apparent continuity in the laws of physics; the possible infinitude of space; a lack of knowledge on our part about the inputs, outputs, or purposes of the computation
Posted in Uncategorized | 18 Comments

Class #12b: Newcomb’s Paradox and Free Will

Do you believe the superintelligent “Predictor” of Newcomb’s Paradox could exist?  Does your answer depend on specific properties of the laws of physics (such as the uncertainty principle)?  Does it depend on the assumption that humans are “open systems”, in constant interaction with their external environment?  Does it depend on subtleties in even defining the Predictor (for example, to what extent it’s allowed to alter the state of your brain while scanning it)?

Do you consider yourself a one-boxer or a two-boxer?  Why?  Or do you reject the entire premise of Newcomb’s Paradox on logical grounds?

What do you make of the idea that, if Newcomb’s Predictor existed, then you’d need to think in terms of two different “instantiations” of you, which nevertheless acted in sync and were “controlled by the same will”: (1) the “real” you, and (2) the simulated version of you being run on the Predictor’s computer?  Does this proposal do irreparable violence to causality, locality, or other principles of physics?  If so, is the “benefit” (justifying one-boxing) worth the cost?

What’s the role of probabilistic or game-theoretic considerations in Newcomb’s Paradox?  Does the probabilistic variant of the paradox (discussed in class) raise any issues different from those raised by the deterministic version?

If Newcomb’s Predictor existed, would that create new and serious problems for the everyday notion of “free will”?  (Feel free to divide this into two sub-questions: whether it would change how people thought about their free will, and whether it ought to.)

More generally, what’s the relationship between Newcomb’s Paradox and the “traditional” problem of free will?  Are there aspects of one problem that aren’t captured by the other?

Apart from what we discussed in class, can you suggest any computer-science examples or metaphors that clarify aspects of the free-will issue?

Posted in Uncategorized | 64 Comments

Class #12a: Evolution

If philosophers, mathematicians, etc. had been clever enough, could they have figured out that natural selection was the right explanation for life a priori, without input from naturalists like Darwin?  If life exists on other planets, should we expect that it, too, arose by Darwinian natural selection—or rather, that if the life was “intelligently designed,” then natural selection was ultimately needed to bring the intelligent designer(s) themselves into existence?  Is there any conceivable mechanism other than natural selection that’s capable, in principle, of doing the same sort of explanatory work (i.e., that would qualify as a “good explanation” in David Deutsch’s sense)?

Consider a “brute-force search algorithm,” which cycles through all possible DNA sequences until it finds some that lead to interesting and complex organisms.  Many people would say that this algorithm does not do the same sort of explanatory work as natural selection—but if so, why not?  Is it because brute-force search takes exponential time?  Or because the goal of “interesting and complex organisms” is too vague?  Or both reasons, or something else entirely?

Likewise, what are the similarities and differences between Darwinian natural selection and the anthropic explanation for the apparent “fine-tuning” of physical constants?  If the former explanation satisfies us while the latter doesn’t, then why?

Is there a puzzle about the speed of evolution?  Is it reasonable to want an explanation for why evolution on Earth took roughly 4 billion years, rather than a much longer (or shorter) time?  If so, what could such an explanation look like?  Can Valiant’s “Evolvability” model shed any light on these questions?

What are the differences between genetic and memetic evolution?

What are the differences between natural selection and genetic algorithms, as applied (for example) to find approximate solutions to NP-hard optimization problems?

Posted in Uncategorized | 18 Comments

Off-Topic Discussion

By student request, I’ve created this post as a place for students and listeners in 6.893 to discuss any questions related to philosophy and theoretical computer science that don’t fit into the other posts.

Posted in Uncategorized | 10 Comments

Class #11: Complexity, Economics, and Bounded Rationality

In general, do computational complexity limitations pose a serious challenge to classical economic theory?  If so, is that challenge over and above the one posed by ordinary cognitive biases?  Note that there are really two components to these questions: the first is whether complexity limitations challenge the “descriptive” part of economics (by showing that real agents might not be able to compute Nash equilibria, perform Bayesian updates, maximize their expected utility, etc).  The second component is whether they challenge the “prescriptive” part: i.e., if classical economic rationality requires computations that are so far out of mortal reach, then is it even worth setting up as a target to aim for?  And even supposing you had unlimited computational power, what about taking into account other agents’ lack of such power?

How should we understand the observation that the Iterated Prisoner’s Dilemma, with any fixed number of rounds, has “always defect” as its only equilibrium?  Is the solution to take into account the players’ bounded memories (as Neyman proposed), or some other cognitive limitation that blocks the “grim inductive reasoning” from the last round back to the first?  Or is it simply that the assumed scenario—where you interact with someone for a fixed, known number of rounds—was artificial in the first place, so it doesn’t matter if game theory gives us an “artificial” answer?

What’s your favored resolution of the Surprise Examination Paradox?  Do you agree with Kritchman and Raz, that the problem is basically one of the students not being able to prove their own rationality—and therefore, of their not being to declare in advance that, if the exam came on Friday, then it wouldn’t be a surprise to them (even though, in actual fact, it wouldn’t be)?  In what ways is the Surprise Examination Paradox similar to the “Iterated Prisoner’s Dilemma Paradox,” and in what ways is it different?

Do you agree or disagree with the “Common Prior Assumption” (CPA), which says that all rational Bayesian agents should have the same prior probability distribution?  If you agree, then what do you make of Aumann’s Agreement Theorem: does it really teach us that “agreeing to disagree” is inherently irrational, or is there some other loophole (for example, having to do with bounded rationality)?  If you reject the CPA, what do you make of the argument that, if two people really want to be rational, they both need to take into account the possibility of “having been born the other person”?  (And for the philosophers: are there any interesting connections here to the views of Spinoza, or Rawls?)

Posted in Uncategorized | 19 Comments

Class #10: The Deutsch MWI Argument, the Evolutionary Principle, and Closed Timelike Curves

The “Deutsch Argument” for the Many-Worlds Interpretation (“Where Was The Number Factored?”)

Does the possibility of scalable quantum computers prove (or rather, “re-prove”) the Many-Worlds Interpretation, as Deutsch believes?  If not, does it at least lend support to MWI?  Is MWI a good heuristic way to thinkabout what a quantum computer does?

On the contrary, does MWI encourage intuitions about how a quantum computer works that are flat-out wrong?  (E.g., that it can “try all possible answers in parallel”?)

If scalable quantum computers are built, do you think that will change people’s outlook on the interpretation of quantum mechanics (and on MWI in particular)?

Can MWI be tested?  What about, as Deutsch once suggested, by an experiment where an artificially-intelligent quantum computer was placed in a superposition over two different states of consciousness?

Does the fact that humans are open systems—that unlike quantum computers, we can’t practically be placed in coherent superposition states—mean that MWI and the Copenhagen interpretation are indistinguishable by human observers?

Would a scalable quantum computer test quantum mechanics itself in a new way?  Is the possibility of scalable quantum computing (or more generally, of a violation of the Extended Church-Turing Thesis) so incredible that our default belief should be that quantum mechanics breaks down instead?

Could quantum computing be impossible in principle without quantum mechanics breaking down?  If so, how?

Suppose it were proved that BPP=BQP.  Would that influence the interpretation of QM?  Would it undercut Deutsch’s case for MWI, by opening the door to “classical polynomial-time hidden-variable theories”?

The Evolutionary Principle and Closed Timelike Curves

Is Deutsch’s Evolutionary Principle—that “knowledge can only come into existence via causal processes”—valid?  If so, how should we interpret that principle?  What counts as knowledge, and what counts as a causal process?

Is Deutsch’s “Causal Consistency” requirement a good way to think about closed timelike curves, supposing they existed?  Why or why not?

Does the apparent ability of closed-timelike-curve computers to solve NP-complete problems instantaneously mean that CTCs would violate the Evolutionary Principle?  If so, how should we interpret this: that CTCs are physically impossible?  That the Evolutionary Principle is a poor guide to physics?  Or that, if CTCs exist, then some new physical principle has to come into effect to prevent them from solving NP-complete problems?

Posted in Uncategorized | 45 Comments