I'm trying to prove a problem that a friend sent me, he is saying that my solution is not good and I wanted to ask if he is correct and im wrong , and if so why? here is the questions:

$L=\{<M>| \text{ M accept all languages with no more then 1 palindrome}\}$

prove that L is not decidable by showing that : $H_{TM} \leq_T L$

(Definition of $H_{TM}$)

$H_{TM}=${$((<M,w>)|$$M$ stops on $w$}

here is my solution:

define $M_P$ machine that runs $M$, on $w$ ,if $M$ stops ,$M_P$ will accept if it get an input=131 otherwise loop (accept only one palindrome).

this is my function:

$$ f(<M,w>) = \begin{cases} \Sigma^* & \text{ } if <M> Bad_.Encoding \\M_P & \text{if }<M,w> \in H_{TM}.\end{cases} $$

my idea is the next: if we have bad encoding , we put $\Sigma^*$ which has more then 1 palindrome, else , we run $H_{TM}$ with $<M,w>$ , if we accept we put our $M_P$ which will accept for our L.

thank you!

  • $\begingroup$ You should include a definition of $H_{TM}$ in your question. $\endgroup$ – roctothorpe Dec 27 '17 at 19:41
  • $\begingroup$ It includes the definition, how is that? $\endgroup$ – secret Dec 28 '17 at 9:22

Your Answer

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

Browse other questions tagged or ask your own question.