Chapter Two Section 6, Rice's Theorem

We can show that problems are unsolvable by using Rice's Theorem. This is part of a course is based on Theory of Computation by Jim Hefferon, a Free text. It covers standard topics, including the definition of computation based on Turing machines, unsolvability such as the Halting Problem, Finite State machines and regular languages, and complexity including P vs NP. The approach is mathematical in that everything is proved, but the development emphasizes concepts and examples. See https://hefferon.net/computation/, which includes worked answers to all exercises, copies of the slides for these lessons, and more. If you like this then you may also be interested in a course based my Linear Algebra, another Free text. See https://www.youtube.com/watch?v=37tn0z9dSDo . The freely-downloadable material for that course also has worked answers to all exercises, copies of the slides for these lessons, etc. There is much more undergraduate mathematics material available at https://hefferon.net, including a number of other texts that are Free. In addition, some of my other videos at https://youtube.com/@JimHefferon include Calc I lessons at https://www.youtube.com/playlist?list=PLwF3A0R8OzMpSL5r8OnOYJIlvafOWv8ph , or my Calc II at https://www.youtube.com/playlist?list=PLwF3A0R8OzMpSL5r8OnOYJIlvafOWv8ph . In particular, you may want to check out How to Study College Mathematics https://youtu.be/pzdO7ugyRmg . If you appreciate this work then you can buy me a virtual coffee at https://ko-fi.com/jimhefferon. And of course you can help by clicking Like or Subscribe. Thanks!