Re: pseudo code v/s algorithm

Neil <NeilKurzm@xxxxxxxxxxxxxxxx> writes:

Tagore wrote:
On Dec 26, 4:02 am, Moi <r...@xxxxxxxxxxxxxxxxxxx> wrote:
On Thu, 25 Dec 2008 14:43:31 -0800, Tagore wrote:
what are differences between pseudocode and algorithm?
Pseudocode is like language
Algorithm is like a thought.

/tagore

HTH,
AvK

Is it true that algorithm should have finite complexity whereas pseudo
code can have infinte compexity?
???????
How do you write code for an problem of infinite complexity?

Tagore is confused. What he refers to is that an algorithm must
terminate in a finite number of steps to be called an algorithm,
stricto-sensu. On the other hand, computers have no problem in
executing "infinite" or rather, "unbound" processes. It's only an
illusion, since around all loop, there's always an unexpressed
terminating condition: UNTIL (OR END-OF-UNIVERSE NEXT-POWER-FAILURE),
which gives a limit of about 15e9 years in the best case.

Of course, this has nothing to do with what is called algorithmic
complexity.



An algorithm is the plan of action how you are going to do it.

pseudo code is the next step a list of steps more in english ( or
insert your language here) than code. More like a recipe.

There is absolutely no difference between algorithm and code, as long as
code is considered in its more abstract, mathematical level.

Pseudo-code is just an informal way to express such a mathematical
being.


That is, if your code is the description of a valid Turing Machine, or
lambda-calculus function, then it is equivalent to the algorithm. Note
that very little is needed from your programming language for this
condition to be realized. Obviously, if your programming language is
implemented in a finite memory Von Neumann computer, then it can be
implemented in a Turing Machine or lambda-calculus function, and if your
language is worth its bits, you will be able to trivially implement a
Turing Machine or lambda-calculus in it, modulo the infinite memory
requirement.

Our computers and programming languages only approximate these
mathematical beings. For example, there is no computer that is
equivalent to a Universal Turing Machine, because there is no computer
with infinite memory. (But a given Turing Machine can be implemented in
a specific computer with enough memory, because one condition for an
algorithm is to be finite, and to terminate, therefore the explored
state space is finite, and may in practice be held in the amount of
memory available to our computers.


For example, C is a poorer approximation than Comon Lisp, because in C,
there sizeof(int) is finite, and pointers and array indexes must be
enumerable by integers, therefore the memory available to a C program,
even if it would run on a computer with infinite memory, would be very
finite. On the contrary, in Common Lisp, there's no limit imposed on
the size of integers, and there's no limit imposed on the number of
different objects that can be referenced (there's no equivalence between
references and integers in CL), so if there existed a computer with
infinite memory, there could exist an implementation of Common Lisp
equivalent to lambda-calculus, with infinite memory (but you will never
be able to use C to implement an infinite memory lambda calculus or
Turing Machine). We can say that Common Lisp is a better algorithmic
language than C.


Another question, is how well formally the programming language
semantics are defined. Again, to take only these two examples, the
semantics of C appear less well defined than the semantics of Common
Lisp or Scheme (even if all have quite a number of holes).


However, my thesis here is that it is in general ridiculous to try to
specify an algorithm with an informal language pseudo-code, because of
the lack of formalism and precision. Pseudo-code is necessarily more
ambiguous than any formally specified programming language.

It would be better to just use mathematics to formalize algorithms, that
is, Turing Machines or lambda-calculus. You will soon notice that
lambda-calculus is more expressive than Turing Machines, and that using
a subset of lisp (or any other functional programming language) as an
extension to lambda calculus is even more expressive, and sufficiently
formal to be usable to describe precisely algorithms, with the level of
abstraction needed.

I see no reason to use a more informal and ambiguous pseudo-language.
If you give pseudo-code, then you need a mathematician to produce a
formal algorithm from it, and the risks that your pseudocode is
inconsistent and does not define an algorithm is higher than with a
formal, mathematical or programming, language.



For example, you could define an algorithm to compute the gcd as the
following mathematical expression:

Let's consider the two associated series:

u(0) = u
v(0) = v

u(i) = | u(i-1) = v(i-1) => u(i-1)
| u(i-1) < v(i-1) => v(i-1) - u(i-1)
| u(i-1) > v(i-1) => u(i-1) - v(i-1)

v(i) = | u(i-1) = v(i-1) => v(i-1)
| u(i-1) < v(i-1) => u(i-1)
| u(i-1) > v(i-1) => v(i-1)


Let r = MU(k, u(k)=v(k))

The function gcd(u,v) is computed as: gcd(u,v) = u(r)


We could as precisely and formally define gcd(u,v) as:

(defun gcd (u v)
(loop
with ui = u and vi = v
while (/= ui vi)
do (if (< ui vi)
(psetf ui (- vi ui)
vi ui)
(psetf ui (- ui vi)
vi vi))
finally (return ui)))

or:

(defun gcd (u v)
(cond ((= u v) u)
((< u v) (gcd (- v u) u))
(t (gcd (- u v) v))))

because the semantics of these Common Lisp functions, when ignoring the
memory limitations, is exactly the mathematical series above, with the
same result.

Note that in both cases to understand the language, you have to know it.
You have to understand the mathematical language, and the formalism used
eg. if you don't know the mu quantifier, you have to learn it,
( mu(k, P(k)) =def= k such as P(k) and forall(i), P(i) ==> k<=i ).
By the same token, if you don't know the Common Lisp language, you will
have to learn it, to learn its syntax and its semantics. Thankfully,
it's not too badly defined, at least there's a definition.
It would be even better to use a more formally defined language.

But using a non defined, informal pseudo code would be worse than using C.


--
__Pascal Bourguignon__
.

Relevant Pages

  • Re: pseudo code v/s algorithm
    ... insert your language here) than code. ... There is absolutely no difference between algorithm and code, ... If I have an implementation or pseudo-code it cannot be ... Turing Machine or lambda-calculus in it, modulo the infinite memory ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... insert your language here) than code. ... There is absolutely no difference between algorithm and code, ... If I have an implementation or pseudo-code it cannot be ... just have a look at the sources of some Common Lisp ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... the lack of formalism and precision. ... Pseudo-code is necessarily more ... ambiguous than any formally specified programming language. ... formal algorithm from it, and the risks that your pseudocode is ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... Pseudo-code is necessarily more ... ambiguous than any formally specified programming language. ... Lisp is a forty-year old language that has hardly ever been used to ... pseudo-code is as good a starting point as the algorithm itself. ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... infinite memory, there could exist an implementation of Common Lisp ... Pseudo-code is necessarily more ... ambiguous than any formally specified programming language. ... formal algorithm from it, and the risks that your pseudocode is ...
    (comp.programming)
Loading