Algorithms beyond programming

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

[imath]\pi[/imath] is a transcendental number that has no end.

Ergo, there are no algorithms for computing [imath]\pi[/imath]

 

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? :rolleyes: ) 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, :phones:

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.

[Buffy]

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

Right, that's my point: you end up doing a deus ex machina of throwing in a "oh, and stop after you get to n digits," which oddly enough from a *theoretical* standpoint is quite dissatisfying....

 

Not getting the irony yet?

 

...another term that is often misused is the term parse...

 

Ah but in that case we have a perfectly useful term, "lexical analysis" (or "lexing" for those of you who like to turn nouns into verbs), but we still have no terminology for this "not-an-algorithm-thingy" which we hate because it's beautiful....

 

Don't tell me that a true "algorithm for computing [imath]\pi[/imath]" would not be a thing of beauty....

 

One should either be a work of art, or wear a work of art, :phones:

Buffy

[stereologist]

Not getting the irony yet?

 

To be honest no. It is provable that there is no finite decimal expansion for pi or sqrt(2). So no algorithm can be written that computes these values.

 

What's wrong with process, procedure, computation, method, technique, method, routine, or operation?

[Boof-head]

Ah cha, as Ramunandran would have said, what if we don't expand or calculate pi?

 

What if we stay "circle-free", and forget about circularity?

[Pyrotex]

...It is provable that there is no finite decimal expansion for pi or sqrt(2).

This is quite true.

So no algorithm can be written that computes these values....

This is not quite true.

 

What you seem to be saying is that IF you cannot compute ALL the decimal expansion (which would be impossible), then any calculation at all is worthless; it's not the "true" value.

 

But scientists, engineers, programmers and others who live in the "Matheverse" don't do things that way. ALL values that are irrational (they cannot be expressed as a/b, where a and b are integers) are always expressed and used and discussed within a certain "error factor", which can be as close to zero as your heart desires. Typically, this error factor goes unspoken and assumed.

 

So, how accurate a value of pi do you want? If you're willing to wait long enough, the algorithms can compute a value as accurate as you like.

[Pyrotex]

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

In 30+ years of programming, the only context I've ever heard "parse" used was in compilers, interpreters, and certain computer games that needed to "read" text input from the player.

 

In all these contexts [pun intended] there was an algorithm that collected the ASCII (typically one letter at time) and determined if there was a sequence of rules and/or filters that would render the input into an unambiguous sequence of internal commands and data items. This was "parsing". If the parsing succeeding in producing a valid sequence of commands (and data), then they were executed. Eventually, one of those commands was "Stop".

 

Having written such a compiler once, long ago, my favorite way of "parsing" was by using a Finite State Machine (FSM) -- as opposed to today's more popular Object Oriented Machine (OOM).

 

Technically, the FSM wasn't an algorithm because it did not HAVE to end; if your input source code went on forever, so would the compiler -- until it overran memory and crashed, of course. But practically speaking, there was always a "Stop" because humans can only write (and attempt to compile) source code of finite length. So, I guess it WAS an algorithm.

[CraigD]

Ah cha, as Ramunandran would have said, what if we don't expand or calculate pi?

I suspect that most programmers with a math bent – who tend to spend a lot of time ignoring proven impossibility and just trying to code it anyway – have on at least one occasions seriously considered this question.

 

The real numbers, which consist of the rational and the irrational numbers, taunt one to find a simple scheme to represent digitally. For the other common numbers systems - the naturals, integers, rationals, and complex - numbers can be simply and compactly represented with pairs of numbers of the more elementary system –

 

[math]\mathbb{Z}=\mathbb{N}_1 -\mathbb{N}_2[/math],

 

[math]\mathbb{Q}=\mathbb{Z}_1 \div \mathbb{Z}_2[/math],

 

[math]\mathbb{C}=\mathbb{R}_1 + i \mathbb{R}_2[/math]

 

– but not so with the reals.

 

Exactly representing an irrational real number is no big challenge – just write it using recognized symbols, [math]\pi, e, \sqrt{2}[/math], etc. The big deal ensues when you start doing arithmetic with them.

 

For example, the simple series [math]\sum_{a=1}^{100} \sqrt{a}[/math]

 

which has an approximate rational value 671.46295, has the exact rational value:

 

[math]55 + 28\sqrt{2} + 15\sqrt{3} + 10\sqrt{5} + 10\sqrt{6} + 6\sqrt{7} + 6\sqrt{10} + 6\sqrt{11} + 3\sqrt{13} + 3\sqrt{14} + 3\sqrt{15} + 3\sqrt{17} + 3\sqrt{19} + 3\sqrt{21} + 3\sqrt{22} + [/math]

[math] 3\sqrt{23} + \sqrt{26} + \sqrt{29} + \sqrt{30} + \sqrt{31} + \sqrt{33} + \sqrt{34} + \sqrt{35} + \sqrt{37} + \sqrt{38} + \sqrt{39} + \sqrt{41} + \sqrt{42} + \sqrt{43} + \sqrt{46} + \sqrt{47} + \sqrt{51} + [/math]

[math] \sqrt{53} + \sqrt{55} + \sqrt{57} + \sqrt{58} + \sqrt{59} + \sqrt{61} + \sqrt{62} + \sqrt{65} + \sqrt{66} + \sqrt{67} + \sqrt{69} + \sqrt{70} + \sqrt{71} + \sqrt{73} + \sqrt{74} + \sqrt{77} + [/math]

[math] \sqrt{78} + \sqrt{79} + \sqrt{82} + \sqrt{83} + \sqrt{85} + \sqrt{86} + \sqrt{87} + \sqrt{89} + \sqrt{91} + \sqrt{93} + \sqrt{94} + \sqrt{95} + \sqrt{97}[/math]

 

As long as the number of operations in a calculation are small, on a human scale, it’s not impractical to represent irrational numbers exactly. If, however, a calculation has billions or more of operations, as they commonly do when performed using a computer, the representations can become impractically unwieldy – intractable, to use a good term – with even simple operations such as comparisons requiring nearly the equivalent of repeating the entire preceding calculation. For some fairly modest calculations, the amount of data storage required for systematic schemes to exact represent a rational number can exceed the amount possible given the limited amount of matter and energy in the visible universe!

 

Intuitively, one can visualize this problem being that real and complex numbers can simply contain too much information to be represented without making shrewd, very context-dependent decisions about the representation scheme to be used. Trying to formalize “shrewd context-dependent decisions” can be a nightmare task.

[stereologist]

the algorithms can compute a value as accurate as you like.

 

I agree Pyrotex. I posted that.

 

I jokingly use 3.1415926535 in my code. I think that is good enough to get the circumference of the earth down to a millimeter. For what I do that is overkill.

[stereologist]

The term parse as you use it Pyrotex is incorrect. To parse is to identify the relationship between the words or parts of a sentence. A parser accepts and rejects input.

 

The FSM is an automaton that is capable of parsing what are known as linear grammars. These are simple grammars. Push down automatons are required for the next level of grammar complexity called the context free grammars.

 

I'm not surprised that you have not heard parse used correctly. It rarely is.

 

Another example of the misuse of language is found in a company where they told people to "solution the problem." No one solved problems there. I always imagined the bosses stirring large vats of liquid trying to create solutions.

[Boof-head]

I remember writing a FSM (ATN net) for a parser for machine instructions for a handful of Intel and Motorola 8 and 16-bit chips for a bunch of engineers.

It was completely deterministic and simply read "tokens" from the input - an ASCII file of assembler tokens and directives - it always looked for a valid declarative. ATN grammars are context-free, and assembler instructions are (mostly) context-free as well, or the few exceptions, like the extensions in addressing modes introduced by Intel with the 16-bit chips were easy enough to handle.

 

Any algorithm can be recoded as a finite-state grammar, or transformed from a procedural 'algorithm' to a completely deterministic one. The deterministic state-transition paths should only be taken though, after you check the input is a valid set of tokens - there should be a lot of 'outs' in the graph, or default lambda-states that either 'fall-through' to the next state, or halt with a runtime error.

You could determine the inner workings of some algorithm, and decide to make it completely deterministic by setting a set of flags in registers, according to a scheme that corresponds to running an algorithm - the machine will produce the same output, although it will be fixed rather than variable so it will only handle one specific input state.

 

This might (or more likely it won't) correspond to what you want the algorithm to do, but in principle any 'program' can be recoded as a set of flags being tested and set, according to a predetermined pattern.

[Pyrotex]

The term parse as you use it Pyrotex is incorrect. To parse is to identify the relationship between the words or parts of a sentence. A parser accepts and rejects input. ....

Well... :hihi:

Isn't that what I said?

If a compiler determines which letters represent 'words' and determines the relationship between the words (this word is a command, this word is a modifier of the command, this word is a data item, this word is the object of the command, etc) -- and determines whether the entire string represents a valid sequence of words (accept!) or not (reject! print out error message!) -- isn't that 'parsing' by your own definition?

 

;)

[stereologist]

You're right. Typical FSM applications find the pieces of the input, but the relationships between those pieces. I misunderstood your post. Sorry about that.

[maddog]

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.

 

 

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

You have everything you need in the Wiki definition of Algorithm to answer your question.

If this is not enough to be satisfactory, look up Buffy's post #9 in this thread. Enuff' said.

 

maddog

[maddog]

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.

Pyrotex,

 

You may have a year or so on me. I agree with you on all you said with one point

which I have highlighted. No that I disagree with it. It is just that Buffy's example in

post #9 constitutes an algorithm by even your definition with the last statement in

essence

"got to step 1" or repeat.

This is in a sense a terminating case that just starts over.

 

maddog

[maddog]

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.

I was looking at that Wiki article. You also forgot to mention one other statement in the

same article, under the heading Termination.

 

Some writers restrict the definition of algorithm to procedures that eventually finish.

Which implies that some do not. This could construe that Algorithm includes both

interpretations: "to endless loop or not to endless loop, that is the question."

 

:smilingsun:

 

maddog