Uploaded April 2018 | Updated September 2026, 13 hours ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
Specific topics covered in this lecture:graph isomorphism, friend-or-foe identification, zero-knowledge proofs, graph isomorphisms as "secrets", "approximating" mathematical proofs, caveats and pitfalls, exams as "proof protocols", zero-knowledge proofs for other NP problems, IP=PSPACE, zero-knowledge protocols in financial transactions, the Turing test, defining intelligence, who/what can "think"?, Turing's seminal paper, "The Imitation Game", "The Turk", Eliza, Elbot, who/what can pass the Turing test?, AI's from Star Wars / Star Trek / Terminator / Matrix / Battlestar Galactica / Blade Runner, criticisms of the Turing Test, the Chinese Room scenario, The Matrix triology, reverse Turing tests / CAPCHAs, Frankenstein stories, robots in movies, self-driving cars
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
Specific topics covered in this lecture:graph isomorphism, friend-or-foe identification, zero-knowledge proofs, graph isomorphisms as "secrets", "approximating" mathematical proofs, caveats and pitfalls, exams as "proof protocols", zero-knowledge proofs for other NP problems, IP=PSPACE, zero-knowledge protocols in financial transactions, the Turing test, defining intelligence, who/what can "think"?, Turing's seminal paper, "The Imitation Game", "The Turk", Eliza, Elbot, who/what can pass the Turing test?, AI's from Star Wars / Star Trek / Terminator / Matrix / Battlestar Galactica / Blade Runner, criticisms of the Turing Test, the Chinese Room scenario, The Matrix triology, reverse Turing tests / CAPCHAs, Frankenstein stories, robots in movies, self-driving cars
