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?
You can consider two variants of this question.


Can a Turing machine simulate parallelism?
Can a Turing machine simulate parallelism efficiently?


The answer for the first question is a resounding affirmative. Just like your own OS simulates threads on a single-core CPU, so a Turing machine can simulate parallelism.

Regarding the more refined second question, it depends on your definition of efficiency. You can probably simulate parallelism with at most a polynomial blow-up in resources (mainly time).

Turing machines are not a good model if you care about concrete efficiency. The more appropriate model is the RAM machine. RAM machines can probably simulate parallelism pretty efficiently, though you should not accept a running time any less that the combined running times of the individual threads in your parallel solution.