0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Have you seen Rice's Theorem? $\endgroup$ Jan 31, 2020 at 15:22

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.