That Veritasium's video is great! I'd also recommend Computerphile's 3-part video series (~10 mins each) which tells the history of undecidability and the incompleteness theorem:

https://www.youtube.com/watch?v=nsZsd5qtbo4

https://www.youtube.com/watch?v=FK3kifY-geM

https://www.youtube.com/watch?v=lLWnd6-vSGo