Algorithms beyond programming

[Buffy]

Originally Posted by stereologist

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?

Originally Posted by stereologist

...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 " would not be a thing of beauty....

One should either be a work of art, or wear a work of art,
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]

Originally Posted by stereologist

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

Originally Posted by stereologist

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

Originally Posted by Boof-head

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 –

,

,



– but not so with the reals.

Exactly representing an irrational real number is no big challenge – just write it using recognized symbols, , etc. The big deal ensues when you start doing arithmetic with them.

For example, the simple series

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






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]

Originally Posted by 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. ....

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