1
$\begingroup$

I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ and, since $\overline{A_{\mathrm{TM}}}$ is not Turing-recognizable, then $L$ is not Turing-recognizable.

I think that $\overline{L} = \{M\mid L(M) \text{ is finite} \}$ and that it means that $L(M)$ contains a finite number of strings.

I don't know how to construct a Turing machine that can prove $A_{\mathrm{TM}}\le_\mathrm{m} \overline{L}$.

$\endgroup$
  • $\begingroup$ Note the distinction between "contains finite elements" and contains "finitely many elements". "Finite" isn't a number, and "contains finite elements" means "contains elements that are finite". Since all elements of $L(M)$ are finite by definition, "contains finite elements" probably isn't what you intended, so I edited. $\endgroup$ – David Richerby Nov 7 '18 at 21:47
1
$\begingroup$

Recall that the input to the halting problem is a pair $(\langle M\rangle, w)$ and we must accept this input if $M(w)$ halts, and reject it otherwise.

We want to decide the halting problem by reduction to $\overline{L}$. That is, we need to produce a computable function $f$ that takes an input $(\langle M\rangle, w)$ and produces a string in $\overline{L}$ if $M(w)$ halts and a string that is not in $\overline{L}$ if $M(w)$ does not halt.

There's a small mistake in your reasoning in the question that's worth mentioning at this point, but it doesn't make any real difference. Strings in $L$ are descriptions of Turing machines that accept infinitely many inputs. That means that a string is in $\overline{L}$ if either it's a description of a Turing machine that only accepts finitely many inputs, or if it's not a description of any Turing machine at all.

However, we can ignore the strings that don't describe Turing machines and design a function $f$ such that $f(\langle M\rangle,w)$ is always the description of a Turing machine and that Turing machine accepts only finitely many inputs if $M(w)$ halts, and is one that accepts infinitely many inputs if $M(w)$ doesn't halt.

Hint: $\emptyset$ is finite and $\Sigma^*$ is infinite. Transform $(\langle M\rangle,w)$ into the string $\langle M'\rangle$ such that $M'$ will accept nothing if $M(w)$ halts and will accept everything if $M(w)$ doesn't halt.

There's another hint below, which you can see by mousing over the yellow box. But try to figure it out on your own, first.

Hint 2: the reduction is very similar to the one used to prove that the problem "Does $M$ halt on the empty input?" is undecidable.

$\endgroup$
  • $\begingroup$ Unless I missed something, I think your first hint is misleading: I can make $M'$ accept finitely many strings if $M(w)$ halts (and everything otherwise), but I can't make it accept nothing. This is enough to prove the reduction, but not in the way you suggest. $\endgroup$ – chi Nov 8 '18 at 12:33
  • $\begingroup$ Maybe I've missed something! I'll have a look this evening, if I remember. $\endgroup$ – David Richerby Nov 8 '18 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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