Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time?

If yes, how are the concurrent computations represented and is it possible to convert them into turing machine?

And do they mathematically describe things like race condition and deadlocks?

share|improve this question
Also, see Pi-calculus, CSP, CCS, and numerous other process algebras. –  Dave Clarke Nov 18 '12 at 9:25
Yes, on most readings of the term "represent" Turing machines can represent concurrent computation. Indeed the Church-Turing thesis states that TMs can represent all computation. TMs are not easily usable for the purpose of mathematising concurrent computation, but a large number of alternative formalisms exist for this purpose, primarily process calculi. –  Martin Berger Nov 18 '12 at 9:28
add comment

3 Answers

up vote 3 down vote accepted

As already suggested above, process algebra or process calculus is the place to start. Quoting freely from the respective Wikipedia page,


In the first half of the 20th century, various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing Machines and the lambda calculus possibly being the best-known examples today. The surprising fact that they are essentially equivalent, in the sense that they are all encodable into each other, supports the Church-Turing thesis. Another shared feature is more rarely commented on: they all are most readily understood as models of sequential computation. The subsequent consolidation of computer science required a more subtle formulation of the notion of computation, in particular explicit representations of concurrency and communication. Models of concurrency such as the process calculi, Petri nets in 1962, and the Actor model in 1973 emerged from this line of enquiry.

Research on process calculi began in earnest with Robin Milner's seminal work on the Calculus of Communicating Systems (CCS) during the period from 1973 to 1980. C.A.R. Hoare's Communicating Sequential Processes (CSP) first appeared in 1978, and was subsequently developed into a full-fledged process calculus during the early 1980s. There was much cross-fertilization of ideas between CCS and CSP as they developed. In 1982 Jan Bergstra and Jan Willem Klop began work on what came to be known as the Algebra of Communicating Processes (ACP), and introduced the term process algebra to describe their work.1 CCS, CSP, and ACP constitute the three major branches of the process calculi family: the majority of the other process calculi can trace their roots to one of these three calculi.

share|improve this answer
add comment

Short answer: yes.

Long answer: Using process algebra as a witness to the claimed existential is certainly admissible, but the way the question is phrased might warrant are more direct answer. If TMs are used as mathematical model for sequential computation, we can surely come up with a concurrent version, and show that it is no more powerful than the good old sequential ones.

There are many ways to do so. We could aim for modelling shared variables as a tape shared by a family of TMs, we could add message passing steps to TMs, we could allow TMs to fork off child TMs with their own little tape, or we could invent TM equivalents of starting and ending a supposedly atomic transaction. Every single one of these extensions is easily shown wo be simulatable by an ordinary good old TM. If you're prepared to elaborate where you see a difficulty, the community may be able to help, even if I'm concerned that none of this qualifies as a research-level question.

share|improve this answer
add comment

Also Petri nets form a computational model tailored for concurrency. The basic vanilla system is a finite state based model, but there exist more involved models (having "inhibitor arcs" or "coloured nets") that reach Turing power.

Nice part of Petri nets is their graphical nature. Modern application includes the modelling of biological processes (e.g. in the cell) that are inherently parallel.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.