Turing Fest

A minor storm has erupted in comments for an article I posted long ago, thanks to a link from
Andrew Orlowski

at El Reg. He unburied an article I wrote almost a year ago, an essay about DRM and the Church-Turing Thesis. I am still answering comments as they arrive, so I thought I should put a note here, to alert people that all the fun doesn’t necessarily happen at the top of the blog.

Turing’s math papers have always fascinated me, but everyone seems to have their own interpretation. I try to see it at its most fundamental. I remember seeing an article many years ago, describing the simplest possible Turing Machine. It consisted of a strip of paper and some flat stones that were white on one side, black on the other. The stones represented one bit, on or off. It was suggested that you use a roll of toilet paper, as it was conveniently marked in squares, one for each bit. The human operator flipped the stones and moved the strip of paper left and right, according to the algorithm. It was essentially a cellular automaton in 1 dimension.

And that’s how I think Turing saw these problems. I am particularly fascinated by his papers on Morphogenesis, analyzing the spotted patterns in animal fur, and the variegation patterns in plants. Turing conceptualized the growth of the pattern as a 2 dimensional cellular automaton. But Turing always wanted everything to be written as functions, he considered a function as a fundamental unit of computing on a Turing Machine. If it’s a function, it runs to completion, if it’s not a function, it might be Turing-Incomplete and be incomputable.

Turing’s dense forests of functions are way over my head. I wonder if there are even a handful of people who fully understand them. The papers I read that introduced me Turing’s morphogenetic pattern functions admitted they barely scratched the surface.

Leave a Reply

Your email address will not be published. Required fields are marked *