3 ms·

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.

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.