Algorithms beyond programming

[maddog]

And the definitions you provide for algorithm all involve the termination requirement.

Again well done.

Again Not the answer from you I expected... :naughty:

 

Borrowed from my post#43 above ...

Algorithm:

 

From Dictionary.com:

al⋅go⋅rithm

 

  /ˈælgəˌrɪðəm/ Show Spelled Pronunciation [al-guh-rith-uhm] Show IPA –noun a set of rules for solving a problem in a finite number of steps, as for finding the greatest common divisor.

 

...

From Reference.com

algorithm

algorithm or algorism [for Al-Khowarizmi], a clearly defined procedure for obtaining the solution to a general type of problem, often numerical. Much of ordinary arithmetic as traditionally taught consists of algorithms involving the fundamental operations of addition, subtraction, multiplication, and division. An example of an algorithm is the common procedure for division, e.g., the division of 1,347 by 8, in which the remainders of partial divisions are carried to the next digit or digits; in this case the remainder of 5 in the division of 13 by 8 is placed in front of the 4, and 8 is then divided into 54. The software that instructs modern computers embodies algorithms, often of great sophistication.

The Columbia Electronic Encyclopedia Copyright © 2004.

Licensed from Columbia University Press ...

 

algorithm

Procedure that produces the answer to a question or the solution to a problem in a finite number of steps. An algorithm that produces a yes or no answer is called a decision procedure; one that leads to a solution is a computation procedure. A mathematical formula and the instructions in a computer program are examples of algorithms. Euclid's Elements (circa 300 BC) contained an algorithm for finding the greatest common divisor of two integers. Manipulation of lists (searching for, inserting, and removing items) can be done efficiently by using algorithms.

Learn more about algorithm with a free trial on Britannica.com.

...

I made "finite number of steps" VERY BIG. "Finite number of steps" does not Necessarily mean "terminate". You can repeat a step.

 

Algorithmic steps (example)

 

Iteration (with termination)

 

1. Z^2 + C --> Z

2. Mod(Z) < 2 ?

3. if true then repeat step 1.

4. Terminate.

 

The above may or may not terminate depending upon data.

 

Iteration (without termination)

1. i = i + 1

2. Repeat step 1.

 

No termination.

 

Sorry.... :)

 

maddog

[stereologist]

Hightlighting just the comments in Green I think get at what I am saying which from I can

tell is Not what you are saying.

 

As Qfwfq has said above Compilers & Interpreters have a Parser nor are ones!

 

In this example of some text --> "192.168.172.13" is a dotted decimal IP address.

I would parse it (removing the ".") to arrive at the number 25251853. This is parsing. I

will not accept it to be not. Period.

 

The double negatives here are a bit confusing, but here goes. The first green comment refers to grammatical structure. That is the relationships between the parts of the input.

 

to determine their grammatical structure with respect to a given (more or less) formal grammar.

 

The parse tree often does not exist in a modern parser. Typically parsers have nothing more than the portion of the tree from root to the current leaf at any given point in time.

 

A parser is one of the components in an interpreter or compiler, which checks for correct syntax and builds a data structure

 

The data structure built is not the same as the output of a transducer.

 

The most common use of a parser is as a component of a compiler or interpreter.

Probably true.

 

In this example of some text --> "192.168.172.13" is a dotted decimal IP address.

I would parse it (removing the ".") to arrive at the number 25251853. This is parsing. I

will not accept it to be not. Period

That's fine. You are welcome to misuse any words you want. It's not parsing and does not meet the definitions you posted.

[stereologist]

I made "finite number of steps" VERY BIG. "Finite number of steps" does not Necessarily mean "terminate". You can repeat a step.

 

Algorithmic steps (example)

 

Iteration (with termination)

 

1. Z^2 + C --> Z

2. Mod(Z) < 2 ?

3. if true then repeat step 1.

4. Terminate.

 

The above may or may not terminate depending upon data.

 

Iteration (without termination)

 

1. i = i + 1

2. Repeat step 1.

 

No termination.

 

Sorry....

 

Very funny shouting. The finite number of steps is not that the algorithms composed of less than an infinite number of executable statements. It is how many steps are executed.

 

If it does not terminate then an infinite number of steps are performed and its not an algorithm.

Sorry.

[maddog]

The data structure built is not the same as the output of a transducer.

A "transducer" has nothing to do with what I am talking about.

That's fine. You are welcome to misuse any words you want. It's not parsing and does not meet the definitions you posted.

:umno:It is NOT a misuse. You are welcome to your Opinion. ;)

maddog

[maddog]

If it does not terminate then an infinite number of steps are performed and its not an algorithm.

Sorry.

Again... Your Opinion. ;)

 

maddog

[stereologist]

A "transducer" has nothing to do with what I am talking about.

It does. I refer you to "The theory of Parsing, Translation, and Compiling" Aho and Ullman Copyright 1973

 

Opinion? No. The definitions you posted, not me, clearly define what parsing and an algorithm are.

[Qfwfq]

So, each has said his opinion and neither seems to be adding much. Not much point in continuing this way, not worth it...

 

Call it a day? ;)

[maddog]

Opinion? No. The definitions you posted, not me, clearly define what parsing and an algorithm are.

How is it that both of us read the same statement and see it differently ? I am reading it in English. What are interpreting in "Transducerish" ??? :doh:

 

Qfwfq,

 

I am beginning to agree with you. Nothing more can be said. Let's close this thread out.

As the curtain falls.... :( :shrug: :shrug: :shrug: :shrug: :shrug:

 

maddog

[stereologist]

It's possible that you were unaware of the meaning of "grammatical structure".

 

I am curious. What are you counting as finite steps? Are you counting steps taken or steps written down?

[stereologist]

To Qfwfq, I am confused as to how someone can pose that an algorithm takes finite steps and yet claims that the algorithm never terminates. Resolving this confusion would be useful to me.

[Qfwfq]

Let's close this thread out.

If necessary. :confused:

 

Resolving this confusion would be useful to me.

Are you asking me to resolve it?

[stereologist]

Qfwfq I know you can't resolve the counting issue. I'd like to find out from maddog what he is counting. Somehow he appears to be counting indefinitely and yet remaining finite.

[Qfwfq]

OK, I got the wrong impression, but it's more helpful to settle differences than to get stuck on terms.

 

This goes for your use of transducer; perhaps you find it in the literature but still, try to make it less important if others haven't. A rose by any other name would smell as sweet, so call it a tomato. Also I get the idea that maddog counts the number of steps used to define the procedure rather than executions of them (as typically meant in defining the term algorithm); try to clear this up more effectively, so as to avoid abrasivity.

[CraigD]

IMHO, the legitimate function of language, technical or non-technical, formal or informal, is to be useful, and an essential requirement for a term in it to be useful, is for those using it to agree on its meaning.

 

Thus, setting aside historic antecedents, I propose that we agree to call an explicit ordered list of instructions a program.

 

Let’s define a sub-collection of the collection of all programs, algorithms, as programs that usually end, and produce useful data.

 

All algorithms are thus programs, but not all programs, algorithms.

 

Let’s use instruction to refer for a single one of the instructions of which a program consists, the actual execution of a single instruction a step.

 

Thus programs must have a finite number of instructions, but their execution can consist, in principle, of an infinite number of steps – in which case, they don’t usually end, and aren’t algorithms.

 

These proposals leave significant gaps in classifying all computation (including failing to define computation, and the vague terms usually and useful), but does anyone disagree on them as a convention, to allow useful communication?

[maddog]

OK, I got the wrong impression, but it's more helpful to settle differences than to get stuck on terms.

With this I fully concur. I would like to resolve if possible.

This goes for your use of transducer; perhaps you find it in the literature but still, try to make it less important if others haven't. A rose by any other name would smell as sweet, so call it a tomato.

Most of my problem was this word <as I have Never used it this context in this way>. When

I hear/see the word "transducer", I am thinking completely of some measuring device for

either Temperature, or Pressure. I am assuming that CS types borrowed this word into

their venue with reinterpreting data in this way. I have been wanting to since the other

day to visit a University Library and look up the word in a "Dated" (say 1950s) Oxford

Dictionary. I doubt that I would find the CS connotation as it was likely created afterwards.

 

Also I get the idea that maddog counts the number of steps used to define the procedure rather than executions of them (as typically meant in defining the term algorithm); try to clear this up more effectively, so as to avoid abrasivity.

Again Qfwfq is dead on the money. I was counting the number of steps in algorithm

(being finite). Not how many times a step is executed. This is my understanding on the

definition of Algorithm.

 

BTW, I was able to get a copy of the book Stereologist mentioned from ACM in PDF form.

This will give me time to read it.

 

Also, I have been parsing data, and other various input streams for close to 30 years.

If I do have the definition wrong (???), it has not seemed to lesson my ability to do so.

Maybe, I will have to wait until the dictionaries of the world change again for me to get it

wright... :)

 

maddog

[maddog]

IMHO, the legitimate function of language, technical or non-technical, formal or informal, is to be useful, and an essential requirement for a term in it to be useful, is for those using it to agree on its meaning.

 

Thus, setting aside historic antecedents, I propose that we agree to call an explicit ordered list of instructions a program.

In the spirit of consensus building, I agree with this definition, provided we can all agree on what "instructions" are.

Let’s define a sub-collection of the collection of all programs, algorithms, as programs that usually end, and produce useful data.

I agree here also.

All algorithms are thus programs, but not all programs, algorithms.

An effective true statement.

 

Let’s use instruction to refer for a single one of the instructions of which a program consists, the actual execution of a single instruction a step.

I go a little fuzzy here in that "how many steps to make an instruction ?"

 

Thus programs must have a finite number of instructions, but their execution can consist, in principle, of an infinite number of steps – in which case, they don’t usually end, and aren’t algorithms.

I am not sure how to make this work with the above satement (implied) that so many

steps make an instruction... ? Does this work as well for High Level Languages as Low ?

 

In C/C++ I can make/write the following instructions (equivalent)

 

i = i + 3;

i += 3;

i++; i++; i++;

 

Same basic instruction done three different ways.

 

In Assembly (MC 68K):

 

i dc.l 0

 

# first method

move.l i(a2),d2

addq.l #3,d2

move.l d2,i(a2)

 

# second method

addi.l #3,i(a2)

 

# third method

i = register d2

 

addq.l #1,d2

addq.l #1,d2

addq.l #1,d2

 

Both C statements above and the assembly do the same thing. The assembly code take

more "steps" to accomplish a C statement ("instruction"). I would caution in the use of

the word "step" as part of an instruction and the "step"s that could be infinite in a program

not terminating.

 

Most often when a program doesn't terminate, a loop is involved. This may have been

planned (rarely) or more often, a "bug" has resulted. Because of loops a single instruction (or step)

may execute multiple times.

These proposals leave significant gaps in classifying all computation (including failing to define computation, and the vague terms usually and useful), but does anyone disagree on them as a convention, to allow useful communication?

I would agree here to postpone tackling "to Compute" or "Utility" for awhile.

 

Just my thoughts for the day. :)

 

maddog

[stereologist]

Most of my problem was this word <as I have Never used it this context in this way>. When

I hear/see the word "transducer", I am thinking completely of some measuring device for

either Temperature, or Pressure. I am assuming that CS types borrowed this word into

their venue with reinterpreting data in this way. I have been wanting to since the other

day to visit a University Library and look up the word in a "Dated" (say 1950s) Oxford

Dictionary. I doubt that I would find the CS connotation as it was likely created afterwards.

 

A transducer is a simple device that has an input and converts it to a different form in the output. So a wind mill is a transducer converting the wind into a water pump. A better example is an electric motor converting electricity into motion.

 

In CS a transducer converts an input into a different form. The mathematical representation is a "recognizer which emits an output string during each move made. The finite transducer is obtained by taking a finite automaton and permitting the machine to emit a string of output symbols on each move."

This quote is from p223 of Aho and Ullman.

 

Think of a finite state machine. The FSM goes through a series of states, but does not make an output. The end result is that the FSM either reaches a final state or it does not. The decision is whether or not a final state is reached. Now if the transitions are augmented with an output, then the FSM becomes an FST, finite state transducer.

 

Example:

 

state A: on 0 goto state A and output 1

state A: on 1 goto state A and output 0

 

This is a finite state transducer that accepts inputs composed of 0s and 1s, and outputs the complement of the input.

 

Here is a definition of transducer I found online:

A substance or device, such as a piezoelectric crystal, microphone, or photoelectric cell, that converts input energy of one form into output energy of another.

 

From an article about Wolfram at:

Stephen Wolfram, A New Kind of Science

A physicist would call a CA a fully-discretized classical field theory; a computer scientist would say each cell is a finite-state transducer, and the whole system a parallel, distributed model of computation.

 

From Wolfram's website we see the following:

transducers

TuringMachine (Mathematica Symbol)

 

The Turing machine is listed as a transducer.

 

In a paper:

http://www.santafe.edu/research/publications/workingpapers/04-09-027.pdf

The second method is to algorithmically construct a transducer that approximates the first algorithm. In contrast to the stack-based algorithm, however, the transducer requires only a finite amount of memory, runs in linear time, and gives immediate output for each letter read; it is, moreover, the best possible finite-state approximation with these three features.

 

The word transducer has a meaning which is not archaic. It is a term describing some of the mathematical machines that can be used to describe computations.