Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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
Does not halt if input does not begin with $101$.
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$).
