Unconventional Computation

Post date: Apr 12, 2011 2:44:05 AM

Unconventional Computation

by Susan StepneyThe mathematician Stanislaw Ulam is famously quoted as saying that using a term like nonlinear science is like referring to the bulk of zoology as the study of non-elephant animals (Campbell, Farmer, Crutchfield, Jen. "Experimental Mathematics: the role of computation in nonlinear science". Comms.ACM 28(4):374-84, 1985). Unconventional, or non-classical, computation is a similar term: the study of non-Turing computation. But how big is its associated field? Whereas zoology has the advantage of studying many kinds of non-elephants, non-classical computer scientists are currently restricted to studying a few relatively primitive, or dimly seen, or merely hypothesised, devices.

The elephant in the room here is the classical Turing machine, with its 70-plus years of detailed study. Some maintain that there are only elephants, and that the rest of us are like the blind men in the Indian parable, claiming we have found snakes, and ropes, and walls instead. However, I prefer the reversed parable, illustrated with a cartoon of several blind men groping at said snake, and rope, and wall, and confidently declaring, "yes, it’s an elephant!"

The classical Turing machine was developed as an abstraction of how human "computers", clerks following pre-defined and prescriptive rules, calculated various mathematical tables. The abstraction has proved extremely powerful, yet, as an abstraction, it omits certain features.