1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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