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.
Lecture
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 explores the concept that there are more boolean functions than algorithms, leading to the existence of functions that cannot be computed. Examples include the paradoxes of Epimenides and Berry, illustrating the halting problem. The lecture delves into the uncomputability of Kolmogorov complexity, demonstrating the impossibility of determining the shortest algorithm for a given output. It also touches on Rice's Theorem and the undecidability of various computational problems, emphasizing the futility of seeking solutions for undecidable problems. Despite the challenges posed by undecidable problems, the lecture highlights that algorithms can still solve practical instances of such problems.