search
Log In
4 votes
566 views

L1= {⟨M⟩| M is a TM and |L(M)| = 5 }. 

we know about at least and at most case, but someone explain equal to case.

Furthermore, I'll complie more questions in same thread only.

L2= {⟨M⟩| M is a TM and M does not accept all even numbers}. 

L3 = {⟨M⟩| M is a TM and M reject all even numbers}. 

in Theory of Computation 566 views
3

L1= {⟨M⟩| M is a TM and |L(M)| = 5 }

|L(M)| = 5 = Language contain 5 strings.

Question says

If M is Turing machine and it has 5 strings. Hence All Turing Machine has 5 strings . Suppose you are given a program now run that program with all Turing Machine as input now Tyes if all are stop and say they accept only 5 strings. Tno if all are  stop and say length of Atleast one is not length 5 . 

Now What happen when All Turing Machine are in loop . we get no output for many years. So its an undecidable problem.

0
@Prashant.

I think atleast two length string can loop TM.

ryt??
0

L1= {⟨M⟩| M is a TM and |L(M)| = 5 } is recursive enumerable language and it is an undecidable problem.

0

@nikhil_cs, what is the minimum length of string, which loops the TM??

0

I think it should be two because for first symbol move to right and for second symbol move to left.
But it can be also done by B (blank). Let there are two states in TM (q0 and q1) then transitions can be:

1. q0 with input B, leave it as B and move to right on tape and go to state q1
2. q1 with input B, leave it as B and move to left on tape and go to state q0

Non-halting TM

Correct me if I am wrong.

0

@nikhil_cs How L(M) is R.E?! I mean, how can you say that? Please share the basis for it.

2

To prove L(M) is R.E. , we need an enumeration method which can generate L(M) i.e set of T.M which can accept string length of 5.
Let we have set T.M {m0 , m1 , .... mn} from which need to generate L(M) = {⟨M⟩| M is a TM and |L(M)| = 5 }.
Step 1 :
give input to m0, if it stops within certain amount of time (say t) then we move to step 2 otherwise we move to step 2 after time 't'.
Step 2:
we give input to m0 and m1 and wait till 't'.
step 3:
now to m0 , m1, and m2. and so on.
 

If in any step, any T.M stops (i.e it accepts sting length 5) then we add this T.M to our language L(m). In this way we can generate all T.M which will accepts string lenght 5.

1

@nikhil_cs Awesome thanks!

0

L(M) i.e set of T.M which can accept string length of 5. or |L(M)| = 5 = Language contain 5 strings.

@nikhil_cs @Prashant. Which is correct?

0

Here according to question, L(M) i.e set of T.M which can accept string length of 5.

0
Alright, thanks! :)
2

All above 3 mentioned languages are NOT RE, not even RE.

First language is also NOT RE, because we have to make sure that once a TM accepts 5 strings, it doesn't accept any other string.

0
Guys, this is so confusing as we have got many different answers contradicting each other!

@Arjun @Bikram, Sir you may please pitch in too!
0

@manu00x

According to definitions:-

Recursive Language (Decidable Language):- The lang for which a halting turing machine exist.

Recursive Enumerable language(Semi decidable languages) :- The lang for which turing machine exists(may or may not halting because for some input machine may loop forever.)

Not Even Recursive Enumerable (Undecidable languages ):- The lang for which no Turing machine exists.

Are these definition correct??

0
yes Shubhanshu all are correct.
0

But here, why don't we have semi decidable in the diagram.

http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/Undecidability.pdf

Refer third slide.

0

@Shubhanshu 

TM may or may not halt means semi decidable only. 

0
The Region Of REL but not recursive is semi-decidable and Out of REL is undecidable.

1 Answer

1 vote

L1= {⟨M⟩| M is a TM and M does not accept all even numbers}. 

L2= {⟨M⟩| M is a TM and M  accept all even numbers}. 

L2 is not RE.

(See L4 from https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf)

L1 = Complement of L2.=>complement of NOT RE is NOT RE.

Correct me if wrong!!!

 

Related questions

1 vote
1 answer
1
291 views
For every deterministic Turing machine, there exists an equivalent deterministic Non Deterministic Turing machine. I know, other way is correct i.e for every DTM there exist a NDTM, but is above TRUE/FALSE. Thank you!
asked Nov 1, 2017 in Theory of Computation iarnav 291 views
3 votes
2 answers
2
296 views
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? L={⟨M⟩∣ M halts on all palindromes}. How can i use Rice's theorem here? Tyes={All palidroms} Tno={Signma*}.Will that work here? M halts on all palindromes means M halts on only palindromes ?
asked Aug 8, 2017 in Theory of Computation rahul sharma 5 296 views
2 votes
2 answers
3
195 views
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? {⟨M1,M2⟩∣ M1 and M2 are two TMs, and ϵ∈L(M1)∖L(M2)}.
asked Aug 8, 2017 in Theory of Computation rahul sharma 5 195 views
2 votes
2 answers
4
673 views
Consider the following two decision problems Whether a Turing Machine takes more than 481 steps on input epsilon? Whether a Turing Machine accepts the null string epsilon? Which of the following statements is true ? Problem a is decidable but b is not Problem a is undecidable but b is decidable Both a and b are decidable Both a and b are undecidable
asked May 25, 2016 in Theory of Computation biranchi 673 views
...