[Solved]: Is multiprocessing possible on a turing machine?

Problem Detail: 

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 By : user2707299

Answered By : Yuval Filmus

You can consider two variants of this question.

1. Can a Turing machine simulate parallelism?

2. 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42175

3.2K people like this

 Download Related Notes/Documents