CODEWITHSUNDEEP
computation-theoryturing-machinescomputation
Mohammad Da
Mohammad Da

Reputation: 7

{<M> | M is TM that accept 3 words } (|L(M)|=3)

I'm stuck with this problem

{<M> | M is a TM that accepts 3 words}

I know how to solve |L(M)|&gt;3 or |L(M)|&lt;3 but when it comes to |L(M)|=3 , I don't know how to proceed!

Upvotes: 0

Views: 1498

Answers (2)

Nikhil Sharma
Nikhil Sharma

Reputation: 11

According to the non-monotonic property of turning machine by Rice Theorem. Let's take a case: we can say (a language accepted by turning machine) T{yes}={0,10,11} and (a language not accepted by turning machine) T{no}={0,10,11,1} so here Tyes is a proper subset of Tno. Hence this problem is undecidable.

Upvotes: 1

Peter Leupold
Peter Leupold

Reputation: 1212

How about using the fact that |L(M)|=3 means that |L(M)|>2 AND |L(M)|<4. Or the fact that with |L(M)|=3 and |L(M)|>3 you could decide |L(M)|>2. These woudl use the things you say you know how to do.

And, of course, if you are allowed to use Rice's theorem that Willem has mentioned, then the answer is pretty immediate.

Upvotes: 1

Related Questions