Recognition of Undecidable Propositions(infinite loop)

Question

Say I want to find a natural number n which n+n=3 To solve this computationally, I would run an algorithm:

int n = 1;
while(n+n!=3)
    n++;
System.out.println(n);

Of course we know that this loop is an infinite loop. But is there an algorithm that can predict whether this loop will be infinite or finite? (similar but different from the halting machine, since my desired algorithm only examines this loop while the halting machine can examine all loops) If there is, what would be the algorithm be?

Answer 1

In answer to the specific question asked ("is there an algorithm that can predict if this loop will be infinite or finite"), the algorithm would be simply to simply report "INFINITE".

If you are looking for something more general (i.e. work on arbitrary source code), there are algorithms that work on various classes of algorithms/code. But it has been known for a long time that no such algorithm exists for the general case.

Answer 2

While that program is running, its state can be fully defined by the value of the variable 'n' and by the next operation (amongst a finite set of operations) to be executed. An algorithm can simulate the execution of that program step by step, at each step checking whether both the data and the next operation match those of an earlier step. If a match is found, then the algorithm stops the simulation and reports that the program does not halt. If a match is not found, the new state of the program is logged for future comparisons. If there is no further operation to be executed, i.e. the program finishes running by itself, then the algorithm reports that the program halts.

This algorithm is of course very inefficient, but it shows a very general case: that it is possible to predict whether a specific program stops, when that program does not use an arbitrarily large amount of memory (for code and data).