Question

Question:Let$\mathit{B}\mathbf{=}\left\{\left(M_1),(M_2\right).......\right\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions such that every machine described in B has an equivalent machine in C and vice versa.

Short answer

A decidable language consisting of Turing machine descriptions such that every machine described has an equivalent this statement is proved.

Step-by-step solution

Step 1: Turing machine.

A Turing Machine is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.

A decidable language consisting of Turing machine descriptions such that every machine described has an equivalent. 

As the given machine in order of is defined as,

$B=\left\{\left(M_1),(M_2\right).......\right\}$

There is a decidable language consisting of Turing machine descriptions such that every machine described in B $B=\left\{\left(M_1),(M_2\right).......\right\}$ has an equivalent machine in C and vice versa .

If D exists, we can construct a Turing machine M₁ such that we search each possible string y , and testing whether,

.$h_x,y_i\in D$

If such y exists, accept. Such a machine M₁ will accept any string in C in finite steps, so C is Turing-recognizable.

If C is recognized by some Turing machine, we define

Clearly, D is decidable. Also, $x\in C$if and only if there exists y such that,

$h_x,y_i\in D$

Thus, $C=\left\{x\right|\exists y(hx,yi\in D)\}.$

Hence, proved.