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
    Thanks a lot @Arthur Fischer.2012-08-01