Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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). – Harald Hanche-Olsen Aug 1 '12 at 8:29
up vote 1 down vote accepted

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

share|cite|improve this answer
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. – Joni Aug 1 '12 at 8:28
@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. – arjafi Aug 1 '12 at 8:51
Thanks a lot @Arthur Fischer. – Joni Aug 1 '12 at 8:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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