Registered: Mar 2004
Posts: 132

What is enumeration really?

What would it mean if we could describe some kind of system and then be able to make every kind of that system like that one after the other?

Nth simple program? What would that be like?

What about being able to combine of the simple programs that we know about so far into one single framework and then be able to just count, and eventually reach all of them? Can we do that?

What about just cellular automata. Can we devise an enumeration scheme that covers all neighborhoods, dimensions, and colors in a single sweep?

Can we devise an enumeration scheme for cellular automata that has no repeats? What about no color repeats?

What about being able to enumerate certain kinds of rules, like totalistic rules in cellular automata, in all colors, neighborhoods and dimensions?

What about having something like the nth network?

the nth symbolic tree? the nth Mathematica pattern?

the nth math problem?

If we can use networks to represent spaces with dimensions that are not whole numbers. Is there a way to find out how to make all of them and see what they look like? Nth regular network topology?


Well those are some questions. I guess a funny thing is that you can put Nth in front of any kind of system you can think of and come up with a worthwile question that pertains to NKS, and great to find a yes or no for.

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 172

The question mentioned in the previous post "what is enumeration?" is definately important.

Are we using numbers to enumerate? Fine. We could have just as well used the alphabet, colors, or chicken scratch. The symbols mean nothing really.

Let's stick with numbers for the sake of tradition.

However, isn't a number just an instance of terminating algorithm? Or maybe the number is just a time slice of a one single recursive algorithm.

Maybe enumeration is very much like time. The act of enumerating (ex:giving the Nth symbol) is basically similar to taking a slice of time.

Interesting thought: something that has no end (an unending algorithm) can not be a "slice" of a recursion.

__________________
P h i l i p . R . D u t t o n

Last edited by Philip Ronald Dutton on 12-27-2005 at 08:10 PM

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

Interesting thoughts. The short answer is any universal machine can do the trick of enumerating all of these things, with repetitions.

It is probably worthwhile considering the question of automating the process of doing NKS, and how computational irreducibility figures into it. On the positive side, we can make tools, such as those which enumerate cellular automata.

Computational irreducibility makes me think that any single enumerating program of all rules would necessarily mislabel some programs as complicated when they should be regarded as simple.

It might be worth pointing out that in a limiting sense, any universal program would suffice, and that there is at worst a constant error. So if one has two machines, and a program in the first labeled as rule n, then the rule number in the other machine is at least n-M where M depends only on the two machines in question. From the point of view of NKS, such a constant M is too big to make this observation meaningful, and can lead to mislabeling a simple rule as complex.

It would seem that the problem of enumerating without repetition is much more severe, because it might be undecidable whether two are the same. One can imagine a situation like X can emulate Y, as long as the substring ABBA does not occur, and furthermore be in the situation where the occurence of ABBA is undecidable.

Report this post to a moderator | IP: Logged

Registered: Mar 2004
Posts: 132

Perhaps there is some way of detecting that rule 60 will always have its output be possible to compute as a function of the coordinates?

Could a more general pattern be made to cover all rules that behave like rule 90 by some simple similar manner?

Maybe you would not be able to get all cases of nested 90-ish behavior in cellular automata, but perhaps you could get just some small slice that is for sure?

One might be able to create a class of "left-on, right-on, both-off" cellular automata that could expand to block CA's as well as higher ranges and numbers of colors, that might all generate the same rule-90 type behavior. Kind of a telescoping action, where you make a generalization about a system and then make all systems under that generalization, per rule or some way. How does that sound?

Report this post to a moderator | IP: Logged