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

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