0
$\begingroup$

Before an exam in Computability I go through questions from last year's test. So the question is:

$$A= \{ \langle M\rangle x | M \text{ is a TM and accepts } x \}$$ $$ L = \{ \langle M \rangle | M \text{ is a TM and halts only on words starting with 101 } \} $$ Prove by reduction that $L$ is undecidable. So this should be done without Rice's theorem.

I have troubles with constructing a reduction function, to show $A\leq L$.

Has someone probably some advice for this problem? Thanks in advance.

$\endgroup$

1 Answer 1

0
$\begingroup$

Assume that $L$ is decidable. Then there is a Turing machine, $T$ that, on input $M$ decides whether $M$ halts only on words starting with $101$.

Using $T$, we will be able to decide $A$. Given $\langle M\rangle x$, we would like to decide if $M$ accepts $x$. In order to do that, imagine another Turing Machine $M_x$, that

  1. Does not halt if input does not begin with $101$.

  2. If input begins with $101$ ignores remaining input and simulates $M$ on $x$. If $M$ accepts $x$, $M_x$ halts else does not halt.

Now $M$ accepts $x$ if and only if $M_x$ belongs to $L$ (i.e. $T$ accepts $\langle M_x\rangle$).

$\endgroup$

Your Answer

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

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