1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Would you care to elaborate on what your concern is, when you ask about whether it conflicts with the Turing machine model? They're two different models. Anyway, I can't see any conflict; they're just different. $\endgroup$
    – D.W. ♦
    Commented Sep 21, 2014 at 5:10
  • $\begingroup$ When thinking about formalisms in the realm of Turing Machines, there are many, Non-deterministic, Deterministic, etc. In the BSP model are there any? For instance when we reason about operating systems they have formalisms for message passing, between objects, and so on; Are formalisms for BSP machines similar? Or are we to look at BSP, for parallel algorithms to implement, calculating the determinant, and other numerical algorithms. $\endgroup$
    – user3483902
    Commented Sep 21, 2014 at 5:56
  • $\begingroup$ Unless the Bulk Synchronous Parallel Machine model is a counterexample to the Church-Turing thesis, then you can definitely simulate it with a Turing machine. Similarly, if you can run any single-threaded program using only while and if-then as control-flow constructs, then you can simulate a Turing machine... which would imply they're equivalent from the standpoint of computability. $\endgroup$
    – Patrick87
    Commented Sep 26, 2014 at 19:28

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

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