Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
This lecture introduces the theory of computation, focusing on problems definition and counting. It covers the concept of denumerability, explaining how to count infinite sets and showcasing examples of countable and uncountable sets. The instructor discusses the importance of algorithms in solving problems and highlights the distinction between countable algorithms and uncountable functions. Through examples, the lecture illustrates how some boolean functions cannot be computed by any algorithm, emphasizing the limitations of computation in handling certain types of problems.