Computing
From ResearchWiki
Contents |
Goals
A high level introduction to the key ideas involved in 'computational thinking', with NO equations and no math background. Targeted to freshmen/sophomores, with a philosophical rather than technical treatment of material. Emphasis on relating these concepts to the world around us.
Outline
- history of key ideas in computing
- atomic steps
- fixed set of operations (ruler and compass)
- idea of what cannot be computed
- automatic procedure to perform steps (Leibniz/Babbage)
- impossibility results
- Hilbert
- Godel/Turing/Church (bring in Hofstadter and GEB)
- computation as a metaphor for "feasible"
- effectiveness: polytime
- replace "cannot be done" by "cannot be done feasibly": birth of modern crypto
- computation as atomic notion in economics, voting theory, physics
- nature "optimizes", "programs": model natural processes computationally (protein folding)
- P vs NP as reflection on human creativity
- Zero knowledge (always useful to bend people's minds)
- computation as the language of science
- math talks about what can and cannot be done; cs talks about what can/can't be done feasibly
- Think of problems from computational perspective: "what is the underlying computational problem" as opposed to "what is the underlying mathematical structure
- emergent phenomena: Conway's Life: set up a simple system with game rules, and let it evolve (the video game Spore)
- computation as lens on the universe
- quantum computing (Feynman's essays, Deutsch)
- information content of a black hole (Hawking, Bekenstein bound)
- (physical) entropy as information: maxwell's demon. "entropy" of a computational step (fascinating philosophical puzzle)
- discrete structure of spacetime (!!! )
- computation as redefining flow of, and access to, information
- data mining, privacy
- electronic voting machines
- DRM, fallacy of the secret key in an open world, Why DRM is impossible
- Dangers of living in a computer-controlled world: Cory Doctorow's 'Human Readable'
- social networks, reputation systems...
