Johnny Logic

Notes Toward a Broad Notion of Computation

When most people think of computers, naturally they think of their desktop PCs. Philosophers inherit this conception, which leads to some quarrels for those of us who wish to extend the notion of computation to natural processes. I wish to argue that computers are more common than most philosophers think, if not ubiquitous. I will start with the uncontroversial observation that integrated (non-programmable) computers are all around us in the form of watches, soda machines, automatic door openers, stoplights and so on. These are understood to be computers in that they lawfully change states; given certain inputs they return certain outputs. This is uncontravercial.

Moving on to natural objects, we may (borrowing from Dennett’s Darwin’s Dangerous Idea) look at the sand distribution on the beaches as the result of a sorting algorithm implemented by the waves of the ocean. The animals we see today (including ourselves) may be seen as answers (outputs) from an ever-changing blind optimization problem (evolution). Again, these processes lawfully change states and, given particular inputs, they return particular outputs. Conceived so generally, anything may be regarded as a computer—the object need not be man made.

Is this merely poetic use of language? I don’t think so. Such a perspective reveals patterns that are as real as atoms, quarks and galaxies.

Non-standard models of computers may help us integrate more systems into the category of computers. The chief computer components are memory (serves as storage for representations, tokens, data structures), and control (serves is to manipulate representations, tokens). It is important to note that memory and control do not have to be performed by separate components—they may be integrated as in neural networks and cellular automata. The control may be digital or analog, as may the memory. In the case where both are analog, the system is dynamical and is typically described by differential equations and the like.

Some relevant distinctions/properties, which combine to make a large class of computing objects i.e. a broad notion of computation:
Analog Control (interacting continuums could compute what?)
Digital Control
Analog Memory (infinite storage and retrieval of information only if there is infinite control?)
Digital Memory
Infinite Control*
Finite Control
Infinite Memory**
Finite Memory**
Sequential Control
Parallel Control
Sequential Memory
Parallel Memory
Quantum
Classical
Probabilistic (non-deterministic machines differ from probabilistic; non-deterministic machines are rather like parallel machines, I think)
Deterministic
Dimension (just one is needed for CAs to be universal when programmed correctly)
Abstract Automata
Concrete Transducer (implementation concerns about sub-computational properties e.g. noise, wear and tear, retaining logical structure and other ceteris peribus issues)

* Oracles must use infinite precision control to work—thus the insurmountable implementation problems.
**This is where Chomsky’s Hierarchy is established by magnitude and structure (stacks, queues, two-way tape)

Machines (logical and physical):
Neural Networks
SIMD (Single Instruction, Multiple Data)
MISD? (Multiple Instruction, Single Data)
MIMD (Multiple Instruction, Multiple Data)
Analog Computers (e.g. Spaghetti Sorter, Vannevar Bush's Differential Analyzer)
Turing machine
Multiple Tape Turing Machine
Multiple Head Turing Machine
PC
Quantum Computers
Cellular Automata (1 to n dimensional)
Moore/Meally Machines
Integrated Chips

More Questions:
What about Gandy Machines? Post Machines?
What other types of computer should I consider?
Are there more relevant properties to consider?
Have I made any egregious errors?

Posted by John at January 23, 2004 05:35 PM