4 ms·

A parallel OR will terminate even if one of the subclauses does not terminate, whereas sequential OR might not terminate in this case. So if you define an algor

A parallel OR will terminate even if one of the subclauses does not terminate, whereas sequential OR might not terminate in this case. So if you define an algorithm as a computation that terminates, parallel OR cannot be fully emulated by sequential OR. The problem is that, as far as I know, sequential algorithms form a uniform class, because e.g. equivalence between different sequential models like Turing machines and the untyped lambda calculus can be proved. AFAIK, this is not possible for parallel models of computation, there are different models of them with different expressivity. (I'm not an expert on that, so take this with a grain of salt and please correct me if I'm wrong!)

daveFNbuck 8y ago
What are you using the acronym OR to mean? Why can't you define a sequential machine that simulates it and terminates under the same conditions? For all the parallel modes of computation I've seen, you can pretty easily simulate them on a single machine by just keeping the full state of each machine and simulating each time unit 1 machine at a time. It's slow, but equivalence isn't about speed.
- overdrivetg 8y ago
  Took me a minute as well - I think he means logical OR (vs logical AND, etc) ie IF (A OR B) THEN ...
- jonathanstrange 8y ago
  Yes, logical OR.
  - daveFNbuck 8y ago
    Why couldn't you simulate that sequentially by simulating 1 step of each computation until one of them returns true or both have terminated?
    - jonathanstrange 8y ago
      Oh man, you and overdrivetg are right, of course. I was silently assuming that A and B are atomic operations or inputs to an open system; otherwise it should be possible to emulate parallel OR. Now this casual remark during my work time is starting to bother me a lot, and I really hope some distinguished expert could jump into the discussion. We know that the pi calculus can embed the lambda calculus (and similar for other parallel models of computation), and I've always assumed that the opposite is not generally true - that you cannot express all parallel computations on Turing machines or in lambda calculus such that the same input yields the same output, at least not if you allow some of the computations not to terminate. Now I'm no longer sure about that and cannot find any foundational theorem that would prove this. Am I the victim of a prejudice? :o Where are the computer scientists when you need them?
      - daveFNbuck 8y ago
        If you want an expert's opinion, I have a PhD in theoretical computer science. I'm not familiar with pi calculus, but parallel models of Turing machines can be fully simulated by standard Turing machines by just simulating a time step on each machine before moving on to the next time step.
        jonathanstrange 8y ago
        Since merely having a PhD in theoretical computer science doesn't really count for being an expert in this area, do you happen to have a reference for that? Don't get me wrong, I do believe you, but am looking for the relevant theoretical results about this.
        daveFNbuck 8y ago
        That's fair. I only mentioned it because you asked for a computer scientist. One simple model of a parallel Turing machine is one with multiple tapes, each with its own read-write head. They all operate simultaneously based on the global state. This is a very general form of parallelism. Wikipedia has an article [1] about them with some references for proofs that they're equivalent to single-tape Turing machines, but I encourage you to try to prove it yourself. It's fairly simple to prove, I'm pretty sure I've seen it as an undergraduate-level homework problem. If you want a hint, try increasing the number of tape symbols so that you can encode the entire global state on one cell of the single-tape machine. It's a bit more work, but you can also show that two symbols are enough to simulate a Turing machine with any number of symbols. [1] https://en.wikipedia.org/wiki/Multitape_Turing_machine https://en.wikipedia.org/wiki/Multitape_Turing_machine
overdrivetg 8y ago
Well... you can still execute the OR essentially via BFS vs DFS... Spend some "cycles" or steps executing one path, then the other, then keep alternating. Eventually you will hit the termination (if it exists). Or essentially, you can always simulate parallel algorithms on sequential hardware. Of course you are correct if the sequential OR is executed naively :-) ...or if you force side-effect free short-circuiting within the sequential OR execution. But then it wouldn't really the same OR (as in the parallel case), now would it?

daveFNbuck 8y ago

What are you using the acronym OR to mean? Why can't you define a sequential machine that simulates it and terminates under the same conditions? For all the parallel modes of computation I've seen, you can pretty easily simulate them on a single machine by just keeping the full state of each machine and simulating each time unit 1 machine at a time. It's slow, but equivalence isn't about speed.

overdrivetg 8y ago
Took me a minute as well - I think he means logical OR (vs logical AND, etc) ie IF (A OR B) THEN ...
jonathanstrange 8y ago
Yes, logical OR.
- daveFNbuck 8y ago
  Why couldn't you simulate that sequentially by simulating 1 step of each computation until one of them returns true or both have terminated?
  - jonathanstrange 8y ago
    Oh man, you and overdrivetg are right, of course. I was silently assuming that A and B are atomic operations or inputs to an open system; otherwise it should be possible to emulate parallel OR. Now this casual remark during my work time is starting to bother me a lot, and I really hope some distinguished expert could jump into the discussion. We know that the pi calculus can embed the lambda calculus (and similar for other parallel models of computation), and I've always assumed that the opposite is not generally true - that you cannot express all parallel computations on Turing machines or in lambda calculus such that the same input yields the same output, at least not if you allow some of the computations not to terminate. Now I'm no longer sure about that and cannot find any foundational theorem that would prove this. Am I the victim of a prejudice? :o Where are the computer scientists when you need them?
    - daveFNbuck 8y ago
      If you want an expert's opinion, I have a PhD in theoretical computer science. I'm not familiar with pi calculus, but parallel models of Turing machines can be fully simulated by standard Turing machines by just simulating a time step on each machine before moving on to the next time step.
      - jonathanstrange 8y ago
        Since merely having a PhD in theoretical computer science doesn't really count for being an expert in this area, do you happen to have a reference for that? Don't get me wrong, I do believe you, but am looking for the relevant theoretical results about this.
        daveFNbuck 8y ago
        That's fair. I only mentioned it because you asked for a computer scientist. One simple model of a parallel Turing machine is one with multiple tapes, each with its own read-write head. They all operate simultaneously based on the global state. This is a very general form of parallelism. Wikipedia has an article [1] about them with some references for proofs that they're equivalent to single-tape Turing machines, but I encourage you to try to prove it yourself. It's fairly simple to prove, I'm pretty sure I've seen it as an undergraduate-level homework problem. If you want a hint, try increasing the number of tape symbols so that you can encode the entire global state on one cell of the single-tape machine. It's a bit more work, but you can also show that two symbols are enough to simulate a Turing machine with any number of symbols. [1] https://en.wikipedia.org/wiki/Multitape_Turing_machine https://en.wikipedia.org/wiki/Multitape_Turing_machine

overdrivetg 8y ago

Well... you can still execute the OR essentially via BFS vs DFS... Spend some "cycles" or steps executing one path, then the other, then keep alternating. Eventually you will hit the termination (if it exists). Or essentially, you can always simulate parallel algorithms on sequential hardware. Of course you are correct if the sequential OR is executed naively :-) ...or if you force side-effect free short-circuiting within the sequential OR execution. But then it wouldn't really the same OR (as in the parallel case), now would it?