Problem Detail: 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.
Asked By : Ayrat
Answered By : Shaull
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14680
