Concurrency and computation

Being mathematically equivalent to a Turing machine may be important for a computer scientist but not so important for an engineer concerned with reliability. Here's the reason I gave two decades ago.

"Even if all processes in intelligent machines are exactly mathematically equivalent to Turing computations, it remains possible that some processes cannot be simulated on a Turing equivalent machine except too slowly for practical use. Even if all can, there may be some important differences. For example, three synchronised machines doing the same task in parallel are mathematically equivalent to one machine, yet the difference in reliability is significant to an engineer."


Aaron Sloman, Beyond Turing Equivalence,
In Machines and Thought: The Legacy of Alan Turing (vol I),
Eds. P.J.R. Millican and A. Clark, The Clarendon Press, Oxford, pp. 179--219, 1996,

Originally presented at Turing90 Colloquium, Sussex University, April 1990,

A slightly more detailed discussion was included in my Review, published in the Artificial Intelligence Journal, August 1992, of:
Roger Penrose, The Emperor's New Mind,

[After discussing differences in speed of physically parallel and sequential implementations of the same program:]
Other differences between parallel and serial implementations are deeper.

Consider the control requirements for a collection of co-existing interacting sub-systems. It is sometimes possible to produce the required interactions on a single time-shared processor, by providing a collection of concurrent virtual machines, but virtual parallel processes on a single machine sometimes have slightly different causal powers from processes implemented on a collection of machines, even when they do compute the same input/output function. One obvious causal difference that is important from an engineering point of view, though not a mathematical point of view, is robustness: a bug in the scheduler or memory management system, or even the central processor, can make a single-processor system go irretrievably awry, whereas a multi-processor implementation could include compensatory mechanisms, for instance one processor detecting the error state of another and doing something to change it. This distinction can also be relevant to the difference between a single process and several processes running time-shared on one computer. If two (or more) interacting processes are always ensured a fair share of the time by the scheduler, then if one process has a bug, or gets stuck in a dead-end search, it can be redirected by another. After all, that's exactly the sort of thing that happens in an operating system. So sometimes the advantages of parallelism are to be found even in virtual machines.

A less obvious point is that a single-processor system simulating N interacting processors would have to cycle through the changes in those processors in sequence. In doing so it would pass through fragile and meaningless intermediate states that don't occur on a true multi-engine machine where all the processors change concurrently. During these intermediate states the machine with virtual parallelism may be incapable of responding coherently to certain inputs. The risks can be reduced if the inputs from the environment are handled by separate processors that buffer all incoming signals until the main processor is ready to handle them (as happens in time-shared computers) but then we are again dealing with a multi-processor system, even though some of the processors perform only lowly buffering functions.

Arguments like this are not normally taken as proof of some difference between simulated and real parallelism because the relevant discussions of computer scientists on such topics as the equivalence of different sorts of computation, are not really about physical computing machinery, for which issues of physical reliability are important, but about virtual machines treated as mathematical objects that cannot have physical flaws.
Maintained by:
Aaron Sloman
School of computer science, The University of Birmingham, UK.