Wednesday, October 24, 2007

The Shroud of Turing

Oh. My. God. Info-theorists and hacker-philosophers alike are creaming their jeans today at the news that a proof exists for the universality of the 2,3 Turing machine!!

A Turing machine, named for Alan Turing, the prehistoric proto-geek who came up with it, is basically an abstract symbol-manipulation device (This makes you horny. I can tell).

In concept, the Turing Machine theory states that a theoretical device can be adapted to simulate the logic of any computer that could possibly be constructed. Turing machines are an abstract definition of an algorithm, or 'mechanical procedure'.

But wait! There's more! Further down the rabbit hole, a Universal Turing machine is a Turing machine than can simulate other Turing machines.

If your mind is still intact after that last shocking psychedelic blast, keep reading. A UTM, as the hip kids refer to it, can "run" any arbitrary, but well-formed, sequence of instructions, applying them to a set of data. Anyhoo, it's all very complicated and annoying to explain. Go read Wikipedia. I'll wait.

Stephen Wolfram is a crackpot idiot-savant mathematician with a brain the size of a planet. He is monomaniacally obsessed with Cellular Automata, "emergent behavior", and "randomness". To the point that he sequestered himself in Hermit-like seclusion for ten years to write a book that he claims revolutionizes ALL OF SCIENCE.

I have read this book, and while it's not complete bunk, it's far from the next Principia Mathematica. Which is not to say that Wolfram isn't a genius. He's just a misunderstood genius. Specifically, he is misunderstood by me.

The super-secret, no-girls-allowed elite class of Turing Machines referred to as "Universal", are usually described by referring to the number of possible states of the machine, and the number of symbols recognized by the machine (it's alphabet).

A Turing machine has a finite number of states and is in exactly one of these states at any given time. Depending on the current state, and an input value (the symbol), the machine will perform some action, possibly modifying it's state.

Anyhoo, since the mid-60s, and until recently, the simplest proven -- mathematically proven, that is, since scientists rarely lower themselves to the level of actually constructing a physical proof -- Universal Turing Machine was a 7,4 machine. This means that, theoretically, a machine could be constructed using only seven states and an alphabet of four possible symbols that, given sufficient time, could simulate the execution of any algorithm.

FYI: The "simplicity" of a given UTM model is given by multiplying the number of states of the machine by the number of symbols.

Wolfram, the hermit crackpot math weenie, posited the existence of a still-simpler model, a 2,5 UTM, the existence of which was proven by one of his research assistants. According to Wolfram other, smaller UTMs should exist, and he proposed a 2,3 machine as a candidate.

Today, that daring dream, that inspirational flight of fancy has become a breathtaking, flabbergasting reality! The universality of the 2,3 machine has been proven by Alex Smith, an undergrad Electrical Engineering doofus at U. of Birmingham in the UK.

Smith did it for the money, of course (as if there's any better reason). Wolfram's offering a $25,000 prize (my schadenfreude makes me want to make a joke about the exchange rate and failing US currency, but I shall resist).

Being an engineering student, you know he'll spend it all on beer. And to what nobler cause could the funds be put, than to destroy those very brain cells responsible for this amazing contribution to the eternal information-theorist "My UTM is smaller than yours" contest?

Really, what are they compensating for?

Wow, that was possibly my most boring (for people who are not me) post ever. If you managed to make it all the way through, congratulations. Have some boobs:

2 uninformed opinions:

Leila said...

Great. I was having fun until the boobies. Phil, you are your very own 1.1 Turing machine. Which, by the way, you are going to have to explain to me over many beers. During which time I will be wearing a thick-ass sweater, many scarves, and a parka.

Cool Ranch Luke said...

Are you trying to say I have a one-track mind? Because I think this post pretty clearly demonstrates at least two tracks...