<p>As already suggested above, <em>process algebra</em> or <em>process calculus</em> is the place to start. Quoting freely from the <a href="http://en.wikipedia.org/wiki/Process_calculus" rel="nofollow">respective Wikipedia page</a>,</p>

<blockquote>
  <p>History</p>
  
  <p>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.</p>
  
  <p>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.<a href="http://en.wikipedia.org/wiki/Process_calculus" rel="nofollow">1</a> 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.</p>
</blockquote>

CC BY-SA 3.0
2012-11-21T21:44:29.160Z
2012-11-21T21:44:29.160Z
Martin Schwarz
<p><strong>Short answer:</strong> yes.</p>

<p><strong>Long answer:</strong> 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. </p>

<p>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.</p>

CC BY-SA 3.0
2013-03-27T11:08:53.110Z
2013-03-27T11:08:53.110Z
Kai
<p>Also <a href="http://en.wikipedia.org/wiki/Petri_net" rel="nofollow">Petri nets</a> 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. </p>

<p>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.</p>

CC BY-SA 3.0
2013-03-30T09:52:02.330Z
2013-03-30T09:52:02.330Z
Hendrik Jan
<p>Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time?</p>

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

<p>And do they mathematically describe things like race condition and deadlocks?</p>

CC BY-SA 3.0
2012-11-18T09:25:57.620Z
Also, see Pi-calculus, CSP, CCS, and numerous other process algebras.
Dave Clarke
CC BY-SA 3.0
2012-11-18T09:28:41.193Z
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](http://en.wikipedia.org/wiki/Process_calculus).
Martin Berger
CC BY-SA 3.0
2012-11-18T13:56:35.667Z
See [Similarities and differences in major process algebras](http://cs.stackexchange.com/questions/465/similarities-and-differences-in-major-process-algebras)
Gilles 'SO- stop being evil'
<turing-machines><dc.parallel-comp><dc.distributed-comp><machine-models><concurrency>
Does mathematical model for conccurent computations exist?
Euphoric
# Does mathematical model for conccurent computations exist?

(Asked by: username_0 on 2012-11-18)

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?

**Tags:** turing-machines, dc.parallel-comp, dc.distributed-comp, machine-models, concurrency

> **Comments:**
> **username_1**: Also, see Pi-calculus, CSP, CCS, and numerous other process algebras.  
> **username_2**: 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](http://en.wikipedia.org/wiki/Process_calculus).  
> **username_3**: See [Similarities and differences in major process algebras](http://cs.stackexchange.com/questions/465/similarities-and-differences-in-major-process-algebras)  

---

## 3 answers

### Answer by username_4 on 2012-11-21. Score: 3 | Accepted answer

As already suggested above, *process algebra* or *process calculus* is the place to start. Quoting freely from the [respective Wikipedia page](http://en.wikipedia.org/wiki/Process_calculus),

> History
>
> 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](http://en.wikipedia.org/wiki/Process_calculus) 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.


---

### Answer by username_5 on 2013-03-27. Score: 2

**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.


---

### Answer by username_6 on 2013-03-30. Score: 1

Also [Petri nets](http://en.wikipedia.org/wiki/Petri_net) 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.


---

