3
$\begingroup$

It's known that the following language, the so-called acceptance problem is undecidable:

$A_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\}$

The proof is by contradiction: Assume there is a TM $H$ which decides $A_{TM}$. Let $D$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D$ simulates $H$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H$ rejects this input and rejects, if $H$ accepts it. That is, $D$ accepts $\langle M\rangle$ if $M$ rejects its own code, and vice versa. Running $D$ on its own code, $\langle D\rangle$, leads to contradiction.


Let's restrict $A_{TM}$ by excluding all input strings which encode a TM:

$E = \{w\,\vert\,w\text{ is a structurally valid encoding of a TM}\}$ $A'_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\text{ and }w\not\in E\}$

I'd like to know whether $A'_{TM}$ is also undecidable.

I tried to prove it the above way: Assume there is a TM $H'$ which decides $A'_{TM}$. Let $D'$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D'$ simulates $H'$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H'$ rejects this input and rejects, if $H'$ accepts it. The problem is that running $D'$ on its own code, $\langle D'\rangle$, doesn't necessarily lead to contradiction. I mean since $\langle D',\langle D'\rangle\rangle$ is not a member of $A'_{TM}$, we don't know what $H'$ will do with it.


Note: An encoding of TMs, and TMs along with an input string

Let $M = (Q, \Sigma, \Gamma, \delta, q_{i}, q_{a}, q_{r})$ be a TM, where

  • $Q$ is the set of states,
  • $\Sigma = \{0, 1\}$ is the input alphabet,
  • $\Gamma$ is the tape alphabet ($\Sigma\subset\Gamma$),
  • $\delta: (Q-\{q_a, q_r\})\times\Gamma\rightarrow Q\times\Gamma\times\{L,R,S\}$ is the transition function,
  • $L$, $R$ and $S$ denote the respective head movements, "left", "right" and "stay", and
  • $q_i$, $q_a$ and $q_r$ are the initial, accepting and rejecting state, respectively.

Let's assign a unique positive integer to each element of $Q$, and do the same in case of $\Sigma$, $\Gamma$ and $\{L,R,S\}$. Now every transition rule $\delta(p, a) = (q, b, m)$ can be encoded as $\langle p\rangle 1\langle a\rangle 1\langle q\rangle 1\langle b\rangle 1 \langle m\rangle$, where $\langle x\rangle$ denotes a sequence of $0$'s, with length being equal to the positive integer assigned to $x$. The encoding of $M$, denoted by $\langle M\rangle$, can be created by concatenating its transition rules, separated by $11$'s. The combined encoding of $M$, and an input string, $w\in\Sigma^*$, denoted by $\langle M,w\rangle$ is $\langle M\rangle111w$.

$\endgroup$
  • 3
    $\begingroup$ You just need to tweak $D$ a bit - the general idea is the same. Instead of $\langle M \rangle$, encode the input in such a way that (1) you can decode $\langle M \rangle$, and (2) it's not a valid encoding of a TM. $\endgroup$ – Yuval Filmus Aug 16 '13 at 14:05
3
$\begingroup$

The complication forbidding the input from being an encoding of a Turing machine is easy to overcome. All you need to do is tweak $D$ a bit, so that instead of accepting an encoding $\langle M \rangle$ of a Turing machine, it accepts some other input which can be decoded into an encoding of a Turing machine, while at the same time not being an encoding of a Turing machine itself.

$\endgroup$

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.