Science & Code

• Felix May 6, 2010

  Wolfram, NKS and lot of books

  Culture, General, Science

  Caused by an intensive (yet, sadly, fruitless) use of Wolfram|Alpha¹ I recently came upon the strange phenomena duped NKS and its inventor² and main proponent Stephen Wolfram. What a strange character.
  

  Here, see him in action:
  
  (Note: There is a new video of him out there on TED. I did not yet have the time to see it, but I assume its the same spiel again)

  His observations of cellular automata are quite nice (and brilliantly illustrated, the staunchest critic has to admit that his visualisations are exquisite) but they are exactly that: only observations. His “New Kind of Science” simply appears to me as a practical application of automatons — he makes a lot of claims about progress being made with NKS, but so far I could only find little gadgets like the notoriously named Wolfram Tones project or some obscure procedural art stuff.

  I want to dissect a certain cornerstone of his work, the concept coined “Mining the computational universe”. First, let me rephrase the basic idea:

  For a given computational problem, instead of hand-crafting an algorithm (or a heuristic for that matter) to solve it, one generates a random program of fixed size and evaluates its performance on the given problem. In case of a bad performance one simply tries again. Eventually, one will find a program that performs reasonably well and thus solve the problem.

  Instead of bashing NKS, Wolfram and Wolframs ego (two distinct entities, I suppose) I want to add a my two cents for Why I Think This Is Crap (I will not go into his claims about mining a GUT for our universe, let the physicist laugh about those).

  Hamlet, King of Norway

  First, let me introduce you to the concept of the Library of Babel, also called the infinite library. Imagine a library which contains every book ever written by anyone. Even books which have not been written yet are there! Sounds great, doesn’t it? The library has only a tiny flaw: it also contains every possible book, that is, every possible combination of letters there is on a finite number of pages (let’s say books are limited to 500 pages).

  Sadly, now our library has become useless: not only is the vast majority of books gibberish (at least to us, some of them could actually mean something in a strange language, but I digress…), but the books that are actually readable might simply be inconsistent or, under some notion, wrong. Imagine searching for Shakespeare’s Hamlet. On your long (but finite) search you will not only find Hamlet, but also Hamlet with Hamlet as the Prince of Norway or Hamlet with a Happy End (he and Ophelia stage her deaths and they flee to England together) and even Hamlet wielding a sub-machine-gun during the showdown. Not to speak of the many, many Hamlets riddled with spelling errors, missing chapters, mixed up chapters… you catch my drift.

  What Stephen Wolfram tries to sell as a new approach not only to computational problems, but science in general, is exactly this infinite library, this time with cookbooks. Imagine that you start with a fixed set of ingredients and pick out a random recipe (we assume that the recipes do not explicitly state the ingredients, but only the recipe, like “Mix ingredient one with ingredient two and stir until mixture jumps wasp”³ ) and apply it to our ingredients, maybe even multiple times (these are Small Recipes, after all). After some trial and error one might actually get a cookie, but what if one wants Ginger Shortbread? How many tries would be needed? The claimed success of this mining approach solely lies in the loose definition of “solving a problem” — in my opinion the reason why it has not gone far beyond Wolfram Tones. If we define a problem with a very broad sense of “solution”, of course we will quickly find one by trying out random ones. Using automata (of whatever flavor) as a mediator simply adds some structure to the result, but this is only a good idea if one actually expects structure. Try solving NP hard problems with this approach and you will certainly hit a brick wall.

  Some personal experience

  Now, I am not entirely disinclined to the whole mining idea. Using cellular automat for stuff is cool and often pretty quick. Rember the java wave applet? The one that turned cheesy images in pure kitsch by adding a water surface below it? The one that even ran on my slow-poke Pentium 2 MMX? It uses a pretty simple cellular automata. But: it was hand-craftet. The automata itself was designed, not fished out of the computational space at haphazard.

  But on to my personal experience. I have been playing around with random map generation for a simple strategy game and, being lazy as I am, was eager to find some automata that would do all the work for me. Starting with a two-colored (land/water), totalistic (I will get to that in a moment) six-neighbour automata (the maps use hexagonal tiles) I had the first small success: several automata showed a pretty good behaviour of converting random noise into coherent shapes vaguely resembling coasts and islands. The next step would be to add woods and mountains to the land for some interesting tactical opportunities… and that’s where the whole thing came crashing down.

  You see, a totalistic cellular automata simply sums up his neighbourhood and decides according to the sum what to do, while a normal cellular automata is not symmetric in that respect (neighbourhoods with different sums might yield different results). Therefore, totalistic automata are pretty small — you don’t need many bits to describe one — but are also limited in their behaviour. In a certain sense they always produces something symmetric (which can be damped by feeding it random input). And I could simply not find any that could produce a reasonable looking landscape.

  The next step was simply to drop the totalisticity (???) and mine for any automata… but then the number of possibilities and thus the probability of failure grow quite dramatically. Until then I simply looked at the output of randomly selected automata and judged for myself which ones did good, but this procedure is of course pretty straining and slow. I therefore started to set up an automatic mining process by teaching the program for what to look in a map: connectedness, good land/water ratio, some tactical considerations… But then it struck me: what I was about to do would be much more time consuming than hand-crafting an algorithm which would assure these things by design. I could simply grow the landmasses in a way that looks natural and assures a good land/water ratio, then I could place the mountains and woods in fashion that assured that certain tactical opportunities arise; I could correct the map by using the scaffolding data structures (like a topological graph which easily shows which regions are disconnected from each other)… all that would be much, much simpler to do.

  Of course, this is only anecdotal. There might be a 6-neighbour, 4-color cellular automata out there creating the most dazzling and tactically demanding maps. But the effort to find such an automata greatly overshadows the simplicity of just doing it myself. If you find it, please feel free to share it with me ;)

  1. Tell me any other tool that can answer important questions like this? [↩]
  2. I’ve read several accusations of Stephen Wolfram stealing ideas; at least one can say he did not properly address previous work in that direction [↩]
  3. We are still talking about an infinite library, what do you expect? [↩]