Computer Science 3331A/B Chapter Notes - Chapter 21: Countable Set, Infinite Loop, If And Only If

• School: Western University
• Department: Computer Science
• Course: Computer Science 3331A/B
• Professor: Lucian Ilie

Document Summary

Any nontrivial property of the sd languages is undecidable. Any language that can be described as {: p(l(m)) = true} for any nontrivial property. Nontrivial property= one that is not simply true for all languages or false for all languages. To use rice"s theorem to show language l of form {:p(l(m)) = true} is not in d, must. Show the domain of p is the sd languages. Show that p is nontrivial: p is true of at least one language, p is false of at least one language. Rice"s theorem only works for properties of languages, not descriptions of the machines. Comparing 2 languages- domain = sd x sd, not simply sd, rice theorem doesn"t tell anything about this. Reduce from h. let p be any nontrivial property of the sd language. We don"t know what p is but its either p(null) = true or p(null) = false.