Month: December 2004

Ramin replied me back and wrote:

Every program could be considered as an automata which gets a string input and outputs a string output of codes. I think the robustness of algorithms can be interpreted as “redundancy” in this messaging framework. Thus, I recommend this, as an alternative strategy, to bring robustness to computer algorithms from the communications view point.

The idea of translating computer algorithms to dynamical systems is fascinating but first, we should reconsider the “dynamic” properties of our algorithms.

And I wrote him:

You mentioned a very good and interesting point. I wonder if there is a relation between dyamical properties of the system and information content of the message. I guess that the fractal dimension of a trajectory of the system’s output has a relation with output signal’s entropy. Consider this: a stable system converges to a single point in the state space (or output space) (fractal dimension = 0) and the entropy of the output signal converges to the zero as knowing the system is stable is equivalent to knowing what its future would be. A limit cycle leads to a finite fractal dimension (e.g. in 2D state space, it is between 1 and 2), and the entropy of it is finite depending on the length of its descriptor string, and etc.
Properties like robustness may be considered as cross-entropy between source (disturbances) to destination (output signal). hmmm … it is interesting in my mind. Maybe we are reinventing cybernetics!

You are writing a very advanced algorithm and it looks that you have noticed to every aspects of implementations, but your program does not work at all! You may become disappointed of the performance of your advanced algorithm, or you might find a very small bug in a line of your code: you had typed x++ instead of x–. The world would be a better place to live if your programs were not that sensitive to these small typos.
Not very seriously, I have thought about robust algorithm, i.e. an algorithm that is insensitive to its changes. Is it possible?! To answer this question, I must know what is an algorithm and what can be considered as an algorithm. I think (however, I am not sure), an algorithm can be considered as a thing that can be implemented by a Turing machine and vice versa. This remains the big question that is about the limits of a Turing machine. I know that it is a universal computer, but I am not sure what is the exact meaning of it: does it mean that every mathematical calculation (e.g. solving a PDE) is a “computation” task and can be implemented by a Turing machine. In addition, I want to know if there exists a problem that cannot be implemented by an algorithm (you know, I have not had any course on theory of computation or something similar).
Let’s assume that an algorithm is a sufficient framework for almost everything, including solution of a dynamical system. If the converse is true, a dynamical system is capable to present an algorithm and is its equivalent, is it possible to use the same robust analyses of the dynamical system to an algorithmic one? For instance, we may analyze a specific algorithm to see whether it is robust to some small changes or it would become unstable? If x(n) is the state of an algorithm at moment “n” and x(n+1) = F(x(n))+G(x(n),u(n)) is the next state, we may present a perturbed version of it as x(n+1)=F(x(n)) + deltaF((x(n)) + G(x(n),u(n)) + deltaG(x(n),u(n)) + du(n). These deltaF(.) and … can be considered as perturbations and the stability of the new system is dependent on their properties. For instance, for the following algorithm:

Get inputs x(1) … x(k)
Sum = 0;
for(i=1;i