I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. This is the reduction:

$M_f$: Given an input of $\langle M, w\rangle$, where $M$ is a $TM$ and $w$ is a word:

Define a TM $M_1$:

Given the input $x$ do:

  1. Run $M$ on $w$ and return its result
  2. Return $\langle M_1\rangle$

This is correct for $ALL_{TM}$ because if $M$ accepts $w$, $L(M_1)=\Sigma^*$, whereas if it rejects, $L(M_1)=\emptyset$

However, it is also given as a solution for $A_{TM} \leq_M INFINITE_{TM}$, where

$INFINITE_{TM}=\{\langle {M \rangle} |$ $M$ is a $TM$, $L(M)$ is an infinite language $\}$, for example here: http://www.sfu.ca/~kabanets/308/lectures/lec7.pdf

I don't fully understand why theirs, or other similar explanations, are correct. What about infinite languages that aren't $\Sigma^*$? What about finite languages that aren't $\emptyset$?


1 Answer 1


The m-reducibility definition says

Language $A$ is m-reducible to $B$ (denoted $A\leq_mB$) if there is a computable function $f:\Sigma^* \rightarrow \Sigma^*$ such that for every $w\in \Sigma^*$, $$w\in A \iff f(w)\in B$$

The point you should pay attention to is that there is no need to talk about every $x\in B$. If you can map all elements of $A$ to one special element of $B$ say $x_0$ and all strings that don't belong to $A$ to string which doesn't belong to $B$ say $y_0$ then you are done!

Maybe if you think of $A\leq_m B$ as language $B$ is harder than $A$ then you feel better about the reduction. This means if you can decide $B$ then you also can also decide $A$.

So by the proof, you have provided we map every $\langle M,w\rangle \in A_{TM}$ to $\Sigma^*$ and every $w' \notin A_{TM}$ to $\emptyset$. Thus $INFINITE_{TM}$ is harder than $A_{TM}$. If you could decide just one elements of $INIFINITE_{TM}$ which is $\langle M \rangle$ that $L(M)=\Sigma^*$ then you could decide $A_{TM}$.


Your Answer

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

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