1
$\begingroup$

I'm asking this, because in every exercise I check if I can relate it to one of the things I know,

like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{TM}}$, $ALL_{TM}$

But in many cases I can not find the connection and then get stuck with the question.

For example:$$L = \big\{ \langle M \rangle \mid M \text{ is TM and }M \text{ accepts only palindromes}\big\}$$ I know the solution to this question, I am not asking for a solution to this.

I want to understand the line of thought so that I will begin to solve questions like this. What are the guidelines?

What is the first thing that should come to my mind with such questions?

My initial thought was always to look for words like accepts to associate it to $A_{TM}$, $\overline{A_{TM}}$ or halts to associate it to ${HALT_{TM}}$,$\overline{HALT_{TM}}$ but that does not help me so much.

My questions are not only related to the example but to the questions in general of this kind, that I need to determine.

Thanks.

$\endgroup$
1
$\begingroup$

The line of thought that I find the most fruitful is: try to come up with a (semi)algorithm for the problem. If you succeed, great. If you don’t, it’s probably impossible.

Let’s apply it to your problem: determining whether a Turing machine accepts only palindromes. The trivial way to solve this problem is to go over all non-palindromes, and check whether your Turing machine accepts any of them. This shows that your problem is co-r.e., since you can enumerate all Turing machines which accept some non-palindrome.

There doesn’t seem to be a matching algorithm for enumerating Yes instances of your problem, so your problem is probably not r.e. Indeed, Rice’s theorem shows that your problem isn’t recursive, and so we can deduce that it is not r.e.

With a bit more work, you can show that your problem is $\Pi_1$-complete, that is, every problem in co-r.e. can be (effectively) reduced to it. To show this, it suffices to show a reduction from the non-halting problem to your problem. In this problem, given a machine $M$ and an input $x$, the goal is to determine whether $M$ does not halt on $x$. Given an instance $\langle M,x \rangle$ of this problem, construct a machine $M’$ which goes into an infinite loop (or rejects) unless the input is $10$ (an arbitrary non-palindrome), in which case it simulates $M$ on $x$, and then accepts (if $M$ ever halts). The new machine $M’$ accepts only palindromes if and only if $M$ doesn’t halt on $x$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Because it is possible to check whether a TM will receive a non-palindrome string by simulate the TM $M$ on all non-palindrome strings and disqualifying the TM that accept one of them, so this mean this TM is $M \in \overline{L}$ then all these TM $M$ that $M \in \overline{L}$ can be enumerate. Such testing can not be done to test the machines which accept only palindromes because I'll need to check TM $M$ by running it on all palindrome strings, infinite amount of them and to check if the TM accepts them all, this is impossible so I don't have an algorithm, therefore $L$ is unrecognizable? $\endgroup$ – Asaf Jul 31 '18 at 16:55
  • $\begingroup$ This kind of informal reasoning does not constitute a proof, but often gives the correct answer. $\endgroup$ – Yuval Filmus Jul 31 '18 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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