closed by
321 views
1 votes
1 votes

REVERSE = { M | M is a TM with the property: for all w, M(w) accepts iff M(wR) accepts}

Here getting confused for applying condition to apply Rice's theorem for the given property 

Tyes={Palindromes}    Tno={Non-palindromes} 

Because of which it is non-trivial property and hence Turing Undecidable(according to Rice's theorem)

Is my analysis above is correct here ?

and is it Turing Recognisable ?can we apply Rice's 2nd theorem?

Source:https://goo.gl/UIhNyT  (Problem 1)

closed by

Related questions

0 votes
0 votes
0 answers
1
Sparsh-NJ asked Aug 6, 2023
227 views
If G is a CFG then L(G) = (Sigma)* is Decidable or Undecidable?The reference where I solved this question says this is an Undecidable problem! But I think it's Decidable ...
0 votes
0 votes
0 answers
2
jatin khachane 1 asked Jan 8, 2019
737 views
L1 = { <M | M halts on $\epsilon$ }L2 = { <M | $\epsilon$ $\in$ L(M) }Which one is RE or not RE
1 votes
1 votes
0 answers
3
srestha asked Dec 6, 2018
381 views
Where can we apply PCP to check, if the grammar is undecidable?Some examples of such grammars Ambiguous grammarAny other example and how they solved with PCP?