[Randomness, searching, and patterns] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

Randomness, searching, and patterns
(Click here to view the original thread with full colors/images)

Posted by: Ed Meier

If Class 3 behavior can be seen from a random starting position, doesn't that just mean that the particular random selection is a pattern from some future (unseen) generation for that pattern?

Is there such thing as randomness anymore?

I worked in an Applied Research department on Information Retrieval, trying to return written documents based on a string of query words. The english language is full of "noise" and it is very difficult, NP hard, to achieve both high recall, finding all the relevant documents from a corpus, and high precision, ignoring documents that aren't relevant. What with the synonymy and polysemy of words, it is very difficult to determine meaning. We tried a number of AI techniques and mathematical analysis, like wavelets. Is there any research being done on this?

Also, I have an idea on how to determine the contributing rules given a sequence of rows from a random pattern. What kind of research is being done on this?

Posted by: Ed Meier

Upon further reflection, I do not have a way to generate CA rules given a pattern. My train of thought was to use a genetic algorithm to search for the right rule, given an random string of 1's and 0's. However, since there are only a handful of rules that generate randomness, it would be a short search.

The real problem is given a random sequence of 1's and 0's, how do we determine which generation/iteration this string came from and where? Can we run CA rules backwards? I don't see why not.

But given a short string how could you determine the outside influences? I'm thinking here of collisions when one sub-pattern collides with another. Tracing backwards, if there was a collision somewhere earlier, the direction we are going, before our particular random sub-string, we would never come to know the original rule. Sigh.

Are there rules like those defined in mathematics for CA properties like, transitive, symmetric, reflexive, and the like? Clearly based on the thought above CA is not symmetric, you can't run it forward and backward and get the same result.

Posted by: Tony Smith

If Class 3 behavior can be seen from a random starting position, doesn't that just mean that the particular random selection is a pattern from some future (unseen) generation for that pattern?

To understand why this is not so, you need to get your head around the subtle but important difference between countable and uncountable infinities, a distinction which continues to elude even many eminent mathematical scientists.

Put as simply as I can, if we just confine our thinking to a two colour CA, the number of possible states grows as 2^n, where n is the number of cells, whereas the number of realised states from a given starting configuration grows as t, the number of generations. As both n and t increase towards large numbers, 2^n grows incomparably faster than t, so your short answer is clearly "No!"

For even the cases with n<=130 that I discuss in my Irreversibility precedes reversibility thread, only a fraction of states have a singular predecessor, many having none and many others having two or more, most likely to first approximation a Poisson distribution with mean 1. Once you try to find singular grandfathers and beyond, that fraction quickly vanishes.

As noted in NKS (p.435-441) there are certainly some reversible CAs but these are a tiny fraction of all possible CAs.

Is there such thing as randomness anymore?

This depends entirely on what you mean by "randomness". The NKS index has more than two full columns of entries relating to "random" and "randomness".

In a purely formal sense "irreducible" is easier to deal with and for practical purposes effectively synonymous, yet our common sense understanding of "randomness" remains valuable.

My take is that randomness begets resilience. It would not surprise me if long after I am gone, the world comes to realise that most measures which we now think of as being conserved because of some inherent indestructible atomicity might be better thought of as being conserved through their natural invariance under Class 3 transformations. Asimov's concept of "psychohistory" in his Foundation series was an early exploration of this possibility.

I worked in an Applied Research department on Information Retrieval, trying to return written documents based on a string of query words. The english language is full of "noise" and it is very difficult, NP hard, to achieve both high recall, finding all the relevant documents from a corpus, and high precision, ignoring documents that aren't relevant. What with the synonymy and polysemy of words, it is very difficult to determine meaning. We tried a number of AI techniques and mathematical analysis, like wavelets. Is there any research being done on this?

I'm trying a crude statistical approach to word frequency and word sequence frequency in pursuit of a comparable but different problem. While I'm not convinced that natural language is any nosier than is necessary to provide just enough redundancy for a realistic level of fault tolerance, I've long conceded that even that level of noise is a barrier to analytic approaches.

Also, I have an idea on how to determine the contributing rules given a sequence of rows from a random pattern. What kind of research is being done on this?

Upon further reflection, I do not have a way to generate CA rules given a pattern. My train of thought was to use a genetic algorithm to search for the right rule, given an random string of 1's and 0's. However, since there are only a handful of rules that generate randomness, it would be a short search.

The real problem is given a random sequence of 1's and 0's, how do we determine which generation/iteration this string came from and where? Can we run CA rules backwards? I don't see why not.

As mentioned above only a diminishing fraction of CAs are reversible. It is also likely in most of those cases that finding the rule given only data is an undecidable problem.

But given a short string how could you determine the outside influences? I'm thinking here of collisions when one sub-pattern collides with another. Tracing backwards, if there was a collision somewhere earlier, the direction we are going, before our particular random sub-string, we would never come to know the original rule. Sigh.

In Life, the study of even glider collisions quickly becomes impossibly complex.

Are there rules like those defined in mathematics for CA properties like, transitive, symmetric, reflexive, and the like? Clearly based on the thought above CA is not symmetric, you can't run it forward and backward and get the same result.

Maybe your question should be: "Do simple mechanisms provide a more useful way of modelling the irreversibility and irreducibility (perceived randomness) of the world than traditional mathematics?"

Posted by: Franck Binard

It is also likely in most of those cases that finding the rule given only data is an undecidable problem.

I have been running under the assumption that there would be several rules that would 'fit' a particular configuration depending on how much freedom there is to play with other factors such as possible initial states and the number of evolution stages.

It seems to me that the set of rules that fit a particular configuration increases as the size of the set of criterias for deciding the next stage of the evolution increases.

Are there heuristical methods being developed anywhere ? This looks like an AI type of computation to me.

Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings