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?

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ Aug 1, 2012 at 8:29

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Joni
    Aug 1, 2012 at 8:28
  • $\begingroup$ @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. $\endgroup$
    – user642796
    Aug 1, 2012 at 8:51
  • $\begingroup$ Thanks a lot @Arthur Fischer. $\endgroup$
    – Joni
    Aug 1, 2012 at 8:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .