I'm quite new to computability theory and would be interested in some examples of realistic programming tasks you could encounter when working as a C++ programmer that are not computable.
Are there some inputs that make my program crash?
Can this object be freed (from memory) or can it be needed later?
I'm building an editor and want to detect the programming language automatically. Given two languages described by CFGs, is there some input code for which I won't be able to guess the language (because it's valid in both languages)?
Do these two programs do the same thing?
Suppose that you have a property of programs so that:
- It only depends on what the program does, not how it's written. So for example "It computes the factorial" or "It loops forever" work, but neither"It's written using a for loop" nor "It uses 5 variables" do.
- There is some program that has the property
- There is some program that doesn't have the property
Then Rice's theorem tells you that you can't have a (meta-)program that looks at source code and tells you if the program it describes has the property.
(My first and last examples are instances of that theorem)