While trying to understand homomorphism for recursive proof I came across the following link - https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec26.pdf
Look for proposition 4. In the last point of the proof it is written that h(L) = HALT. What does it mean?
---------------------------------------------------------------------------------------------------------
Rewriting proof here, if in case the links breaks down in future.
Proposition 4: Recursive Languages under homomorphism are not decidable.
Proof: We will show a decidable language $L$ and a homomorphism such that $h(L)$ is undecidable.
- Let L = $\left \{ x \mid x\in \left \{ 0,1 \right \}^{*}, y\in \{0,1 \}^{*} x = <M,w>, such\ that\ the\ turing\ machine\ M\ on\ input\ w\ will\ halt\ in\ n\ steps \right \}$
- L is decidable: can simulate $M$ on input $w$ for $n$ steps
- Consider homomorphism, $h: h(0) = 0, h(1) = 1, and h(a) = h(b) = ε$.
- $h(L) = HALT$ which is undecidable.
