The Turing model of computing is widely accepted, as a Tape, Head, State registe

Question

The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part similarity to the PRAM model, but with additional features in state management, by communication, and synchronization. So, in a sense it implies barrier synchronization, communication, and concurrent communication implicit in its workings, with processors having an order imposed on them. Does this conflict with the Turing machine model(?). Can one simulate one model by the other? Are they equivalent, or are there differences between these models?

Explanation / Answer

I don't know the particulars of the bulk synchronous parallel machine, but it is highly likely that both have the same computational power, that is, both machines compute exactly the class of recursive languages. The difference between the models lies in their corresponding complexity measures: a language that has a certain (time or space) complexity in one model could have a different complexity in the other model.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.