微软21世纪的计算研讨会：笔记

• Turing started modern computation
  • universality
  • mentioned the computation of the universe
• Moore’s Law & clove algorithms
• is P != NP?
• Intractable problems
  • in Facebook can you find 100 people being friends of each other?
  • find all factors of a number? (modern encryption is based on this)
• The more people listen to your view, the more important the view you will be
• CS: a lens on the Sciences
  • A new way of thinking: Algorithms
• Physics
  • The mystery of phase transitions vs. the speed of convergence of algorithms
    • physics and applied mathematics invent algorithms
    • CS research helps understand how phase transitions
• Quantum Computations
  • reinvent the bit
  • bit vs. qubit
  • 0 or 1 vs. Q = a |0> + b |1> (both states at the same time, just probabilities)
  • Oh my god, how do you simulate such a system on a computer?
    • Richard Feynman, 1982: solution: build a computer out of such things
  • Peter Shor: No safe encryption
  • Quantum computation is about testing quantum physics
• Cloud
  • the internet is based on computers
  • with internet, CS is no longer about computers, it is about many complicated issues, it is a social science
  • internet is a kind of equilibria
    • the same as economics
  • Economic is about to find a equilibria
    • But it is intractable !! (2006)
    • If your laptop can’t find it, neither the market will.
• Evolution
  • The Origin of Species: the most clever scientific argument in the history of science
    • worth reading!
    • natural selection
  • Evolution since 1859
    • Genetics (Mendel, 1866)
    • the crisis (1900—1930) — the genetics is contradictory with Darwin’s theory
    • the synthesis through math (1930—)
    • the genomics revolution
  • Unanswered questions
    • How do complex adaptations happen?
    • What is the role of sex/recombination?
      • why do we have parents?
      • Sex doesn’t make sense
      • at first there is no sexual difference!
    • Why so much genetic diversity?
  • A radical idea
    • what id evolution under sex is a poor optimizer of fitness?
      • it seems to be when used in heuristic algorithms!
      • mixability!
        • alleles are good mixers
      • it has connections with game theory
        • evolution can be seen as a repeated game between genes
        • the strategies of each gene are its alleles
          • the genes are inventing into themselves
        • the common utility id the species;s fitness
        • multiplicative updates!
          • some many sophisticates problems
          • a trade off between two
            • cumulative fitness
            • genetic diversity
• Conclusion
  • computation is not only about computing
  • a lens of many sciences

Do more, Know More, and Be More with computational living

Xiaowen Hong