[Solved]: Is this variant of ATM decidable?

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,w\rangle \in ATM$. We define the reduction function $f$, $\mathrm{HP} \leq \mathrm{BTM}$ as follow:

$f(\langle M,w\rangle) = 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,w\rangle \in ATM$ then $L(M_w) = \Sigma^*$, and in particular $101 \in L(M_w)$. if $\langle M,w\rangle \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