Comment by dTal

I'd say that it is a trivially answerable question - "no, we cannot recognize arbitrary infinite loops" is the answer. It is easy to encode difficult-to-prove statements about number theory into loops. Consider a program that searched for a counterexample to the Collatz conjecture, or the Riemann Hypothesis.