The Gateway to Computer Science Excellence

+63 votes

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:

- decidable and recursively enumerable
- undecidable but recursively enumerable
- undecidable and not recursively enumerable
- decidable but not recursively enumerable

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

We call recursively enumerable languages semi-decidable, then here why are we saying it is Recursively enumerable and undecidable?

+2

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

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

+5

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

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.

+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

0

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?

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

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.

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?

Another question coming here

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

then what it will be?

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.

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.

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

+7 votes

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

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 .

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,279 answers

198,173 comments

104,840 users