1
$\begingroup$

I'm trying to prove that $\mathrm{Inf}=\{\langle M\rangle\mid L(M)= \infty\} \notin R$ where $R$ is the group of all decidable languages.

I'm trying to make a reduction from The acceptance problem $A_{TM}=\{\langle M,w\rangle\mid $ $M$ accepts $ w\}$ which is not in R.I'm new to these reductions, so I'm not sure if I'm doing it well. and I This is my reduction, I wonder if it is correct.

$f(\langle M\rangle,w)=\langle M'\rangle$.

Given $\langle M\rangle,w$ I'll create a new Turing machine $M'$. For an input $x$: 1.if $x \ne w$, $L(M')=\{1\}$, otherwise if $x=w$ I'll emulate eunning of $w$ on $M$ if $M$ accepts, $L(M')=\Sigma^*$, otherwise $L(M')=\{1\}$, in this way $L(M')=\infty$ iff $M$ accepts $w$.

Is this correct?

  • 0
    Please use `\langle` and `\rangle` instead of `<` and `>` in this context. The latter are *relation* symbols, and not only look different, but also produce the wrong spacing. I fixed it for you (along with some other minor TeX fixes).2012-08-01

1 Answers 1

1

The description of the Turing machine $M'$ you construct is a little suspect. You should be describing what $M'$ does on any input $x$, but instead you seem to be using the input $x$ of $M'$ as a parameter for determining its language, which leaves the language of $M'$ somewhat indeterminate.

Consider the following: Assume that $M$ does accept the string $w = 001001$. Now based on your description of $M'$, on input $001001$ the language of $M'$ is everything, and therefore $M'$ will accept the string $000$. But, again, based on your description of $M'$, on input $000$, since $000 \neq w$ then the language of $M'$ is $\{ 1 \}$, and since $000 \neq 1$ it follows that $M'$ does not accept $000$. Note that we cannot decide what $M'$ is supposed to do on input $000$! (And similarly for basically every string.)

Instead of varying the output of $M'$ on different inputs, why not ensure that $M'$ does the exact same thing regardless of the input it is given? (You can still emulate $M$ on input $w$, however....)

  • 0
    Thank you.I understand what you are saying. (I don't have 15 reputation so I can't vote up). can do it however this following way? Emulate w on M. If M accepts M' accept x, otherwise M' accepts only {1} or reject x. Is it now correct? since If M accepts w, basically M' accept all x, and if M does not accept w, the language of M' is finite.2012-08-01
  • 0
    @Joni: I would have done it slightly differently: on any input $x$ the new TM $M'$ emulates $M$ on input $w$ and will accept/reject $x$ exactly as $M$ accepts/rejects $w$. But your idea is now perfectly sound.2012-08-01
  • 0
    Thanks a lot @Arthur Fischer.2012-08-01