Is this variant of ATM decidable?

Question

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?

Answer 1

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$

Answer 2

BTM is also undecidable, with a similar diagonalization proof. Suppose the Turing machine $M$ decided BTM. Define a Turing machine $T$ that, on input $x$ an encoding of a Turing machine, it computes the encoding $y_x$ of a Turing machine which runs the Turing machine encoded by $x$ on input $x$; if $M(y_x)=1$ then $T$ gets into an infinite loop, and otherwise it halts. Then $T$ halts on input $\#T$ (where $\#T$ is the encoding of $T$) iff $M(y_{\# T})=0$ iff $y_{\# T}$ doesn't halt on 101 iff $T$ doesn't halt on input $\#T$, contradiction.