Differences between ALLTM and INF

Question

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?

Answer 1

The two sets are clearly different – there are Turing machines whose language is infinite but doesn't consist of everything. However, both languages belong to the same Turing degree, that is, each of them can be reduced to the other (computably).

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