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?
Asked
Active
Viewed 178 times
1
-
1Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope. – chazisop May 05 '15 at 13:39
-
Cross-posted on cs.se: http://cs.stackexchange.com/questions/42175/is-multiprocessing-possible-on-a-turing-machine. – Yuval Filmus May 05 '15 at 16:11
-
What is "this"? Your question is not well defined. – Sasho Nikolov May 05 '15 at 18:05
1 Answers
3
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.
Martin Berger
- 11,420
- 3
- 39
- 71