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