Theoretical Computer Science
turing-machines dc.parallel-comp
Updated Sat, 21 May 2022 05:44:16 GMT

Is multiprocessing possible on a Turing Machine?

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?


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.