# Differences between ALLTM and INF

The definitions of ALLTM and INF are as follows:

$$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM M such that L(M) = \Sigma^*} \}.$$

$$\mathrm{INF} = \{ \langle M \rangle \mid \text{TM M such that L(M) is infinite} \}.$$

In one of the proofs of undecidability of INF, they reduce $$A_{TM}$$ to INF as follows:

Given $$\langle M,w \rangle$$, construct $$M'$$ : "On input $$x$$, simulate $$M$$ on $$w$$. If $$M$$ accepts w, then Accept". Clearly, $$M$$ accepts $$w$$ when $$L(M) = \Sigma^*$$. "

Here, the proof for INF proof used the definition of ALLTM to show that the reduction is valid.

Can we use INF and ALLTM interchangeably? If not, what are some crucial differences in these sets?

Given an instance $$M$$ of ALLTM, construct a Turing machine $$M'$$ which on input $$x$$ runs $$M$$ on all inputs $$y \leq x$$ (in some arbitrary computable ordering of all strings). Then $$M$$ is total (i.e., halts on all inputs) iff $$M'$$ halts on infinitely many inputs.
Given an instance $$M$$ of INF, construct a Turing machine $$M'$$ which on input $$x$$ runs $$M$$ in parallel on all inputs $$y \geq x$$, and halts once one of the runs halts. Then $$M$$ halts on infinitely many inputs iff $$M'$$ is total.
(In fact, both ALLTM and INF are $$\Pi_2$$-complete.)