The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+53 votes
8.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 by Veteran (99.6k points)
edited by | 8.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?
+1

@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...

3 Answers

+72 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$

by Veteran (418k points)
edited by
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?
+6 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 . 

by Loyal (9.4k points)
+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
by Active (1.4k points)
Answer:

Related questions

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
49,984 questions
55,135 answers
190,487 comments
85,106 users