<p>This is a subtle question.</p>

<p>TMs are very much a sequential model of computation. So in some sense, TMs cannot (directly) model multiprocessing. However, TMs can do step-by-step simulations of the reductions a multiprocessor is carrying out. So TMs can do a sequential simulation of a parallel computation. Whether this a genuine model of parallel computation is debatable.</p>

<p>See also the discussion <a href="https://cstheory.stackexchange.com/questions/12377/applicability-of-church-turing-thesis-to-interactive-models-of-computation">Applicability of Church-Turing thesis to interactive models of computation</a>.</p>

CC BY-SA 3.0
2015-05-05T14:53:06.427Z
2015-05-05T14:53:06.427Z
Martin Berger
<p>I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?</p>

CC BY-SA 3.0
2015-05-05T13:39:54.847Z
Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see [help center](http://cstheory.stackexchange.com/help/on-topic). Your question might be suitable for [Computer Science](http://cs.stackexchange.com/) which has a broader scope.
chazisop
CC BY-SA 3.0
2015-05-05T16:11:56.373Z
Cross-posted on cs.se: http://cs.stackexchange.com/questions/42175/is-multiprocessing-possible-on-a-turing-machine.
Yuval Filmus
CC BY-SA 3.0
2015-05-05T18:05:58.420Z
What is "this"? Your question is not well defined.
Sasho Nikolov
<turing-machines><dc.parallel-comp>
Is multiprocessing possible on a Turing Machine?
user2707299
# Is multiprocessing possible on a Turing Machine?

(Asked by: username_0 on 2015-05-05)

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?

**Tags:** turing-machines, dc.parallel-comp
> **Comments:**
> **username_1**: Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see [help center](http://cstheory.stackexchange.com/help/on-topic). Your question might be suitable for [Computer Science](http://cs.stackexchange.com/) which has a broader scope.  
> **username_2**: Cross-posted on cs.se: http://cs.stackexchange.com/questions/42175/is-multiprocessing-possible-on-a-turing-machine.  
> **username_3**: What is "this"? Your question is not well defined.  

---

## 1 answers

### Answer by username_4 on 2015-05-05. Score: 3 | Accepted answer

This is a subtle question.

TMs are very much a sequential model of computation. So in some sense, TMs cannot (directly) model multiprocessing. However, TMs can do step-by-step simulations of the reductions a multiprocessor is carrying out. So TMs can do a sequential simulation of a parallel computation. Whether this a genuine model of parallel computation is debatable.

See also the discussion [Applicability of Church-Turing thesis to interactive models of computation](https://cstheory.stackexchange.com/questions/12377/applicability-of-church-turing-thesis-to-interactive-models-of-computation).


---

