A new kind of science - questions
The NKS2006 (New Kind of Science) conference is announced here, where a large number of questions are posed that ask what can be done with NKS (essentially, NKS is science based on elementary algorithms, rather than based on elementary mathematical functions as is usually the case).
Here is the list (copied from here), with each question highlighted in bold, and with my comments appended. Note that my comments do not imply that I am keen to see things happen the way that is predicted in various places below (e.g. Ray Kurzweil's imagined future).
- Will algorithm mining revolutionize software development? You need a way to detect when an algorithm is doing something useful, which requires a meta-algorithm for observing the algorithm under study. For instance, development via the process of Darwinian evolution uses a meta-algorithm (i.e. survival of the fittest) that has demonstrably led to some truly revolutionary developments. If we do simulated evolution (e.g. genetic programming) then we can guide the developments, but we have to be careful not to guide too closely otherwise we will miss the revolutionary developments.
- Is there a core computational architecture in biological cells? It is difficult to see how Darwinian evolution could work without reusing standard building blocks developed during earlier stages of evolution. If you don't allow this sort of reuse then you end up with the naive argument-against-evolution, which reasons that the chance of everything working together in exactly the right way is so vanishingly small that things must have been deliberately designed by an external agency.
- Will generative content revolutionize the entertainment industry? Virtual reality will rival and surpass real reality. The quality of the rendering is currently limited by computer power rather than by lack of algorithms, although improvements in both would be welcome. Ray Kurzweil suggests that nanobots could connect up directly to our nervous systems to provide a vivid virtual reality. Now that would be amazing, but rather invasive.
- How will computer experiments change the face of mathematics? Experimental mathematics allows us to escape from focussing only on computationally extremely-reducible problems which are amenable to analysis based on properties of elementary mathematical functions. Experimental mathematics allows possible solutions to be explored much faster, whether or not they are computationally reducible. I find a good research strategy is to use experimental mathematics to do a numerical search to find potentially interesting relationships/patterns/etc, which I then attempt to prove (if the result is computationally reducible) by more conventional means.
- Are there business structures founded on computation universality? I don't know the answer to this one, but I do have experience of the failure of computation universality. In my own narrow experience of business structures they attenuate the propagation of information, so the right hand doesn't know what left hand is doing. There are certain types of computation that simply cannot be done in the types of business structure that I have been exposed to. For instance, top-down dogma is frequently used to override bottom-up information (e.g. that's what led to the Challenger shuttle disaster).
- What would an operating system for a swarm of microbots be like? Each single time step causes the invocation of a number of elementary update operations, and the elapse of multiple time steps causes the emergence of collective phenomena. The design of a suitable set of elementary update operations to lead to a required set of emergent phenomena is a hard problem. Simulated evolution is a way of developing such systems.
- What kinds of artificial physics can support quantum mechanics? Multiway systems allow the parallel branching behaviour that you need to implement QM. Any artifical physics that allows this type of multiway branching has a QM-like flavour.
- Will artificial life arise spontaneously within the internet? With some help from us to start it off, then the answer is yes. Ray Kurzweil's prediction of where evolution is taking us is probably how it will happen. He suggests that you will have biological humans who are enhanced by machine-like add-ons, and that eventually the add-ons will become so fancy that the biological part becomes irrelevant and unnecessary.
- Can one map the space of all possible economic systems? I don't know.
- Will the next core computer architecture be discovered by search? Not the next one, but one further down the line. Massive fine-grain parallelism (e.g. networks that are as large as a human brain, in terms of nodes and connectivity) can be developed by a combination of simulated evolution (to develop network structures) and self-organisation (to allow the plasticity in each such network to adapt to the environment).
- Can we enumerate the morphologies of possible biological organisms? If there is a "core computational architecture in biological cells" (see earlier) then the answer is "yes".
- What pattern recognition algorithms can molecules implement? Indirectly they can do very clever pattern recognition (e.g. DNA controls the construction of brains which then do pattern recognition). Directly they do only elementary pattern recognition (e.g. sensing signals), and if the molecules can communicate with each other then they can do some simple signal processing (e.g. smoothing, differentiation, etc). It is hard to see how molecules can themselves do cleverer things than this directly, so if you want to do fancy pattern recognition you have to use the molecules indirectly as a program (e.g. DNA) to construct the pattern recognition engine (e.g. a brain-like processor).
- What does computational irreducibility mean for supercomputing? You can't simplify a computationally irreducible problem, so the fastest way of solving it is to use a programmable architecture to create a special purpose super-computer for running your computationally irreducible problem. The software for solving a computationally irreducible problem would effectively be a blueprint for constructing the corresponding special purpose architecture.
- Is there an algorithm for telling if an object was designed? We know that computationally irreducible processes lead to structures that have arbitrary complexity, and that look as if they have been "designed". Can one look at a structure and reverse-engineer the underlying rules (if they exist) that led to it? This is a computationally hard problem, so there is no algorithm that will always work.
- Will the most important nanomaterials be intrinsically random? Important materials will "design" themselves (i.e. self-organise). Such self-organisation is computationally irreducible because you have to go through all the intermediate steps to get to the result. The results can therefore be apparently random.
- Can a single rule design the complete structure of a building? No. Unless you are a mollusc, that is.
- Is there an absolute measure of elegance for programming languages? "Elegance" = "Brevity". That's one reason why I like Mathematica.
- What is the network analog of a recursive function? Nested propagation loops in a network do a recursive computation, where the meaning of "recursive" has been broadened somewhat. This is analogous to computing a multi-loop perturbative expansion in quantum field theory, where the exact result of the computation is a recursively "dressed" version of the leading order approximation to the result.
- Can we find the simplest undecidable problem in number theory? I don't know.
- What would prove the Principle of Computational Equivalence? I don't know.
- What will happen if kids learn cellular automata before algebra? A lot more copies of Mathematica will be sold. There will be a move away from the "classical" approach using toy models that are usually selected for their analytic tractability (i.e. computational reducibility), and a move towards simple models with useful emergent phenomena (a.k.a. "effective theories") that are computationally irreducible.
- What will be the first major industry created by mining the computational universe? Human-level (and better) artificial intelligence. Simulated evolution will be used to search the space of simple algorithms for ones that lead to emergent properties that have "useful" properties. Very large scale brain-like processors will probably be developed in this way.