Algorithms beyond programming

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

Originally Posted by maddog

Let's close this thread out.

If necessary.

Originally Posted by stereologist

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]

Originally Posted by Qfwfq

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.

Originally Posted by Qfwfq

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.

Originally Posted by Qfwfq

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]

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

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

Originally Posted by CraigD

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.

Originally Posted by CraigD

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

An effective true statement.

Originally Posted by CraigD

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

Originally Posted by CraigD

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.

Originally Posted by CraigD

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

[stereologist]

It was fairly clear to me that the problem was a "counting issue." Counting issues often lead to claims like Disraeli's who said, "Lies, damned lies, and statistics". For instance, the literature about the number of neurons in our brains has claimed 500 million and up to 500 billion. The broad range was due to counting issues.

In counting, step 1 is to decide on what to count, and then step 2 is deciding how to count.

Maddog points well to this issue by describing how counting steps does not reflect cost. One solution is to count each step in a weighted manner. Another solution is consider all solutions with a constant ratio to each other as being equal. By this I mean a solution that takes 3n steps is the same as a solution involving 10n steps. But a solution requiring log(n) steps is not equivalent.

[CraigD]

Originally Posted by stereologist

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

Or, in the immortal words of Richard O’Brien’s Planet, Schmanet, Janet:

Tha’ tranducer
Will seduce ‘ya
It’s something you’ll get used to

Language is mutable. Here, technically, it should have been “transmuter”, but that wouldn’t rhyme with “seduce ya”.

Even in computer science (which these lyrics are unambiguously not), one shouldn’t discount the importance of ring and rhyme.