EECS Publication
The Nature of Computing - Computing in Nature
Bruce MacLennan
My goal in this report is to recontextualize the concept of computation. I review the historical roots of Church-Turing computation to show that the theory exists in a frame of relevance, which underlies the assumptions on which it rests and the questions it is suited to answer. Although this frame of relevance is appropriate in many circumstances, there are many important applications of the idea of computation for which it is not relevant. These include natural computation (computation occurring in or inspired by nature), nanocomputation (computation based on nanoscale objects and processes), and computation based on quantum theory. As a consequence we need, not so much to abandon the Church-Turing model of computation, as to supplement it with new models based on different assumptions and suited to answering different questions. Therefore I will discuss alternative frames of relevance more suited to the interrelated application areas of natural computation, emergent computation, and nanocomputation. Central issues include continuity, indeterminacy, and parallelism. Finally, I will argue that once we understand computation in a broader sense than the Church-Turing model, we begin to see new possibilities for using natural processes to achieve our computational goals. These possibilities will increase in importance as we approach the limits of electronic binary logic as a basis for computation. They will also help us to understand computational processes in nature.
Published 2005-10-17 04:00:00 as ut-cs-05-565 (ID:167)