Decidability

Question

1. {<M,w>| M is a TM, and w is a string, and there exist a TM, M' such that w (does not belongs to) L(M) Intersection L(M')}

2. {<M>| M is a TM, and M is the only TM that accepts L(M) = { } = empty set}

I think this problem is decidable as we can construct another TM which have different encoding compares to given TM, which also accepts  {} = empty set.

Ryt??

3. {<M> | M is a TM, and |M| < 100}

here, does |M| < 100 means we are talking about binary encoding of the TM, whose decimal value must be less than 100.

Binary Encoding:- 0^{no of states}10^{no of input symbol}10^{no of tape symbol}1... like this other information.

Ryt??

Comments

All three are talking about TM and not about their language

So, all should be decidable

rt?

---

...................

---

U mean in question u want to replace Turing Machine with Language accepted by TM

right?

---

I mean to say in the question if they give both the attributes TM and its language then how to solve, because I don't find any particular way to approach such kind of problems.??

---

1) must be phi as it not in L(M) and L(M'). So, such language cannot exists
2) undecidable
3) R.E. language. Here yes cases possible

It will be answer. Can u confirm me plz these are ans or not

---

@Srestha.

All above problems are decidable!!

---

All are decidable but how?

I checked many links

but these are all language property not TM property

Qs should be like this

L= {<M,w>| M is a TM, and w is a string, and there exist a TM, M' such that w (does not belongs to) L(M) Intersection L(M')}

If all are TM property then ans will be all decidable

---

See if all are TM property

Qs should state like this

{<M> | M is a TM, and |M|  has less than 100 states}

but here not talking about states, then it must talking about language :(

---

PLZ EXPLAIN THIS ONE....

---

@ srestha, why are your statement

If all are TM property then ans will be all decidable

is wrong.

Note. Properties of TMs, as opposed to those of languages they accept, may or may not be
decidable.

---

hey were u able to understand this question?? i have same doubt

Answer 1

1st. One is  decidable

2 nd one is undecidable

3rd is also decidable

Comments

@sajal singh please specify the steps too.

---

1  according to a theoram if L is recursive

Enumerable and L' is also recursive enumerable then both are recursive and recursive are closed under intersection so therefore. Their will be a member ship algorithm so that's why it is decidable

2 since empty string is undecidable so therefore it is also undecidable

3 rd since we have a utm which recognize binary encoding of tm so therefore we  can

Do this problems