The Gateway to Computer Science Excellence
0 votes

Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ is TM that halt on all input and $L\left ( M \right )=L'$ for some undecidable language $L$}. $(L’$ means complement of $L).$ Then $D$ is

$(A)$ Recursive

$(B)$ Non-Recursive

$(C)$ Recursively enumerable

$(D)$ Not Recursively enumerable

My question is Is it not a Halting Problem they are asking for? 

in Theory of Computation by Veteran (119k points)
edited by | 381 views

No, Halting Problem's statement  is $L=\{<M,w> | \;M \;halts\; on \;input\; w\}$ and your question is different.

Both $L$ and $L'$ are non-RE and undeciadable. use dovetailing trick.


No, @ankitgupta.1729

ans is decidable :(

By the way

M is TM that halt on all input 

is it not halting prob statement? I finded in piter linz but couldnot able to find halting problem :( 


mam, given answer is wrong.

check it


@srestha Please understand a question properly before seeing others. I see that you are duplicating many questions which shows that you are not understanding them properly.

@ankitgupta.1729 The given problem is undecidable?


@Arjun sir, sorry. I didn't read question properly that time. Set $L$ should be empty because {<M>|M halts on all inputs} means L(M) is decidable(recursive) and  L(M) = L' for some undecidable language L' means L(M) is undecidable. So, both things are not possible at the same time.     

yes, $L = \{\}$ which is regular.
But according Sai lecture 39:20 min

It is telling that "M is TM that halt on all input" is undecidable.

Because it could go an infinite number of string in a infinite time

That is perfectly correct. Just a single "word" can make a regular language not even recursively enumerable. Here, you are skipping half the language description and arguing.


sir, if L is decidable, then how L' could be undecidable?

It cannot be. So, the set of all such TM descriptions, say $D$ becomes empty. Now, this set $D$ is regular because we can have a DFA for $D = \{\}.$
In the question given, we have a TM $D$ for the given problem and also a TM $M$ which is part of the problem description.

@Arjun  sir

Yes , it is universal TM, where one TM can work inside other TM.


But why it is not halting TM?

And another point is the inside TM generates the language which is complement of outside TM. And it is undecidable

How this could happen for outside TM?

Last year did you do the assignment on same in GO classroom?
I cannot remember now

Which one?
A C program taking as input an executable?

@Arjun Sir

yes, I tried to do, and I tried it in stackoverflow post, but still not able to found appropriate solution

So, I stopped there

Can u plz tell me , how that question related to this?

This question is related to universal turing machine

Am I right?

Then how inner program generates a language which is complement of outer program?

Moreover outer program generating a language which is decidable and inner program generating language which is undecidable, how that possible

plz plz tell me

3 possibility coming for me

1) why L is not halting problem?

2)if not halting (according to sai) why it is not non-R.E?

3) Why it will be decidable?
what is difference when lenguage representing as L and when representing as L(M)
I don't think you got anything about Universal Turing machine. When you have a program which takes another program as input you get totally 2 programs. That's the same way for Turing machines here. Also you must be good in English grammar if not expert to understand these topics because they can twist a problem just by a word.

Actually I am getting problem, the description they given

L(M) is definition of L

but according to L(M) are those string which are not in L (that means description of L is just complement of L)

That means when we are telling L halt on all input

but also telling L(M) doesnot halt in any input



hello @srestha mam, Please check  this link

In the given link, it is mentioned that :-

"$L = \left \{ \left \langle M \right \rangle | TM\ halts\ on\ every\ input\ \right \} \Rightarrow L = \left \{\left \langle M \right \rangle | L(M)\ is\ Recursive \ \right \}$"

Because a machine that  halts for every input is called a Total Turing Machine and class of languages associated with these machines are called recursive languages.

Now in this question,

$1^{st}$ part of the problem says :- Turing machine $'M'$ halts on all inputs. So, language accepted by this Turing Machine '$M$' i.e. $L(M)$ Is recursive(decidable).

So, till now, we got a statement which says :- "$L(M)$ is recursive(decidable)." 

Now, $2^{nd}$ part of the problem says :- "$L(M)=L'$ for some undecidable language $L'$"

According to this statement, $L(M)$ should be undecidable because it is equal to some undecidable language.

So, according to 2nd part :- "$L(M)$ is undecidable".

Now, there is an "and" between these 2 statements means both statement should be true simultaneously.

i.e. {$L(M)$ is recursive(decidable) and $L(M)$ is undecidable}

Since, it is not possible that L(M) is decidable and undecidable at the same time. So, no elements should occur in this set.

So, it should be empty set i.e. $\{\}$ 

I think instead of 'L' in LHS, they should have to give different letter because here if $L=\{\}=regular$ then its complement should also be regular which is contradicting by saying L' is undecidable. If we consider LHS as some set S then answer will be $S=\{\}$ which is regular set and also recursive(decidable) set.



you written very easy way

yes , I understood ur every point

Still think more on this point

"L(M)=L′ for some undecidable language L′"-That means L(M) not only undecidable, but it also undecidable on L'

So, we can say , L halts on every input , but at the same time L(M) not halt on any input (as L(M) is L')

Another contradictory point in ur analysis

"a machine that  halts for every input is called a Total Turing Machine and class of languages associated with these machines are called recursive languages."

According to Sai lecture it is non R.E.


I have edited the question to remove any ambiguity. There's nothing more to explain in this than what Ankit did.

@Arjun Sir

if u change L to D, then L' also need to be D'


Otherwise what is L' ??

$L$ was not there -- now see.

2 Answers

0 votes
L = { <M>| M accepts w } is a halting problem. L is recursive enumerable but not recursive as on input w, M can either halt on w or enter into loop.

But L = { <M>| M halts on w } is a recursive language and decidable because there is no possibility of entering into loop. Thus L is not the halting problem.

Given, L= { <M>| M is a tm that halts on all inputs } and L(M) = L' for some undecidable language L' .

Let us assume <M'> ∈ L. Then L(M') is decidable. But according to given condition, L(M') = L' for some undecidable language. Hence this contradicts our assumption. Therefore <M'> ∉ L.
Thus L is an empty language. Hence L is regular and decidable.

Since, every regular languages are also recursive languages are also recursive languages.

Hence L is decidable and recursive.

Option a is correct.
by Active (1.4k points)

what is difference between L and L(M)?

question is like this

L={⟨M⟩M is TM that halt on all input and L(M)=L′ for some undecidable language L′}

I mean L(M) is inside L. that L(M) also inside language description 


@srestha mam L is the language consisting of binary encoding of turing machines which halts on every inputs. <M> denotes binary encoding M.

L(M) is the language accepted by turing machine M whose binary encoding is in L.

L(M) is not in L. Both L(M) and L are different. 

let w and s are two strings over alphabet ∑. Let w∈ L and s∈ L(Mi). Therefore, s is a string accepted by tm Mi and w is a string in L representing binary encoding of some turing machine Mi. Therefore L and L(M) are different.


w is a string in L representing binary encoding of some turing machine Mi

havenot got this

u told $w , s$ both are encoding through same TM $M_{i}$


Both w, s are not encoding of same tm Mi. Plz read my previous comment carefully.

I told w is in L where L is set of binary encoding of all tm M where M halts on all inputs.
A binary encoding of a tm is a string of 0 and 1. Hence w is a string in L representing binary encoding of some tm M.

And s is in L(M) where L(M) is the language accepted by tm M. s is also a string of 0 and 1. But it is the string accepted by tm M and it is no the binary encoding of tm M


L is binary encoding of M and L(M) accepted the language has no binary encoding

how do u differentiate between two?

In computer all are in binary 



@srestha mam

It is differentiated in the question itself.

Consider L={⟨M⟩⟨M⟩ M is TM that halt on all input and L(M)=L′ for some undecidable language L′}

Think accordingly with the question. Those definitions are provided in the question.

$L=${$\left \langle M \right \rangle$ $M$ is TM that halt on all input and $L\left ( M \right )=L'$ for some undecidable language $L’$}

L is a language taking encoding of TM  'M' , say it is 0101

Now  what L(M) means?

It means language of TM 'M', Now we know language of M already encoded

So, can we not say, that it also taking the same , but instead of L it is taking L'??



chk it

Only accepts doesnot tells halting problem


There is no C program that reads a C program P and input w, and decides ifP “accepts” w.

The proof of the above theorem is identical to the halting theorem - we just perform our rewriting on the C program.

Also, notice that being able to recognize a language and its complement implies that the language is decidable, as the following theorem testifies.

Halting problem is problem of determining whether an arbitrary program on a certain input will halt on enter into loop forever.
For an arbitrary turing machine, whether tm will halt on certain input or loop is same as halting problem. That is why acceptance of a certain word or string by a turing machine is undecidable as it is same as halting problem.
But in this question, it is mentioned that tm halts on all inputs. That's why it is decidable and not same as halting problem.
0 votes

Language L is undecidable => Recursively Enumerable Language.

RE languages are not closed under complement. So L' is not RE language.

by (235 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,709 answers
107,610 users