Science Forums 2

[CraigD]

Originally Posted by stereologist

The stopping criteria is part of the definition used in the theory of algorithms. Here is the Wikipedia page.
Algorithm - Wikipedia, the free encyclopedia

It says "eventually terminating in an end-state".

Note that further in that article, in it’s “(Formalization of algorithms) Termination” section, it explains

Some writers restrict the definition of algorithm to procedures that eventually finish. In such a category Kleene places the "decision procedure or decision method or algorithm for the question" (Kleene 1952:136). Others, including Kleene, include procedures that could run forever without stopping; such a procedure has been called a "computational method" (Knuth 1997:5) or "calculation procedure or algorithm" (Kleene 1952:137); however, Kleene notes that such a method must eventually exhibit "some object" (Kleene 1952:137).

States simply, in the language of the wikipedia article’s “Expressing algorithms” section, this ambiguity can be resolved by answering the question “is every Turing machine’s state table the formal description of some algorithm?”

I though little about this distinction until, years after my last academic experience with Turing machines, I read the Turing Machines chapter of Penrose’s 1989’s “The Emperor’s New Mind”. In this chapter, Penrose presents a universal Turing machine (one with an alphabet consisting on only 0 and 1), and asks the question of what it does if presented with every possible tape, beginning with one representing zero, and counting by one, noting and discussion the first one that terminates, the first that does something “useful”, and so on. IMHO, this chapter is one of the best presentations of Turing machines ever written.