Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$.
Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable?
But isn't $L$ decidable since it is possible to make a CFG (or PDA) of that language. And if I can make a reduction, $L$ would become not decidable because of $A_{TM}$.
-
1$\begingroup$ Have you seen Rice's Theorem? $\endgroup$– Rick DeckerJan 31, 2020 at 15:22
1 Answer
The decision problem that corresponds to $L$ deals with the behaviour of Turing machines, not with strings of $1$'s and $0$'s.
More precisely, the decision problem is
Given a Turing machine $M$, is it the case that $L(M) = \{ 1^n0^n \mid > n \geq 0 \}$
A decider for this decision problem would take as input the description $\langle M \rangle$ of an arbitrary Turing machine $M$ and tell us if $M$ accepted exactly those strings that are of the form $1^i0^i$ for some $i \geq 0$. A pushdown automaton that recognizes the language $\{ 1^n0^n \mid > n \geq 0 \}$ is clearly not such a decider.
A reduction from $A_{TM}$ to $L$ will, given an instance $\langle M,w \rangle$ build a description $\langle M' \rangle$ such that
$$M \text{ accepts } w \iff L(M') = \{ 1^n0^n \mid > n \geq 0 \}$$
Here is $M'$:
On input $x$
- If $x \neq 1^i0^i$ for some $i \geq 0$, reject
- Else simulate $M$ on $w$ and answer what $M$ answered.
Clearly, if $M$ accepts $w$ then $L(M') = L$. If $M$ does not accept $w$, then $L(M') = \emptyset$.