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?
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.
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.
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.
The proof is a little trickier than I remembered. There's a bit more housekeeping to handle that each head can be on a different cell of their respective tapes.
Try coming up for a proof for the case where each head moves in the same direction so they're always all on the same position of their tapes first. This can be extended to the general case by some annoying bookkeeping.
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?