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?

  • 1
    $\begingroup$ 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. Your question might be suitable for Computer Science which has a broader scope. $\endgroup$ – chazisop May 5 '15 at 13:39
  • $\begingroup$ Cross-posted on cs.se: cs.stackexchange.com/questions/42175/…. $\endgroup$ – Yuval Filmus May 5 '15 at 16:11
  • $\begingroup$ What is "this"? Your question is not well defined. $\endgroup$ – Sasho Nikolov May 5 '15 at 18:05

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.


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