Algorithms beyond programming

[SidewalkCynic]

I recently learned that algorithm is a word being used without a definite defintion, as seems to be the case of a lot of terms I have been analyzing.

 

Anyway, I am wondering about this passage that algorithms and it seemingly exercised in fields beyond computer programming.

 

Most algorithms are intended to be implemented as computer programs. However, algorithms are also implemented by other means, such as in a biological neural network (for example, the human brain implementing arithmetic or an insect looking for food), in an electrical circuit, or in a mechanical device.

There is no reference, anybody able to direct me toward any?

[SidewalkCynic]

Okay - 52 views and no replies.

 

Do you agree, or disagree, with the description of algorithms provided in the excerpt?

[freeztar]

I think it's hard to discern the context of their usage of the word "algorithm" given the scant information provided.

 

If we assume the wiki definition of

 

an algorithm is a finite sequence of instructions, an explicit, step-by-step procedure for solving a problem

 

then I would have to say that the examples given in your quote are not a correct use of the word "algorithm". I don't think they should have used "implementation". To think of an electric circuit "implementing" an "algorithm" is silly to me. An electric circuit is not trying to solve a problem. It might solve a problem for the designer (the one who actually implements an algorithm using an electric circuit), but no problem is addressed inherently by the circuit itself.

[CraigD]

I recently learned that algorithm is a word being used without a definite defintion, as seems to be the case of a lot of terms I have been analyzing.

I think the meaning of “algorithm” is well defined and understood The definition give in your wikipedia link

In mathematics, computing, linguistics, and related subjects, an algorithm is a finite sequence of instructions, an explicit, step-by-step procedure for solving a problem, often used for calculation and data processing.

strikes me as a good, conventional, uncontroversial one.

Anyway, I am wondering about this passage that algorithms and it seemingly exercised in fields beyond computer programming.

The term “algorithm” is commonly used to describe any step-by-step list of instructions for doing something. So long as the entity reading and executing the instructions does so correctly, an algorithms is useful, so any entity from an electronic computer to a human short-order chef can use them. The term algorithm has been in use for more-or-less a thousand years, mostly among mathematicians – as the wikipedia article expains, like the term “algebra”, the word is a westernization of a Arabic word. When used in other disciplines, other words are used to describe the same concept – for example, in cooking, “recipe”.

 

The idea of an algorithm is very old, arguably nearly prehistoric. Some even argue that algorithms – recorded or orally handed-down list of instructions for doing useful task or meaningless rituals – are key to the emergence of humankind from its pre-human ancestory. An interesting fictional lecture on the subject can be had in the 1992 novel “Snow Crash” – something of a classic among computer-ish folk, and highly recommended by me – in which author Neal Stephenson equates instructions for such mundane tasks as baking bread with what early humans considered magic spells, called in the Novel “me”, a word borrowed from Sumerian mythology.

There is no reference, anybody able to direct me toward any?

Beyond the various discussions and links in the wikipedia article, I’m unsure what sort of reference to an algorithm-related idea you’re looking for, SidewalkCynic. I’ve a hunch you’re interested in the idea algorithm-like processes that are not algorithms. A concept that come to mind is the computational oracle, used in formal computing theory to allow for solving problems that provably cannot be computed.

 

Let us know if any of this is what you’re looking for, or if I’m misreading what you’re looking for.

Okay - 52 views and no replies.

Keep in mind that many viewers are unregistered guest users who can’t and don’t want to reply to threads, only read them, that hypography is a small, friendly, sometimes slow-paced forum, where sometimes days can pass while people think about how to reply to a post before doing so.

 

Also, this thread doesn’t belong in the Engineering and Applied Science forum, as it’s about a generally mathematical concept, not physically building things, so may have been overlooked by people interested in its subject. I’ve moved the thread to Computer Science – if it proves to fit some other forum better, I or another moderator will move it there later.

[SidewalkCynic]

Thanks,

 

Basically, what I am trying to determine is if I can classify engineering and computer programming as having the commonality of algorithms involved in the initiation of a task/project exercising either of the activities.

 

My problem being that I understand algorithms as being the abstract concept that the initiator of a project requests engineers or programmers to detail. For instance, a manager asks a programmer to write a program to "do (something);" I thought "do (something)" was the algorithm, and the programmer writes the steps that the processor can calculate.

 

So, I am probably looking for the term that describes the general classification of expectations of what a tool can be directed to do.

[CraigD]

Basically, what I am trying to determine is if I can classify engineering and computer programming as having the commonality of algorithms involved in the initiation of a task/project exercising either of the activities.

Taken far enough, nearly anything can be considered an algorithm, but in normal usage, we only refer to artificial lists of instructions as algorithm. So a computer program is an algorithm, while the chemical reaction of a virus encountering a particular cell is not, although the number, complexity, and consistency of execution of “coded” instructions for each may be similar.

My problem being that I understand algorithms as being the abstract concept that the initiator of a project requests engineers or programmers to detail.

I think you may be overcomplicating things.

 

An algorithm is simply a rule for doing something. For example

1. Set a counter named “A” equal to 1, one named “B” to zero
   
2. Compare B to a counter named “C”. If B is greater than or equal to C, state the value of C, followed by the words “factorial is” followed by the value of B, and stop.
   
3. Otherwise, increase B by 1, set A to A multiplied by B, and repeat from step #2
   

is an algorithm for stating the value of the factorial of an integer, C, ie: C! Note that it’s not a “bullet-proof" one, as it doesn’t check to assure that C is a non-negative integer.

 

There are some common and uncommon usages of the term “algorithm”, and some words meaning the same thing used more and less commonly in various contexts. A list of instructions performed by an electronic or mechanical computer, or by someone who knows how to act like one, is usually called a “program”. When spoken of abstractly, as something that could be performed by in principle any equivalent entity, it’s usually called an “algorithm”. When performed by a human being in a business setting, it might be called a “procedure” or “process”, and might be written in a strange way (the “how to make a sandwich” and “how to wash your hands” pictographs found in restaurants, for example)

So, I am probably looking for the term that describes the general classification of expectations of what a tool can be directed to do.

A common word for this, if I understand your meaning, is “specifications”. There’re many specialized business versions on the term, but “specification”, often with various modifiers (eg: “detailed specifications”, “business specification”, etc.) is, I think, the most widely used and recognized. Occasionally, one sees the word “specifications” replaced with another word – “solution” is a common one – but in my experience such substitutions are more trade art than meaningful language differences.

 

While specification and algorithms are clearly related, they’re very different and distinct things. In short, a specification describes is what an algorithm should do, an algorithm, how it is actually done.

[SidewalkCynic]

Well, we're knocking them down by elimination. Let me think about my dilemma a little bit, and see if maybe I need to redirect my inquiry.

[stereologist]

There is an important issue here that is missing.

 

Algorithms eventually stop. The following is not an algorithm:

 

1. Wait for person to walk by

2. Smile at person

3. Go back to step 1

 

This sequence does not end.

 

1. Wait for person to walk by

2. Smile at person

3. Go back to step 1 if not friend

4. Talk to friend

 

This sequence can stop.

[Buffy]

There is an important issue here that is missing.

 

Algorithms eventually stop.

 

Well for practical purposes, probably, but I'm not sure how you justify this statement.

 

Many programs are in fact written this way:

 

1. Turn on red light.
   
2. Wait 30 seconds.
   
3. Turn on yellow light.
   
4. Wait 4 seconds.
   
5. Turn on green light.
   
6. Wait 30 seconds.
   
7. Goto 1
   

 

Got up, got out of bed, dragged a comb across my head, made my way down stairs and drank a cup, and looking up I noticed I was late, :thumbs_up

Buffy

[CraigD]

There is an important issue here that is missing.

 

Algorithms eventually stop. ...

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.

 

In wider usage, however, algorithm seems to be used more generally to include both programs that can end, and ones that can’t. I’ve a hunch this more general meaning gained popularity when people began formally defining “algorithm” as “that which can be represented by the state table of a Turing machine”. When the term first began showing up with any frequency ca. the 12th century, I suspect the most common definition was an informal one like “way to calculate something”, and would have considered endless programs to be either very bad algorithms, or not deserving of the name at all.

 

Personally, I like to use the term “program” in place of the most formal description of an algorithm, and “algorithm” to describe a higher level, “essential” description. I say things like “this program implements that algorithm”, implying a many-one relationship where an algorithm can be implemented by many programs.

 

This issue of a single word, even a fairly technical one, having multiple, context-dependent meanings, is I think a lot of what inspired Korzybski to propose using subscripts on every word in natural language writing, with the wild idea that if everybody – or at least everybody important became enculturated to doing this and thinking in the manner it engendered, social problems like war and poverty would disappear. I’m don’t know if Korzybski’s hunch is right or wrong, but I’m pretty sure that such a practice would dramatically change communication on science boards like hypography! :thumbs_up

[Buffy]

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

 

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!" :thumbs_up

 

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]

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