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?

  • $\begingroup$ Note our reference questions. $\endgroup$
    – Raphael
    Commented Sep 29, 2014 at 7:47
  • $\begingroup$ Just quote Rice's theorem! $\endgroup$ Commented Sep 29, 2014 at 13:54
  • $\begingroup$ What's the use of $w$ in BTM? $\endgroup$
    – xskxzr
    Commented May 25, 2018 at 12:08

2 Answers 2


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$

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 29, 2014 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.