[Solved]: Undecidability of a restricted version of the acceptance problem

Problem Detail: 

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

Asked By : kol

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13771