Todd Rowland
Wolfram Research
Maryland
Registered: Oct 2003
Posts: 115 
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 nM 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
