Consider be the encoding of a Turing Machine as a string over alphabet -0-1- Consider L- M is TM which halts on all the input and LM -L- for some undecidable language L-Then L is

Since M is a TM that halts on all input. So, L(M) is decidable. So, L(M)≠ L'. Hence, it will be recursive too. ...

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Consider be t...

Question

$Consider < M > be the encoding of a Turing Machine as a string over alphabet \sum = {0, 1} . Consider L = {< M > | M is TM which halts on all the input and L(M) =L' for some undecidable language L^{'}} .$
Then L is

Recursive

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Undecidable and Recursively Enumerable

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Undecidable

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Decidable but Non-Recursive

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

Suggest Corrections

Similar questions

$M = {ω ω^{R} ω ω^{R} | ω \in {(0, 1)}^{*}}$

$N = {ω_{1} ω_{1}^{R} ω_{2} {ω_{2}}^{R} | ω \in {(0, 1)}^{*}}$

l, m, n

I . (l^{*} m^{*} n^{*})^{*} = (l m^{*} + m n^{*} + n l^{*})^{*} I I . (m n + m)^{*} m = m (n m + m)^{*} I I I . (l^{*} m^{*} n^{*})^{*} = (l^{*} + m^{*} n + n^{*})^{*} I V . (l^{*} m)^{*} = (l + m)^{*}

L (M) \cap L (N)

L = x^{l} y^{n} 2^{n} | (l + m + n)

Join BYJU'S Learning Program