Must an algorithm terminate?

Question

I am confused. Sometimes i read about terminating and not terminating algorithms. I almost always read these things in the context of turing machines. This means to me: There are algorithms which terminate and others which don't.

But for example the german wikipedia page for algorithm says that an algorithm always must terminate:

https://de.wikipedia.org/wiki/Algorithmus#Turingmaschinen_und_Algorithmusbegriff

"4. Das Verfahren darf nur endlich viele Schritte benötigen."

This brings me to my question:

Does every turing machine represent an algorithm, or only the turing machines which terminate for a at least one input? Or: Must an algorithm terminate, or is it okay if an algorithm runs forever? Maybe i do not really understand the formal definition of the word "algorithm"?

Best regards

Kevin

Answer 1

Even a Turing machine that never finishes regardless of its input can be said to 'solve a problem' (i.e., implement a recursive function), namely, the unique recursive function with empty domain.

The necessary condition in the article you quote is not that the Turing machine must be guaranteed to halt, only that is must be guaranteed to halt for every input in the domain of the recursive function (jede Eingabe, die eine Lösung besitzt).

Answer 2

The question you asked is more of a philosophical one instead of a mathematical one. Your question depends on the more general and fascinating question, “What is an algorithm?” Let me explain:

Everything involving computer science and computation in general can be thought of in terms of algorithms: recursive functions, programming languages, programs, computers, operating systems, etc. In the early days, the notion ‘all good algorithms can be translated into some halting Turing machine’ would have been widely accepted. Today, however, halting Turing machines do not maintain the high status they once held. There is an apparent information gap when we try to reduce so called interactive and parallel algorithms into halting Turing machines. Intuitively this can be understood as trying to reduce a windows operating system into a halting Turing machine (sounds ridiculous right?). The ridiculousness of this task stems from the fact that, ideally, an operating system like windows should never halt. You don’t want to be on Microsoft word and suddenly the algorithm ‘halts’ without being given specific instructions. Operating systems are definitely algorithms (a system of specific instructions for given inputs), but for long drawn out projects we might want our operating system to run indefinitely. So in regards to your question “Must an algorithm terminate?” in my personal opinion the answer is no. Similarly, in regards to the question, “Are all algorithms translatable into some halting Turing machine?” my answer is also no.

Many of the ideas I have suggested here were brought to my attention by the work of algorithm master Yuri Gurevich (Russian mathematician and computer scientist who now works for Microsoft). Gurevich has attempted to generalize the concept of algorithm with something he calls ‘abstract state machines’: a system for formalizing algorithms including the non-Turing-machine-convertible algorithms (like interactive and parallel algorithms). ‘Abstract state machines’ have been met with wide acclaim and there are learned societies focused solely on them.

To find more information on the work of Yuri Gurevich check out these two lectures:

Yuri Gurevich, Church Turing Thesis: Story & Recent Progress (2009) https://www.youtube.com/watch?v=7XfA5EhH7Bc

Yuri Gurevich, What’s an Algorithm? (2011) https://www.youtube.com/watch?v=FX2J24u92GI