# Is this variant of ATM decidable?

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?

• Note our reference questions. – Raphael Sep 29 '14 at 7:47
• Just quote Rice's theorem! – Ryan Sep 29 '14 at 13:54
• What's the use of $w$ in BTM? – xskxzr May 25 '18 at 12:08

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$

• Hmm thank you I am getting the concept of the behaviour of one turing machine versus a language describing how a set of turing machines behave - still a bit confused. – Daniel Baughman Sep 29 '14 at 6:44

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.