1
$\begingroup$

Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$.

Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$

Is A semi-decidable (Turing recognizable or recursively enumerable)?

My try!

I said it is so here is my proof, tell me if I am way off base or tell me if A ought not to semi-decidable in the first place.

$\underline{Proof}$

A is semi-decidable by The Certificate Theorem, which states that:

If $A\subseteq\Sigma^*$ then $A\in SD$(semi-decidable) iff there is some decidable relation, $R\subseteq \Sigma^* \times \Sigma^*$, such that $\forall x\in\Sigma^*$, $x\in{A}$ iff $\exists y$ such that $R(x,y)$ holds.

We know that if $x\in{A}$ that means that $x=\langle M\rangle$, so we can choose $y = \langle M,w\rangle$ where $w\in{PAL}$. What we know is that when $M$ takes $w$ as an input it will accept (since we choose $w$ as an input), if that is the case then $w\in{L(M)}\subseteq{PAL}$. That means that $A\in{SD}$. QED

Any help would be greatly appreciated, have a great day!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

What you have shown is that the language of Turing machines accepting at least one even palindrome is semi-decidable. However, your question is interested in the language of Turing machines accepting only even palindromes, which is rather different. The complement of this language is the language of Turing machines accepting at least one word which isn't an even palindrome, and so the complement is semi-decidable according to your argument. This still leaves open the question of whether the original language is semi-decidable (and so decidable).

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thank you for the response. Can you give a suggestion on how to tackle this problem? $\endgroup$
    – InsigMath
    Oct 20, 2013 at 20:05
  • $\begingroup$ @InsigMath Hint: Rice's theorem. $\endgroup$
    – David Richerby
    Oct 20, 2013 at 20:39
  • $\begingroup$ We have not learned Rice's Theorem so I don't think it would be appropriate (well okay we have been shown it passively but told not to ever rely on it). $\endgroup$
    – InsigMath
    Oct 20, 2013 at 20:43
  • $\begingroup$ @Yuval: I don't think that "the complement of this language is the language of Turing machines rejecting at least one even palindrome". $\endgroup$
    – Dai
    Oct 20, 2013 at 20:47
  • $\begingroup$ @InsigMath Go read this. Congratulations: you just learned Rice's theorem. OK, if a question specifically states you're supposed to do something from first principles, then you should do that; but there's no such thing as knowledge that it would be inappropriate to use. (Except for insider-trading. ;-) ) $\endgroup$
    – David Richerby
    Oct 20, 2013 at 20:52
1
$\begingroup$

My first hint is that your proof of $A \in SD$ is wrong. Assume that $M$ accepts only even palindromes, how are we supposed to certify that?

However, if you look at $\bar{A}$, which consists of $\langle M \rangle$ such that $L(M) \not \subseteq PAL$, so $M$ must accept some string which not even palindrome. Hint: Can we apply the Certificate Theorem for this case? If so then $\bar{A} \in SD$.

It remains to show if $\bar{A}$ is decidable. If you can show that $\bar{A}$ is undecidable, then we can easily conclude $A\not \in SD$. (How?)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you, I guess I got this backwards since I wanted to show that $\overline{A}$ was not semi-decidable by means of reduction. I will think of showing that $\overline{A}$ is semi-decidable then. $\endgroup$
    – InsigMath
    Oct 20, 2013 at 20:50
  • $\begingroup$ I'm still getting used to how to approach these problems ... thank you for the help though! $\endgroup$
    – InsigMath
    Oct 20, 2013 at 20:51
  • $\begingroup$ Yeah now that I think about it, showing that $\overline{A}$ is semi-decidable by means of the Certificate Theorem would not be too difficult. Then showing it is not decidable by a reduction with maybe the universal Turing machine would not be too hard either... cause I know that if $\overline{A}$ is not decidable, that means that $A$ must also not be semi-decidable! $\endgroup$
    – InsigMath
    Oct 20, 2013 at 20:55
  • $\begingroup$ Why universal TM? We just need to reduce some undecidable problem to it! $\endgroup$
    – Dai
    Oct 20, 2013 at 20:57
  • $\begingroup$ By universal TM I mean $A_{TM} = \{\langle M,w\rangle\ \ |M \textit{ is a Turing Machine and M accepts w} \}$, I could also do it with $HB = \{\langle M\rangle \ | \textit{M is a TM and M halts on a blank tape}\}$ $\endgroup$
    – InsigMath
    Oct 20, 2013 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.