[ITOC-ch5] REDUCIBILITY
If A reduces to B
- we can use a solution to B to solve A
- solving A is no harder than solving B
$ A \longrightarrow B \ (decidable) \Rightarrow A \ (decidable) $
$ A \ (undecidable) \longrightarrow B \Rightarrow B \ (undecidable) $
5.1 UNDECIDABLE PROBLEMS FROM LANGUAGE THEORY
General Idea
Contradiction on $ A \longrightarrow B \ (decidable) \Rightarrow A \ (decidable) $
If we have a TM R that decides $ HALT_{TM} $ ( or sth ).
- Then we can use R to construct a TM S that decides $ A_{TM} $
- thus obtain a contradiction.