Registered: Jun 2004
Posts: 1

I dont see a difference between the difinition of a rule and an algorithm. Can you illuminate some light on the difference between these things ?

Algorithm == rule in that it is a precise instruction ?

so instead of rule 30 we can say algorithm 30.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

In the simple case of the 256 1D CAs, a single algorithm can easily serve all, treating the rule number as a data item in additional to the string of binary digits which represent the current state of the particular CA.

Such an algorithm, especially when implemented in a general purpose computing environment, embodies definitional aspects of what it actually means to be a CA: determining the next state of a cell from the previous states of a local neighbourhood of cells, in the same simple case from three linearly adjacent cells; and determining the new state of all cells from the old state in a single pass (generation), most obviously implementable via a loop.

In the case of the fraction of rules exhibiting "simple" behaviour (Class 1 and Class 2) it is possible to use a more efficient algorithm for each specific rule, but one of the key points of NKS is that there are no such shortcuts for Class 3 and Class 4. (That is only strictly true in general for Class 4, there being potential local efficiencies with respect to the large areas of uniform pattern which often emerge in Class 4.)

It is also at least implicit in Wolfram's Principle of Computational Equivalence that any given algorithm can be implemented in many fundamentally different rule architectures of which CAs are just one.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 46

A good question. Here's a way to look at things:

A rule is just a definite and unambigous procedure for turning some data into new data. This does not in general include any mention of when to "stop" applying the rule (although it might for some rules).

For instance a cellular automaton turns a line of cells into another and that process may continue forever in a sequence of steps.

An algorithm is a rule put into action to solve some set of very similar problems. There is a clear definition of the set of possible input problems, and a clear definition of the set of possible outputs. The crucial thing is that given any valid input problem, the rule must always halt in some finite time and produce a correct solution to the problem.

Thus an algorithm comes with a guarantee that it always solves the problem in a finite time. Different inputs may take different times to compute and there may be inputs that take longer and longer to compute, but they always stop sometime.

In the real world algorithms may contain bugs and not be correct. Also they may in practice take too long or use up too much memory to be used to solve the problem.

Occasionally computer scientists bend this strict definition of the word algorithm and use it to describe programs that may not always be successful in solving a problem. Perhaps a computer vision "algorithm" may give up trying to decide whether a video picture is a hat or an upturned bowl.

Most of the things in NKS are just studied as rules (in the general sense), rather than algorithms solving a problem. For instance Turing machines just carry on computing the next line of cells forever, whereas the traditional treatment of Turing machines includes an explicit "halting" state and talk of additional input and outputs.

Nevertheless potentially all the rules in NKS could be turned into algorithms that solve some problem just by being explicit about the inputs, outputs and when to stop applying the rule (this must be guaranteed in some way).

Examples are:
http://www.wolframscience.com/nksonline/page-638
http://www.wolframscience.com/nksonline/page-639

If someone just gives you a rule, it may or may not solve any useful algorithmic problem - although it solves some problem (perhaps boring or even unintelligable). To constuct an algorithm to solve a particular problem that you have in mind may take searching a huge number of rules.

If NKS is applied to solve a particular problem with a rule that uses complex behavior of some sort, then its seems likely that at least for some cases the process will not halt and thus will not qualify as a traditional algorithm. Of course the best known "rule" for solving problems (the human brain) doesn't always guarantee an answer, and that may or may not be a problem!

The processes at work in traditional engineered computer algorithms tend to have a regular pattern of behaviour and this is often part of what makes it possible to guarantee that they always return a solution and thus are strictly algorithms.

As for rule 30. Well rule 30 run for any definite number of steps (say 100) solves some abstract problem (involving strings of 0s and 1s as inputs and outputs say). It might also provide other algorithms in other ways - say by saying we stop when a particular pattern is reached. Also, assuming it is universal it could in theory be programmed to solve any algorithm.
Useful applications of rule 30 to cryptography and random number generation are already known.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 38

I think Richard's explanation is good and fairly clear, so Im going to try to reintroduce some confusion.

In general usage, 'algorithm' is typically means some sort of proceedure to compute a particular kind of thing. For instance, the earliest algorithm is the Euclidean algorithm for computing the greatest common divisor of 2 numbers (http://mathworld.wolfram.com/EuclideanAlgorithm.html)

Despite this, i think its true one can have algorithms without a predefined purpose.

So how to understand the difference between an algorithm and a rule?

An algorithm is a complete proceedure for computing something.

In NKS usage, a "rule" is typically an input to an algorithm that actually runs the system.

Rule 30 on its own doesnt really do anything. Its just a description of a bunch of parameters, which then are inputted into the cellular automaton function, which itself is an algorithm.

This is why it doesnt make much sense to say "algorithm 30". Without knowing what kind of algorithm you are plugging that number in, it has no real meaning.

In the book NKS, the term "rule" is often used to describe elements of the Elementary Cellular Automata class.

"Code" is used to describe more general kinds of cellular automata.

"Machine" is used to describe turing machines and register machines

Elsewhere, systems are described using a symbolic expression rather than a number.

Personally, I think of something like rule 30 as being not an algorithm or a set of parameters, but more like a programming language.

The most obvious case this is true is rule 110, which is known to be universal. One can literally write programs in rule 110 by setting up the initial conditions in a certain way.

Would one describe C as an algorithm? I dont think so. However, one could describe the system that executes the C code as an algorithm. This is how I see the relationship between a rule and the function that executes the rule.

I hope this helps...

__________________
Everything is an expression.

Report this post to a moderator | IP: Logged