The Gateway to Computer Science Excellence
+3 votes
426 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 by Loyal (8.4k points) | 426 views
+2

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! :)
+1

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

0 votes

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!!!

 

by (11 points)

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
50,741 questions
57,244 answers
198,019 comments
104,614 users