This is very cool, in a way I am far from qualified to articulate: a 20 year old undergraduate has proven that a 2,3 Turing machine is capable of universal computation. Every word I write after that will be one more inaccuracy, but nonetheless here goes: a 2,3 Turing machine is a mechanically very simple device, which can be theoretical or could actually be constructed, as Turing and associates did, and which follows a few simple rules. It’s current “state” depends on it’s state in the last time step: in the case of the 2/3, it has some “heads” which can be either up or down, and it prints on some “paper” in 3 colours. The state of each head and the colour it prints depends on the head positions and previous colours of the line above on the roll of printer paper. Or alternatively, any other 2 and 3 position machine you can imagine. If this sounds to you something like the game of life, that’s because you know more about this stuff than I do. By comparison, the computer you’re reading this on has many, many “states” in the logic gates of it’s CPU. Like millions.

Universal computation means it can accomplish any possible computational task, if you got the rules for up/down white/orange/red colour right. Obviously. Duh.

People have proven that relatively complicated (7 state(?)) machines are capable of universal computation. Which is pretty wild. People claim that 2/2 and simpler machines aren’t capable of it. So the question was: can 2,3 machines do it? Cause if they can, that probably makes them the simplest possible machines capable of universal computation.

Stephen Wolfram, boy genius and subsequent author of the scale-crushing A New Kind of Science was so intrigued by the topic that he offered up $25 000 to the first person to prove (in the mathematical Proof sense) the question either way.

Why is this important? Hell I don’t know. Folks claim that all life and possibly the entire universe is really just a form of information computation, and this impinges on that sort of thinking somehow. I don’t really understand what that means, although it’s somehow provocative to the old imagination.

It also gives us all a fresh excuse to read Cosma Shalizi’s review of A New Kind of Science, one of the most refreshingly acerbic excercises in sharp-blade big-brain academic critique I know.

A New Kind of Science
A Rare Blend of Monster Raving Egomania and Utter Batshit Insanity
….
What, then, is the revelation Wolfram has been vouchsafed? What is this new kind of science? Briefly stated, it is the idea that we should give up trying on complicated, continuous models, using normal calculus or probability theory or the like, which try to represent the mechanisms by which interesting phenomena are produced, or at least to accurately reproduce the details of such phenomena. Instead we should look for simple, discrete models, like CAs (“simple programs”, as he calls them) which qualitatively reproduce certain striking features of those phenomena. In addition to this methodological advice, there is the belief that the universe must in some sense be such a simple program — as he has notoriously said, “four lines of Mathematica”. Most of the bulk of this monstrously bloated book is dedicated to examples of this approach, i.e., to CA rules which produce patterns looking like the growths of corals or trees, or explanations of how simple CAs can be used to produce reasonably high-quality pseudo-random numbers, or the like.
….
As the saying goes, there is much here that is new and true, but what is true is not new, and what is new is not true; and some of it is even old and false, or at least utterly unsupported. Let’s start with the true things that aren’t new.

A disclaimer of sorts: I am a giant fanboy of the idea that the bizarre swirly patterns of the world may be the encrusted aggregate product of a handful of granular basic mechanisms, not least because that would mean that it’s okay if I let down the people trying to teach me the “complicated, continuous models, using normal calculus or probability theory or the like, which try to represent the mechanisms by which interesting phenomena are produced, or at least to accurately reproduce the details of such phenomena”.