closed by
319 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
224 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
722 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
378 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?