Algorithms beyond programming

[Buffy]

Originally Posted by CraigD

A good point, IMHO. I tend to equate “algorithm” with “function”, and define function as “something that takes input and returns output”. By this definition, a program that can never end can never return an output, so can’t implement a function.

Well, more formally, a function that does not return does not produce a return value, but that does not prevent it from producing output *while it's running*....

Originally Posted by CraigD

In wider usage, however, algorithm seems to be used more generally to include both programs that can end, and ones that can’t.

And that's what I've always gone with, otherwise, we need a new term for the thingies for which Turing's Halting Machine would return "No!"

SO, anyone want to try to take a shot at really explaining why a "non-halting function/program" isn't an "algorithm?"

To follow, without halt, one aim: There's the secret of success,
Buffy

[Pyrotex]

I've been programming for 30+ years, and I have to agree with the above.
An algorithm is a specific set of instructions that, when executed, will result in a specific end-state or solution.
An algorithm may be expressed in technical English; when it is expressed in a specific computer language, it is often called a "routine" or "program" or "script".
The description of what the algorithm is supposed to accomplish, under all expected conditions, is the
"set of requirements" or the "specifications".
The general term for creating algorithms is "coding", especially if the algorithm is being created in a specific computer language. If it's being created in technical English, it is sometimes called "pseudo-coding".
Algorithm has many synonyms, such as recipe, instructions, procedure, process, especially when used in a non-computer context.

[stereologist]

but I'm not sure how you justify this statement

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".

An infinite loop as mentioned several times here is not an algorithm. It may be a program, but not an algorithm.

[stereologist]

Think of it this way, if a program never ends how do you know that the set of output is the complete set of output?

It's true that programmers appear to be more willing to bend the meaning of words or even abuse the daylights out of English.

[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.

[stereologist]

Still, the issue of termination is an important consideration in the definition of algorithm. Otherwise, it would not have been discussed.
Since all books I've used on the subject of algorithms include termination as a part of the algorithm definition I suspect that allowing nonterminating procedures to be part of algorithms makes the definition not useful.
As Minsky pointed out, if you don't know what the answer is, then what do you do.

[Boof-head]

Halting of algorithms is an "algorithmic problem".

Consider the fact that designing and building a modern electronic computer is algorithmic; it's a process that halts when "a viable, working computer" exists; or when it's plugged in and switched on, i.e. tested.

The test is another algorithm, which halts when the test is successful, or when the faulty machine halts - perhaps catastrophically in a big cloud of smoke.

However, Alan Turing proved that there is no way to determine with certainty if a given algorithm will halt - the only way to find out is to test the machine, or build it (so you can test it). The halting problem is well-understood.

Check out Godel's incompleteness theorem (which you'll see is - consistently - an incomplete theory).

[stereologist]

Boof-head when I read your post I was not sure if you were point out the difference between an algorithm that halts and writing an algorithm that can determine if an algorithm halts.

Although it is true that it is not possible to write an algorithm that can determine if any algorithm does halt, that does not mean that it is not possible to write an algorithm that can determine halting for some algorithms.

Some of the new bug detection software are called static analysis tools. These attempt to analyze some aspects of a program without executing the code. Some of the analyses examine the code for infinite loops, dead locks, race conditions, and possibly other program flow issues.

[Buffy]

Consider the following conundrum that pops out of this discussion:

All algorithms must halt.
is a transcendental number that has no end.
Ergo, there are no algorithms for computing

I'll be the first to admit that we computer folk err on the side of the practical, but gosh sometimes these terms get bent out by the theorists (although who am *I* to be arguing with Kleene? ) to the point where they have no usefulness!

In the above, I have only seen the term "program" used as a possible candidate term for "an algorithm that does not terminate (but may produce lots of output)" but *that* term by every definition I can find refers specifically to something written in a "programming language" and thus does not satisfy the issue posed in the Original Post here of a general description that is not a program!

So, what'cha gonna call it folks? Or for purity's sake, is it just a "not in my backyard" issue?

I'm not saying that lots of smart people haven't decided this is a good thing, but I'm not sure why. Even Minsky's question is at odds with the fact that all his AI work basically produced "an answer" that was an approximation, and never "the answer" which was from a practical standpoint not practically computable.

I took all the computational theory classes, and I know what the issue is here, but I do argue that this one is out at the how-many-angels-dance-on-the-head-of-a-pin end of the spectrum...

I'm not dumb. I just have a command of thoroughly useless information,
Buffy

[stereologist]

i would agree that there are no algorithms for computing pi. There are algorithms for computing approximations to pi.

Not to get off on a tangent, but another term that is often misused is the term parse. People often say things like "parse the input for the phone number". Parse means to find the relationships between the parts. Scanning and searching are not parsing. Parsing human languages requires determining the relationship between words.

Getting back to the issue of algorithms, the definition I find useful is the one that allows for a better understanding of the work being done. A function that never returns is not useful to me.

just as parsing is often used in a less precise manner, so is algorithm. Fortunately, in most cases people are able to adjust their thinking to go from less well defined to more precise definitions when the context requires it.