TOC Turing machines Decidability

Question

Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable?

L={⟨M⟩∣ M halts on all palindromes}.

How can i use Rice's theorem here?

Tyes={All palidroms} Tno={Signma*}.Will that work here?

M halts on all palindromes means M halts on only palindromes ?

Comments

Same reason is also applicable here, as I told in your previous question.

---

I was thinking the same way.Not getting cough confidence though:)

Answer 1

I think the given language is NOT RE. L is the collection of all such TMs which halts on all palindromes.

I think it's not possible to say that a TM halts on all palindromes, it will keep on checking before we can conclude a TM halts on all palindromes.

Comments

Yes,right. Thanks

Answer 2

We can apply Rice' Theorem here  because:
   1. Its a non trival property as there are some TM which does not halt on all palindrom and some are halt.
  
   2. Its a language property obviously.

So, The above problem is undecidable.