Does an algorithm have to terminate?

Question

I was reading about the finiteness property of an algorithm where it is mentioned that

the algorithm must always terminate after a finite number of steps.

Does this mean that any pseudo-code cannot contain infinite loops or it should be equivalent to Halting Turing Machine. I don't know whether the statement about finiteness property of an algorithm is correct or not. I have not found any reliable source for it and I have not read it in CLRS.

My question is whether the statement and whether my interpretation about it is correct:

An algorithm must always terminate after a finite number of steps

References:

• Intro Problem Solving in Computer Science, CS@VT (Page 3)
• Wikipedia article on Algorithm_characterizations
• Data Structures and algorithms, CmpE, Boun

Answer 1

Yes, an algorithm should always stop after a finite number of steps, otherwise we would call it a procedure or process or computation specification. A procedure that doesn't halt for certain inputs can be considered partial algorithms. Algorithms are more useful, since they terminate for any input.

An algorithm can be viewed as a function $f: \mathbb{N} \to \mathbb{N}$. if it is defined for all input values, we say that $f$ is "total" ; for an algorithm, it means that it halts for any input. On the other hand, if a function $f$ is "undefined" for an input, say $4$, we say that $f$ is a partial function, and in computation theory, we write $f(4)\uparrow$ meaning it "diverges", or simply "doesn't halt".

An example for a partial function can be the inverse of the integer square function, i.e. $sq(n) = n^2$. The inverse, $sq^{-1}$ is defined only on perfect squares, that is, $$sq^{-1}(n) = \cases{\sqrt{x} \text{ if $x$ is a perfect square} \\ \text{undefined otherwise.}}$$

Answer 2

I find this a particularly interesting question, one that I have pondered myself a couple of times.

The set of algorithms is usually defined as consisting of a finite number of instructions, and also executing in a finite number of steps. In other words, algorithms halt. But the halting problem also says that if someone is presented with a finite set of instructions, there is no universally applicable decision procedure to figure out if it actually will finish executing, i.e. whether it is an actual algorithm.

For instance, in

http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

"unbounded algorithm" would be a contradictio in terminis.

I personally advocate dropping the finiteness requirement from the definition of an algorithm. An algorithm must consist of a finite number of instructions, but it does not necessarily terminate in a finite number of steps. This definition avoids getting into a mess.

for (i = 0; i < 1e99; i++)
        puts("This is an algorithm");

while (true)
        puts("This is not an algorithm");

Just doesn't add up.

Answer 3

Well, I could write a program that will print all the Fermat primes in ascending order, given enough time. A tiny change: Make it print the first 40, 41, 42, etc Fermat primes and it becomes an algorithm. So you can say “it’s not exactly an algorithm, but as good as”.

Or I write software connected to a camera that detects known wanted criminals. You’d want that software forever, so it’s not an algorithm. Change it to stop running after 100 billion years, and it becomes an algorithm.

So finite number of steps is a technical requirement for an algorithm, but in practice it’s not very relevant. (Of course if I take any problem and add “stop after 10 billion years” then the Halting Problem for this program is easy. Deciding whether it halts in less than 10 billion years is a bit harder. )

So to be called an algorithm it must always halt. To be useful, not necessarily.

Answer 4

There isn't a good formal definition of "algorithm" at the moment, and this is one of those corner cases.

For the purpose of determining how long an algorithm takes to run, an algorithm must terminate. But there is a large cohort of computer scientists who analyse "algorithms" which don't terminate because they are cooperating processes (e.g. operating systems, servers, stream processors), but still do useful work and actually progress, rather than unproductively looping forever.

Rather than doing induction on data, we refer to this as doing codinduction on codata, the "co-" prefix referring to the category dual. And such "algorithms" may not terminate, but they might coterminate.