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
    Sep 29 '14 at 7:47
  • $\begingroup$ Just quote Rice's theorem! $\endgroup$
    – Ryan
    Sep 29 '14 at 13:54
  • $\begingroup$ What's the use of $w$ in BTM? $\endgroup$
    – 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$

  • 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$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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