Our 2007 NKS Summer School started about two weeks ago, and one of my roles there was to show a little of how NKS is done.

In the past, it would have been pretty unrealistic to show this in any kind of live way. But with computer experiments, and especially with Mathematica, that’s changed. And now it’s actually possible to make real discoveries in real time in front of live audiences.

I’ve done a few dozen “live experiments” now (here is an account of one from 2005). My scheme is as follows. Sometime between a few hours and a few minutes before the live experiment, I come up with a topic that I’m pretty sure hasn’t been studied before. Then I make sure to avoid thinking about it until I’m actually in front of the live audience.

Then, once the experiment starts, I have a limited time to discover something. Just by running Mathematica. Preferably with a little help from the audience. And occasionally with a little help from references on the web.

Every live experiment is an adventure. And it seems like almost every time, at around the halfway point, things look bad. We’ve tried lots of things. We’ve opened lots of threads. But nothing’s coming together.

But then, somehow, things almost always manage to come together. And we manage to discover something. That’s often pretty interesting. (There are still papers coming out now based on the live experiment I did at our very first Summer School, back in 2003).

I usually make my first live experiment at each Summer School be a piece of “pure NKS”: an abstract investigation of some simple program out in the computational universe.

This year I decided to take a look at an “old chestnut” that I’d recently been reminded about: a simple program (though it wasn’t thought of that way then) that was actually first investigated all the way back in 1920.

Here’s the story. In 1920, a young math graduate student at Princeton named Emil Post was trying to understand the structure of Whitehead and Russell’s Principia Mathematica: their very complicated attempt to formalize the foundations of mathematics. And Post did what any good modern NKS student should do: he tried to simplify things as much as he could.

Eventually he came up with an abstract system that he thought might capture the essence of what Whitehead and Russell were doing. His system worked like this. It had a sequence of 0’s and 1’s, say 011101010101. And it proceeded in a sequence of steps. At each step, it chopped off the first three elements in the sequence. Then if the first of those elements was 0 it appended 00 to the end, and if the first element was 1 it appended 1101.

And it kept on doing this.

Pretty simple, eh? Well, Post started playing with the system back in 1920. He thought he’d be able to “crack” it easily. But it wasn’t so simple. He found that the system could do some pretty complicated things. And actually he couldn’t really tell what the system was doing. And after months of work he just gave up. And decided to write his thesis about a much more traditional area of mathematics.

Perhaps if he’d kept going, Post might have come up with NKS, all the way back in 1920. And in fact a few years later, Post also narrowly missed discovering what Alan Turing discovered with Turing machines. Post came back to his “problem of tag” (as he called his NKS-like system) one more time, in the early 1940s. But he never cracked it. And he died, after a somewhat difficult life, in 1954.

So, I decided to see how we could do now on Emil Post’s 1920 problem. I’d already looked at the problem a bit nearly 15 years ago for the NKS book, but I thought that with the capabilities of Mathematica 6, I’d be able to get further.

Here’s a screen shot of the complete notebook from the live experiment I did:

If you look at plots like this of sequence length vs. time

you realize why Post had a problem. Starting say with 11010101011000011001, it takes over 2000 steps before the system settles down to periodic behavior. Of course, that takes only a fraction of a second to discover with Mathematica today. And to look at lots of other cases—seeing whether they ever settle down.

Well, we figured out quite a lot of new things about Post’s tag system during the experiment. But I’m sorry to say we didn’t completely crack it. In fact, it’s my guess that it’s at least as hard to crack as the 2,3 Turing machine that’s the subject of our recent prize.

But one thing we did do is see what Post’s system in a sense should have been: we found the very simplest tag system of Post’s type that shows complex behavior.

It only chops off two elements at each step, and it adds 01 or 100. Really simple. Yet this is what its sequence length does starting just from 10:

Well, actually, that’s not quite the sequence length. Curiously, we found that the sequence length seems on average to increase by exactly Sqrt [2]-1 at each step (which would be interesting to prove). So the plot above is the “detrended” sequence length.

We discovered the minimal tag system with complex behavior at 17:12:12 ET on June 25. It’s a pretty interesting system. For example, so far as we could tell it makes perfect randomness. Quite remarkable. Perhaps in some ways it’s the very simplest system ever found that does this.

It would have been a lot of fun to go on investigating it. And I’d hope people will now do that. It’ll make for some very interesting papers that I look forward to reading…

But as it was, I was told that we had to finish before 5:30pm, or everyone would miss dinner. So I stopped. Satisfied that in a couple of hours of live experimentation we’d discovered at least one thing that’ll one day be in the textbooks.

I just now finally got time to write up this post about our experiment, and in doing so, I thought I’d use the Cell > Notebook History… menu item in Mathematica 6 to look at the actual history of our experiment.

Here’s the plot I got:

It almost looks like one of the systems we were studying. But actually what it shows is how we built up the notebook of our experiment. Each dot represents a change in a cell in the notebook. The cells run down the page, and time runs across the page.

So what we see is that we started a little slow. Then really sped up. Then got kind of stuck around 4pm (my “halfway point” phenomenon). But finally around 5pm pulled out again—and a little later made our main discovery. Without even missing dinner.