I am studying An Introduction to the Theory of Computation by Sipser -- there is a problem *3.17 (p.161) which I can not solve. Any hints (not answers) from which side to attack it?Let $B=\{M_1, M_2, ...\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.
Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs
turing machines;decision problem
Technical hint: assume that every string is a legal encoding of a TM. Can you solve this now?Intuitive hint: the language $C$ can contain many other encodings as well as those that are equivalent to the machines in $B$. Perhaps so many that $C$ becomes decidable.