Problem Detail: It’s known that the following language, the so-called acceptance problem is undecidable: $A_{TM} = {langle M,wrangle,vert,Mtext{ 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 Mrangle$ as input, $D$ simulates $H$ on $langle M,langle Mranglerangle$, and accepts, if $H$ rejects this input and rejects, if $H$ accepts it. That is, $D$ accepts $langle Mrangle$ if $M$ rejects its own code, and vice versa. Running $D$ on its own code, $langle Drangle$, leads to contradiction. Let’s restrict $A_{TM}$ by excluding all input strings which encode a TM: $E = {w,vert,wtext{ is a structurally valid encoding of a TM}}$ $A’_{TM} = {langle M,wrangle,vert,Mtext{ is a TM which accepts }wtext{ and }wnotin 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 Mrangle$ as input, $D’$ simulates $H’$ on $langle M,langle Mranglerangle$, 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’ranglerangle$ 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 ($SigmasubsetGamma$),
- $delta: (Q-{q_a, q_r})timesGammarightarrow QtimesGammatimes{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 prangle 1langle arangle 1langle qrangle 1langle brangle 1 langle mrangle$, where $langle xrangle$ denotes a sequence of $0$’s, with length being equal to the positive integer assigned to $x$. The encoding of $M$, denoted by $langle Mrangle$, can be created by concatenating its transition rules, separated by $11$’s. The combined encoding of $M$, and an input string, $winSigma^*$, denoted by $langle M,wrangle$ is $langle Mrangle111w$.
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
