4 ms·

> These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learnin

> These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc. These can all be converted into sequential algorithms with some overhead. Is there an actual proof in the video or just an argument that something that can't be made sequential must exist?

macleginn 8y ago
As was proved recently, there are quantum algorithms that can not: https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ https://www.quantamagazine.org/finally-a-problem-that-only-q...
- atq2119 8y ago
  First of all, the paper that this article is reporting on doesn't actually prove a separation between quantum and classical algorithms at all. It's an oracle separation result, which makes it an important result in complexity theory, but not a statement about actual classical or quantum algorithms. Second, the result is unrelated to the Church-Turing thesis in the first place, since it's only about relative efficiency, whereas the Church-Turing thesis is about computability. Every quantum algorithm can be simulated by a classical computer, so quantum computing cannot possibly disprove the Church-Turing thesis. However, there's a stronger variant of the Church-Turing thesis which also takes performance into account, and it's plausible that quantum computers can contradict this stronger version (although we're very far away from actually proving that).
jonathanstrange 8y ago
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?

macleginn 8y ago

As was proved recently, there are quantum algorithms that can not: https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ https://www.quantamagazine.org/finally-a-problem-that-only-q...

atq2119 8y ago
First of all, the paper that this article is reporting on doesn't actually prove a separation between quantum and classical algorithms at all. It's an oracle separation result, which makes it an important result in complexity theory, but not a statement about actual classical or quantum algorithms. Second, the result is unrelated to the Church-Turing thesis in the first place, since it's only about relative efficiency, whereas the Church-Turing thesis is about computability. Every quantum algorithm can be simulated by a classical computer, so quantum computing cannot possibly disprove the Church-Turing thesis. However, there's a stronger variant of the Church-Turing thesis which also takes performance into account, and it's plausible that quantum computers can contradict this stronger version (although we're very far away from actually proving that).

jonathanstrange 8y ago

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?