search
Log In
67 votes
12.6k views

Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$. Let $$L=\left\{\langle M \rangle \mid M \text{ is a Turing machine}\\\text{ that accepts a string of length 2014} \right\}.$$ Then $L$ is:

  1. decidable and recursively enumerable
  2. undecidable but recursively enumerable
  3. undecidable and not recursively enumerable
  4. decidable but not recursively enumerable
in Theory of Computation
edited by
12.6k views
0
y undecidable even if mention tht accept 2014 then
0
we dont know whether it will halt or not on string of length 2014 but it can halt or can not so Recursively enumerable. and halting problem is undecidable
1
Very Good and Important question
1
We call recursively enumerable languages semi-decidable, then here why are we saying it is Recursively enumerable and undecidable?
3

@nadeshseen semi-decidable property is a kind of subset of undecidable property. If a Turing machine accepts all string present in a language but we don't know whether it halts on a string not present in the language or not, then it is semi decidable because we don't know what will happen either it accepts or rejects. Due to the fact "at least it accepts all string present in the language it is SEMI-decidable.
But if a Turing machine designed to accept strings present in a language, may or may not halt on at least one string present in the language, then we consider it as an undecidable problem because it may accept or reject in infinite time that's why it is not even semi-decidable.
This is one of the most confusing topics of computer science, kindly read it carefully...

5 Answers

91 votes
 
Best answer

There are only a finite number of strings of length $2014$. So, we can give all those strings to $TM$ simulating each string for $1$ step, then $2$ step and so on (dovetailing), and if the $TM$ accepts any of them ("yes" case of $TM$), we can say "yes". So, $L$ is recursively enumerable.

(If the $TM$ doesn't accept any string of length $2014$, it can go to an infinite loop ("no" case of $TM$), and hence we can't say the method is decidable).

Now, to prove whether the problem is decidable or not we can make use of Rice's theorem. Rice's theorem (I) states that any non-trivial property of $L(TM)$ is undecidable. $L(TM)$ has a string of length $2014$ is a non-trivial property as there are $TM$s whose language contains such a string and there are $TM$s whose language doesn't have such a string. So, the given problem is undecidable.
http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

Correct Answer: $B$


edited by
0
Pls Explain what kind of problem decidable in case of turing machine?
1
go through the link given above by Arjun
2

Rice's 2nd Theorem will not be applicable in this example. Right ??

3
Yes. We can't because we can't make a subset relation to show the monotonic property.
6
I think it is recursive enumerable by definition because if TM take a input string and it weather it test a string and say that Yes its present in LANG but if there is string and which TM unable to say weather string is in given language or TM goes in infinite loop i.e. never halt then correspondnce class of language is called Recursive enumerable.

 

and if class of language where TM always halt for string present in language and not present in language is called Recursive Language
1
yes- just from definition we can say this because there are only finite number of strings on length 2014.
0
Do we have finite no. of such TM's which accept string of length 2014 or infinite ?
2
they are infinite countable set of TMs that might be able to accept a 2014 length string, but given a string from L -> an encoded TM we cant decide if it will accept string of length of 2014, so (b) undecidable and recursively enumerable
0
Halt if a turing machine acceptes $ 1$ string of length 2014. or all strings of lenght 2014. a string means some or all
2

@Arjun Sir correct me if i am wrong.

0

If the TM doesn't accept any string of length 2014, it can go to an infinite loop ..

strings of length 2014 are finite only. so we can say No after all strings of len 2014 are scanned

–1
Arjun Sir,

One small doubt on the proof that you gave for Recursive ennumerable.So we will give machine code  (M) as input to UTM whose language is L,which will then verify that whether the machine M accept the string of length 2014 by using the way you mentioned.Is this correct understanding?
1
Is there any other source to learn more about Rice theorem??
1
You are saying "giving it to TM" so let me get this straight.<M> is encoding of Turing machine(bits of 0 and 1) and the Language is like : L ={ <011010>,<0110101011>...finite no. of such Turing machines which can accept a string of length 2014} .Here <011010> represents the initial state,transition,final states all inputs and other usual things. Now we will give this Language (L) to a SINGLE Turing machine(let me call this T1) which will process the encodings of all other turing machines.Now we can say "yes"  if the T1 can halt after processing the <011010> etc encodings after processing an arbitrary string based on the input symbols of the encoding.If the TM halts after processing 2014 length and ends in final state then it is accepted and says "yes".Coming to "no" part it can say no or can go to loop.So to confirm for loop we use Rice's Theorem which states that as there exists a turing machine which will take a string(based on input symbols of the TM) and halt on length 2014 and there exists another TM which wont halt after processing a string of length 2014 hence we can confirm its undecidable. @Arjun Sir Please check ( These question's basics are quite uneasy to me hence i need you to clarify it by word and see if i made mistake(s) ) .Thank you!
0
Why can't L reject the strings which are of length less than or greater than 2014? Even a simple DFA can do that.

EDIT: The membership of an element in a TM is undecidable, but recognizable. Therefore L is R.E. I forgot this property.
0
Why can't the dovetailing concept be extended to the problem of whether a turing machine halts on every input?
0
yes , it will be Non RE

Another question coming here

L={⟨M⟩∣M is a Turing machine that accepts string of length $\geq$2014}

then what it will be?
0
@Deepak Non-monotonicity makes a language not even recursively enumerable - you told the reverse.
1
Thank you Sir. Don't know what was I thinking.... Guess I was high.
0
@Arjun Sir... I have a confusion,... I think that non monotonicity exists here.

Tyes - TM1 accepting string of length 2014 only.
Tno - TM2 accepting string of length 2014 and greater than  2014.

Both TM1 and TM2 are different TMs. In this case Tyes is a subset of Tno and non monotonicity property exist. hence its 'non REL'

If this approach is wrong then the following solution should also be wrong given at gatecse.com site

L(M) = {0}

Tyes = {0}, Tno = {0,00,000}

Here Tyes is a subset of Tno Hence "non REL".
Sir, plz tell me why my approach is wrong and wat is the difference between these two problems. I m getting confused here. I have read several times the concepts of Rice's Theorem but still getting the same doubt. Plz expalin it.
0

So as the question implies L(M) is finite (lets assumes N = 2^2014), We can have Tyes for N and Tno for Σ^∗ thus we have N⊂Σ∗. According to second property of Rice's theorem  L={M∣L(M) is finite} is not Turing recognizable (not recursively enumerable).

@Arjun Veteran sir, any comment would be prefferable. 

0
@Ankur Why you added "only" there? If it is there, then it is indeed non-monotonic as you have explained.

@Zaheer $L(M)$ is actually not necessarily finite here. The question says "accept" - so $L$ can also have any other strings making $L$ even infinite. But even if $L(M)$ is finite, when some specific set is given, we cannot generalize it and solve that general problem and apply the result to the special set.
0

We can solve this problem by using a simple reduction.

Let's assume that you have a decider named '2014' which takes input as the description of a Turing machine i.e <M>, and accepts <M> if M accepts any string of length 2014 otherwise it rejects <M>.

clearly, The language accepted by '2014' is all the <M>'s which accepts at least one string of length 2014. (Problem statement).

Now say if you really have a decider like '2014', I'll use it to solve the halting problem.

So, I want to build a decider D for language A = {<M, w> | M is a Turing machine which accepts string w} i.e a decider for the halting problem. 

 

My decider D takes input <M,w> and creates another TM D'.

D' does the following things:

                                                 Run M on w.

                                                 If M halts on w then D' accepts its input.


Clearly, D' accepts all the inputs if M halts on w. So, D' accepts a string of length 2014 if and only if M halts on w. 

D' accepts no string if M does not halt on w.

 

                                                Give <D'> as an input to '2014' .

                                                 if '2014' accepts <D'> then D accepts <M,w>

                                                                                        else D rejects <M,w>

 

Clearly, we can solve the halting problem if we have decider like '2014', but, we know that  HP is Undecidable. So '2014' Must be undecidable.

Please check if this is a valid reduction or not. @Arjun sir.

1
If w is of length 2015 and is halting on M, your machine is rejecting it rt?
0
Now?
0

I didn't understand the options... 

A. Decidable & RE  => language is "Recursive"

B. Undecidable but RE  => language is "RE- Recursive"

C. Undecidable & not RE  => language is "not RE"

 

But what does option D concludes ??  Decidable & not RE ?? How's that possible ? 

@Arjun sir

@Bikram sir 

 please help... 

0
option D is not possible.
10 votes

There are finite number of strings of length ‘2014’. So, a turing machine will take the input string of length ‘2014’ and test it. 
If, input string is present in the language then turing machine will halt in final state . But, if turing machine is unable to accept the input string then it will halt in non-final state or go in an infinite loop and never halt. 
 
Thus, ‘L’ is undecidable and recursively enumerable . 

1 vote
String can be of length 1,2,3,2014...N but we can never be sure that TM will ever halt on that given input or not hence it is undecidable
1 vote

There will be 2 case for the string of length 2014 :

Either,

1) It will be halt on final state i.e. accepted.

or else,

2) It will halt on non-final state or go on a loop.
 

So this is a partially decidable language.

If 100% decidable then Recursive

If partially decidable then Recursively enumerable

If 100% not decidable then not Recursively enumerable

Hence it is Partially decidable(Undecidable) and Recursively Enumerable.

 

0 votes

Answer: (B)

Explanation: There are finite number of strings of length ‘2014’. So, a turing machine will take the input string of length ‘2014’ and test it.

If, input string is present in the language then turing machine will halt in final state .

But, if turing machine is unable to accept the input string then it will halt in non-final state or go in an infinite loop and never halt.
Thus, ‘L’ is undecidable and recursively enumerable .

Answer:

Related questions

75 votes
5 answers
1
10.4k views
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ $\text{s as} $ ... one of the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
asked Sep 28, 2014 in Theory of Computation jothee 10.4k views
46 votes
4 answers
2
6.3k views
Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE? If $A\: \leq_m B$ and $B$ is recursive then $A$ is recursive. If $A\: \leq_m B$ and ... recursively enumerable then $A$ is recursively enumerable. If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.
asked Sep 28, 2014 in Theory of Computation jothee 6.3k views
27 votes
3 answers
3
3.4k views
If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$ Which one of the following is CORRECT? Only I Only II Both I and II Neither I nor II
asked Sep 28, 2014 in Theory of Computation jothee 3.4k views
53 votes
3 answers
4
9.3k views
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________
asked Sep 28, 2014 in Operating System jothee 9.3k views
...