Problem Detail: Ok so I understand how $mathrm{ATM} = {langle M,w rangle mid text{$M$ is a TM and $M$ accepts $w$}}$ is undecidable. Is this because $w$ is a variable? What if the parameter is fixed? Consider $mathrm{BTM} = {langle M,w rangle mid text{$M$ is a TM and $M$ accepts the string 101}}$. BTM is decidable right? The diagnolization problem here doesn’t seem to apply because it would seem trivial to build a Turing machine that is 100% capable of accepting only the input “101” and rejecting every other possible input, correct? And our machine would always reject itself as an input, since it only accepts “101”, right?
Asked By : Daniel Baughman
Answered By : Roi Divon
You can show that $mathrm{BTM}$ is undecidable with a simple reduction from $mathrm{ATM}$. Let $langle M,wrangle in ATM$. We define the reduction function $f$, $mathrm{HP} leq mathrm{BTM}$ as follow: $f(langle M,wrangle) = M_w $, Where $M_w$ on every input $x$, runs $M$ with input $w$. if $M$ stopped, then $M_w$ accepts $x$. if $M$ rejects, then $M_w$ rejects. Clearly, if $langle M,wrangle in ATM$ then $L(M_w) = Sigma^*$, and in particular $101 in L(M_w)$. if $langle M,wrangle notin ATM$ then $L(M_w) = emptyset$, and $101 notin L(M_w)$. Because $mathrm{ATM} $is undecidable, so is $mathrm{BTM}$. It should be intuitive that $mathrm{BTM}$ is undeciadble, because given a turing machine $M$, you can’t tell if $M$ will halt with input $101$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30401
