# Is L decidable or not

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

• Have you seen Rice's Theorem? Jan 31, 2020 at 15:22

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

1. If $$x \neq 1^i0^i$$ for some $$i \geq 0$$, reject
2. 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$$.