## [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.