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:

- Run $ M$ on $ w$ and return its result
- 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$ ?