L19: Uncomputable Functions, and Introduction to Complexity

Proof by diagonalization that there are uncomputable functions; introduction to complexity theory, big-Oh notation, definition of worst-case for a non-deterministic. Turing machine; definition of the classes P and NP.

[@huilinchang8027]

awesome lecture :)

[@bazwa6a]

Complexity 26:45

[@zanfu3053]

nice, down to earth.

[@markit30]

great

[@puneetsingh6782]

who stole my chalk :D

[@sanssoleilfilm]

at 18:00 - doesn't he just prove that it is impossible to list all computable functions, rather than proving there are uncomputable functions?

[@sethbarton9748]

It does say that, because the list of computable functions is infinite, but he's also saying that for every computable function there's "another one", this d function. Which means that the list of functions is longer than the list of computable functions, therefore at least one of them must be uncomputable.

[@SirMrMcMsMrs]

one view? me? shame on America