Which of the following is/are undecidable?
- A = { M| M is TM that accepts exactly all the odd length strings}
- L = { M|M is a TM and L(M) is infinite}
- EQ = {<D,E> | D is a DFA , E is a regular expression and L(D) = L(E) }
Here is my doubt:
option a: we can construct a TM which goes to final state for odd lengths and for even goes to non-final , since TM we are able to create for it hence DECIDABLE
option b: Languages accepted by TM are also called Turing recognizable i.e nothing but recursively enumerable languages and these languages are undecidable for infinite problem hence , UNDECIDABLE
option c: straight forward it’s decidable
According the key option ‘a’ is also UNDECIDABLE why is that, where am I going wrong and is the idea I’ve thought for option ‘b’ correct?