But the sentiment is not wrong. There are potentially new computing paradigms that are really good for things that our machines are really bad at. I've always been fascinated by analog computers (machines, really). The old firing solution computers for torpedoes are just precisely machined wheels and gears (TDC, it's called).
But ultimately, for information exchange and transmission, it does seem nature selected for something that strangely appears to be Turing-like: DNA. Perhaps there's something to this Turing machine model after all? I find it interesting too, is all I'm saying.
You can also find the minimum element of a list in logarithmic time instead of linear time if you have enough parallelism available, even though finding the minimum element is O(N).
Only because the prism puts an upper bound on the size of the input. If you do that, every problem is O(1).
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.
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.
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.
> And crackpots have been around for even longer.
There’s nothing crackpoty about what I’m saying.
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.
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.
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.
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.
Also, analog computation schemes tend to rapidly encounter fundamental physical limits. If calculating an N-bit result requires a measurement with N bits of precision, then adding one additional bit tends to require twice as much energy, or twice as big an apparatus, or something of the sort. So even if the "computation" itself looks as if it's O(1), your resource consumption is still exponential.
By that definition computers have AI because humans can communicate through them (i.e. connect a prism to do O(1) Furrier transform vs connect a human for computer to behave like human).