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$
1
  • $\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$ Nov 7, 2018 at 21:47

1 Answer 1

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$
3
  • $\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, 2018 at 12:33
  • $\begingroup$ Maybe I've missed something! I'll have a look this evening, if I remember. $\endgroup$ Nov 8, 2018 at 12:42
  • $\begingroup$ Was thinking if this simple argument is valid: "keep generating strings infinitely on given alphabet and make Turing Machine dovetail on these strings. It may accept some and/or reject some strings. But, at any point in time, when TM has rejected some number of strings, we will never know if it will accept any string in future, making it impossible to say its language is infinite. Hence not recognizable." $\endgroup$
    – RajS
    Jan 14, 2020 at 8:46

Your Answer

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

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