1
$\begingroup$

during school exercises we worked on decidability problems and there was one I don't really understand. We were provided with solution and explanation regarding this exercise but still I need more guidance.

The problem is:

Proof that $L = \{ <M> | M$ is Turing machine, $ |L(M) \cap \{a,b\}|= 1\} \notin REC$

Idea of proof:

  1. reduction from Halting problem
  2. machine $M_x$ (output of reduction function) checks if on its input is $a$, saves this information
  3. if $<M_h,W_h>$ (instance of HP) does not have required structure, $M_x$ rejects
  4. $M_x$ simulates $M_h$ on $W_h$, if $M_h$ accepts, $M_x$ accepts if on its input it had $a$, otherwise rejects... if $M_h$ is in loop $M_x$ is in loop also

then

  • $L(M) = \emptyset$ if $<M_h,W_h>$ has structure corrupted or $M_h$ is in loop on word $W_h$
  • $L(M) = \{a\}$ if $<M_h,W_h>$ has correct structure and $M_h$ halts

How I see it:

  • $M_x$ saves information of its input
    • if $M_h$ halts, $M_x$ checks saved information regarding input, if it contains $a$ or $b$ accepts, otherwise rejects

then

  • $L(M) = \emptyset$ if $<M_h,W_h>$ has corrupted structure or $M_h$ is in loop on word $W_h$
  • $L(M) = \{a\}$ if $<M_h,W_h>$ has correct structure and $M_h$ halts with input $a$
  • $L(M) = \{b\}$ if $<M_h,W_h>$ has correct structure and $M_h$ halts with input $b$

I do not understand what happened with $b$.

$\endgroup$

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.