7 ms·

So does any physical computer. Modern computers push that limit into the billions or trillions, while optical interferometry machines are currently stuck in the

by tlb 6y ago

So does any physical computer. Modern computers push that limit into the billions or trillions, while optical interferometry machines are currently stuck in the hundreds or thousands. But you can't guarantee that won't change.

lisper 6y ago
> So does any physical computer. That's technically true, but it misses the point rather badly. The size of the problem that a prism can accept as input is constrained by the physical size of the prism. The size of the problem that a computer can accept as input is constrained only by time. So yes, technically, the universe will eventually undergo heat death and so the amount of time available is finite, but that's just not very interesting.
- adamnemecek 6y ago
  Whether or not it can be spread really depends on the representation you use.
  - lisper 6y ago
    No. Turing machines are universal. All Turing-complete models of computation are equivalent. The representation is irrelevant. That is the whole point of TMs. A TM can do the same computation as a prism, or any other physical system. The converse is not true. That is the reason TMs are a thing.
    - adamnemecek 6y ago
      I wasn’t talking about Turing machines, I was talking about a hypothetical analog photonic computer.
      - lisper 6y ago
        If you think there is a salient difference then you don't understand P=NP at all.
        adamnemecek 6y ago
        Are you legit claiming that a TM the most powerful computational model?
    - teraflop 6y ago
      > A TM can do the same computation as a prism, or any other physical system. To be fair, this is only an unproven hypothesis. The Church-Turing Thesis is an assumption about the physical world (which so far seems to have held up pretty well) rather than a theorem.
      - lisper 6y ago
        It is a hypothesis with no extant counterexample. Discovering a counterexample cannot be ruled out, but it would be the biggest breakthrough in the history of science, so it seems safe to bet against it.
        adamnemecek 6y ago
        Is it? Turing machine has been around for what? 70 years? And photonics has been around for like 50? Wrong theories have been around for much longer.
        lisper 6y ago
        > Is it? Yes, it is. Turing machines can do math, so a system that exhibited behavior that could not be emulated by a TM would have to be one whose behavior is not describable mathematically. No one has been able to come up with any idea of what such a system would even look like, let alone actually produce an example. > Wrong theories have been around for much longer. And crackpots have been around for even longer.
        adamnemecek 6y ago
        It’s about doing math with certain performance characteristics. Check out the book “Real computation”. > And crackpots have been around for even longer. There’s nothing crackpoty about what I’m saying.
    - tlb 6y ago
      Computability isn't really relevant here. I was talking about, for problems that are computable within NP, how big a problem can be solved by physically realizable machines. Turing machines are polynomially worse than von Neumann machines. It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops.
      - lisper 6y ago
        > Turing machines are polynomially worse than von Neumann machines. No, they are not. > It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops. Here you have done exactly what a prism does: put an upper bound on the problem size. When you do that, you can just precompute all the possible answers (because there are only a finite number of possible inputs) and the computation becomes O(1). To assess computational complexity you have to do it with respect to an unbounded input size. And when you do that, you will find than VNMs have only a constant advantage over TMs, not a polynomial one. This is because a VNM has a finite word size and so can only randomly address a finite memory, and so it can be emulated by a TM in constant time. There is no getting around this. Either you bound the input size or you don't. If you do, it's all O(1) which isn't very interesting. If you don't, all computational models are equivalent (except quantum computers, which give you an exponential speedup for some problems). This is the entire reason that computational complexity theory is interesting in the first place, because you can talk about it coherently without committing to a particular model of computation.
- tlb 6y ago
  It's hard to imagine an algorithm with complexity beyond P that don't require intermediate storage as large as n. I suspect there are none, because you need at least n bits of state in order for a program to run for 2^n cycles before halting. In other words NP ⊆ PSPACE and the polynomial growth in space is always at least degree 1 for any algorithm that is more than O(n). So I don't think it's true that "the size of the problem that a computer can accept as input is constrained only by time", except for some O(1) algorithms like computing the parity of a bit stream. Which isn't the sort of thing people are building optical computers to solve.
  - lisper 6y ago
    > you need at least n bits of state in order for a program to run for 2^n cycles before halting Only for a non-embedded system. Prisms are embedded: you have to illuminate them to get them to do anything interesting. So to compare apples and apples you have to consider a case like: connect a microphone to your computer and compute the SHA512 hash of the audio stream. That will require only O(1) space but will never halt as long as the microphone is plugged in.

by tlb 6y ago

lisper 6y ago

> So does any physical computer. That's technically true, but it misses the point rather badly. The size of the problem that a prism can accept as input is constrained by the physical size of the prism. The size of the problem that a computer can accept as input is constrained only by time. So yes, technically, the universe will eventually undergo heat death and so the amount of time available is finite, but that's just not very interesting.

adamnemecek 6y ago
Whether or not it can be spread really depends on the representation you use.
- lisper 6y ago
  No. Turing machines are universal. All Turing-complete models of computation are equivalent. The representation is irrelevant. That is the whole point of TMs. A TM can do the same computation as a prism, or any other physical system. The converse is not true. That is the reason TMs are a thing.
  - adamnemecek 6y ago
    I wasn’t talking about Turing machines, I was talking about a hypothetical analog photonic computer.
    - lisper 6y ago
      If you think there is a salient difference then you don't understand P=NP at all.
      - adamnemecek 6y ago
        Are you legit claiming that a TM the most powerful computational model?
  - teraflop 6y ago
    > A TM can do the same computation as a prism, or any other physical system. To be fair, this is only an unproven hypothesis. The Church-Turing Thesis is an assumption about the physical world (which so far seems to have held up pretty well) rather than a theorem.
    - lisper 6y ago
      It is a hypothesis with no extant counterexample. Discovering a counterexample cannot be ruled out, but it would be the biggest breakthrough in the history of science, so it seems safe to bet against it.
      - adamnemecek 6y ago
        Is it? Turing machine has been around for what? 70 years? And photonics has been around for like 50? Wrong theories have been around for much longer.
        lisper 6y ago
        > Is it? Yes, it is. Turing machines can do math, so a system that exhibited behavior that could not be emulated by a TM would have to be one whose behavior is not describable mathematically. No one has been able to come up with any idea of what such a system would even look like, let alone actually produce an example. > Wrong theories have been around for much longer. And crackpots have been around for even longer.
        adamnemecek 6y ago
        It’s about doing math with certain performance characteristics. Check out the book “Real computation”. > And crackpots have been around for even longer. There’s nothing crackpoty about what I’m saying.
  - tlb 6y ago
    Computability isn't really relevant here. I was talking about, for problems that are computable within NP, how big a problem can be solved by physically realizable machines. Turing machines are polynomially worse than von Neumann machines. It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops.
    - lisper 6y ago
      > Turing machines are polynomially worse than von Neumann machines. No, they are not. > It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops. Here you have done exactly what a prism does: put an upper bound on the problem size. When you do that, you can just precompute all the possible answers (because there are only a finite number of possible inputs) and the computation becomes O(1). To assess computational complexity you have to do it with respect to an unbounded input size. And when you do that, you will find than VNMs have only a constant advantage over TMs, not a polynomial one. This is because a VNM has a finite word size and so can only randomly address a finite memory, and so it can be emulated by a TM in constant time. There is no getting around this. Either you bound the input size or you don't. If you do, it's all O(1) which isn't very interesting. If you don't, all computational models are equivalent (except quantum computers, which give you an exponential speedup for some problems). This is the entire reason that computational complexity theory is interesting in the first place, because you can talk about it coherently without committing to a particular model of computation.
tlb 6y ago
It's hard to imagine an algorithm with complexity beyond P that don't require intermediate storage as large as n. I suspect there are none, because you need at least n bits of state in order for a program to run for 2^n cycles before halting. In other words NP ⊆ PSPACE and the polynomial growth in space is always at least degree 1 for any algorithm that is more than O(n). So I don't think it's true that "the size of the problem that a computer can accept as input is constrained only by time", except for some O(1) algorithms like computing the parity of a bit stream. Which isn't the sort of thing people are building optical computers to solve.
- lisper 6y ago
  > you need at least n bits of state in order for a program to run for 2^n cycles before halting Only for a non-embedded system. Prisms are embedded: you have to illuminate them to get them to do anything interesting. So to compare apples and apples you have to consider a case like: connect a microphone to your computer and compute the SHA512 hash of the audio stream. That will require only O(1) space but will never halt as long as the microphone is plugged in.