Computation Theory

Books, Lecture Notes

• Stephen Wolfram: A New Kind of Science
• ncat lab Homotopy Type Theory
• The Church-Turing Thesis (and how it is often misunderstood), at the Stanford Encyclopedia of Philosophy
• M.R. Garey, D.S. Johnson:Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)

Videos

• Stephen Wolfram: Cellular Automata, Computation, and Physics, Lex Fridman Podcast #89 (2020)
• Stephen Wolfram: Stephen Wolfram: Fundamental Theory of Physics, Life, and the Universe, Lex Fridman Podcast #124 (2020)

Posts

• Stephen Wolfram: Finally We May Have a Path to the Fundamental Theory of Physics… and It’s Beautiful (2020)

Papers

• Geroch, Hartle: Computability and Physical Theories. Referenced in Penrose’s ‘Road to Reality’, Chap. ‘The Ladder to Infinity’. Contains in introduction a proof of the Halting Theorem that was missing in Penrose’s chapter.

People

• Klaus Sutner, Google scholar
  • Turing vs. Bourbaki - Teaching Mathematics to CS Majors (Intro to CMS math class for Computer Science, 2021)
• [Stephen Wolfram]

Other

• Automated Theorem Proving
• Artificial Intelligence
• Cognitive Science
• Machine Learning
• Probabilities and Statistics
• Robotics
• Self Driving Cars