Introduction to Computation: From Turing Machines to Black Holes 🌐

This is the lecture I.b of the mini-course "What is Computation? From Turing Machines to Black Holes and Neurons" offered at Harvard University in January 2022. More information can be found on the course website: https://cnchou.github.io/mini-course/

Comments and suggestions are welcomed :)

0:00 Announcement
1:35 Overview
2:55 Turing Machine is not Alone!
5:17 Example 1: Circuits
8:19 Example 2: Communication Models
13:13 Different Computational Resources
15:05: Example 1: Nondeterminism
20:30 Example 2: Randomness & Quantumness
24:27 Modern Study of Computation: Computability to Complexity
27:15 Formulations of Computational Complexity
35:36 An Example
37:15 Questions Asked in Complexity Theory
40:55 The Gem of Theoretical CS
41:10 Reductions
45:58 Example 1: Cook-Levin Theorem
49:00 Example 2: Communication Complexity
54:51 Summary