Wolfram – A New Kind of Turing Machine

Stephen Wolfram’s book, “A New Kind of Science” is flippin’ brilliant! (or perhaps I'm just not brilliant enough to realize he's a mad man) 1,280 pages packed with beautiful insights and Tufte-worthy visualizations. I remember discovering it while randomly browsing the MS library one day. I became so enthralled, an hour passed just standing there reading it!  [I should also plug his excellent TED talk]

Just one of the bazillions of wonderful things covered is this simplest possible universal Turing machine. It was proved to be the lower limit on Turing machine universality by Alex Smith in 2007.

The tape head can be in one of two states (up/down) and the tape position may be one of three colors (white/yellow/orange). Of course, Alan Turing’s original allowed an unspecified finite number of states and symbols. The rules for Wolfram’s 2,3 machine are:

For example, the first rule says when in the up state and pointing at orange, then paint yellow, remain up and move to the left. On the other hand, if conditions are the same but in the down state (4th rule) then paint white and move to the right. Starting with a blank (white) tape it produces the following sequence of tape states (nice animation here):

Here’s a quick F# implimentation:

open System.Drawing
open System.Windows.Forms 

let w = 200
let h = 1000
let b = new Bitmap(w, h)   

let tape = Array.create w 0
let rec machine head state y =
  let rules = function
     | 1, 2 -> 1, 1, –1
     | 1, 1 -> 1, 2, –1
     | 1, 0 -> 2, 1, 1
     | 2, 2 -> 1, 0, 1
     | 2, 1 -> 2, 2, 1
     | 2, 0 -> 1, 2, –1
  let state', color, offset = rules (state, tape.[head])
  tape.[head] <- color
  Array.iteri (fun x c -> b.SetPixel(x, y,
    match c with 0 -> Color.White | 1 -> Color.Yellow | 2 -> Color.Orange)) tape
  if y + 1 < h then machine (head + offset) state' (y + 1)
machine (w / 2) 1 0   

let form = new Form(Text="Wolfram 2,3", ClientSize=new Size(w, h), Visible=true)
form.Paint.Add(fun a -> a.Graphics.DrawImage(b, 0, 0))
Application.Run(form)

Comments

• Anonymous
  June 08, 2010
  Lovely, simply, elegant, powerful. Wished there were more ideas like this which bring the scientific ideas closer to the IT industry.Looking forward to more!
• Anonymous
  June 09, 2010
  Awesome!  I love tiny computing machines, and F# is an excellent language for exploring them.
• Anonymous
  June 14, 2010
  Despite the small number of talks on F#, it seemed the language was on everyone’s lips this TechEd. 
• Anonymous
  June 15, 2010
  Hillarious review taken from Amazon (I love the book actually, but it’s true that Wolfram is insanely arrogant :-)Why you are reading this reviewI can only imagine how fortunate you must feel to be reading my review. This review is the product of my lifetime of experience in meeting important people and thinking deep thoughts. This is a new kind of review, and will no doubt influence the way you think about the world around you and the way you think of yourself.Bigger than infinityAlthough my review deserves thousands of pages to articulate, I am limiting many of my deeper thoughts to only single characters. I encourage readers of my review to dedicate the many years required to fully absorb the significance of what I am writing here. Fortunately, we live in exactly the time when my review can be widely disseminated by "internet" technology and stored on "digital media", allowing current and future scholars to delve more deeply into my original and insightful use of commas, numbers, and letters.My place in historyMy review allows, for the first time, a complete and total understanding not only of this but every single book ever written. I call this "the principle of book equivalence." Future generations will decide the relative merits of this review compared with, for example, the works of Shakespeare. This effort will open new realms of scholarship.I am the author of all thingsIt is staggering to contemplate that all the great works of literature can be derived from the letters I use in writing this review. I am pleased to have shared them with you, and hereby grant you the liberty to use up to twenty (20) of them consecutively without attribution. Any use of additional characters in print must acknowledge this review as source material since it contains, implicitly or explicitly, all future written documents.