Decidability and undecidability
Theory of Computation · Engineering
Study notes
Prove 'does program P print hello?' undecidable: reduce from halting. Given (M,w), build P that simulates M on w and prints hello iff M halts. If we could decide hello-printing, we could decide halting: contradiction. So the property is undecidable. Rice's theorem generalizes: any nontrivial semantic property of programs is undecidable.