3 ms·

I think it has to be. The former problem is about computational complexity; the latter is about computability. I don't know much about this topic -- I skimmed

by chubot 9y ago

I think it has to be. The former problem is about computational complexity; the latter is about computability. I don't know much about this topic -- I skimmed through Scott Aaronson's "Quantum Computing and Democritus", and got lost by the last third. As far as I remember, it was all about computational complexity. I don't recall anything about computability, but correct me if I'm wrong. I just had to look up the strong Church-Turing Thesis: The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis I don't have much justification, but I believe it's false. There is a lot more to the universe than computers. Computers cannot simulate even elementary physical systems accurately. Doesn't it take supercomputers to even accurately simulate even a few atoms? I think the biggest cultural "lie" in the last couple decades is "the Matrix". Since that movie, educated people including software engineers take for granted the fact that the universe can be simulated by computers. They write silly papers like "we are almost certainly living in a simulation". Granted, that argument is sound if you believe it's even possible to simulate the universe with a computer. But I actually take that as further evidence that it's NOT possible to simulate the universe with a computer. Anyway, I haven't thought about these things in a long time, but I would say that just because something is impossible on a Turing machine doesn't mean it's impossible in the universe!

nightsd01 9y ago
You can simulate a lot of atoms with a modern supercomputer. The only problem is just how many atoms there are even in a tiny grain of sand. However that doesn’t mean all hope is lost. You just have to get really clever - there is a lot of repeating patterns in a grain of sand - you don’t really need to simulate all or even most of it. The same holds true for most structures.
sobellian 9y ago
Wouldn't an incomputable physical process have serious implications beyond CS? How would a physicist even model such a thing? edit: I guess not, since all you need is access to the real numbers which is a strict superset of computable numbers, but this doesn't seem like an "interesting" violation of the SCT.
- chubot 9y ago
  What makes you think physics can model everything? That's the point. Math is FULL of functions that can be described -- have properties X and Y, which are useful to prove theorems -- which nobody has thought about how to compute. (Obviously, there are the ones related to incomputibility like the Godel function, but there are others too... I'd appreciate help from others here :) ) And it might not even be useful or interesting (for the purposes of mathematics) to compute them. Not all math is constructive. Likewise you can describe physical processes without computing them.
- daxfohl 9y ago
  If SCT is false then for example it may be possible for a quantum computer to use an uncountable set of inputs to compute in finite time whether an arbitrary turing machine will end. That said, you're right, if all that is required is real numbers, then hypothetically an analog computer is all that would be required. But in a truly quantum world where SCT holds, an "analog" computer is only a computable approximation. (Full disclosure: I guess....)
Udik 9y ago
> I don't have much justification, but I believe it's false. There is a lot more to the universe than computers. Computers cannot simulate even elementary physical systems accurately. Correct me if I'm wrong, but wouldn't a system that computes a non-recursive function be some sort of box where, given the same inputs, you invariably obtain the same outputs; however there is no way of finding any mathematical or algorithmic expression that could, in any finite amount of time, predict the same result? To find yourself in that situation, you need a physical process that is intrinsically non-computable; being unable to compute the sum of computable processes is not enough.
- wnkrshm 9y ago
  A problem that I see in simulating the universe (i.e. the sum of computable processes) is that in quantum mechanics, you can't simply isolate yourself from the system under scrutiny. I.e. to compute and predict the state of the universe a computer would have to take into account its own internal present and future state which was the aim to compute in the first place.

by chubot 9y ago

nightsd01 9y ago

You can simulate a lot of atoms with a modern supercomputer. The only problem is just how many atoms there are even in a tiny grain of sand. However that doesn’t mean all hope is lost. You just have to get really clever - there is a lot of repeating patterns in a grain of sand - you don’t really need to simulate all or even most of it. The same holds true for most structures.

sobellian 9y ago

Wouldn't an incomputable physical process have serious implications beyond CS? How would a physicist even model such a thing? edit: I guess not, since all you need is access to the real numbers which is a strict superset of computable numbers, but this doesn't seem like an "interesting" violation of the SCT.

chubot 9y ago
What makes you think physics can model everything? That's the point. Math is FULL of functions that can be described -- have properties X and Y, which are useful to prove theorems -- which nobody has thought about how to compute. (Obviously, there are the ones related to incomputibility like the Godel function, but there are others too... I'd appreciate help from others here :) ) And it might not even be useful or interesting (for the purposes of mathematics) to compute them. Not all math is constructive. Likewise you can describe physical processes without computing them.
daxfohl 9y ago
If SCT is false then for example it may be possible for a quantum computer to use an uncountable set of inputs to compute in finite time whether an arbitrary turing machine will end. That said, you're right, if all that is required is real numbers, then hypothetically an analog computer is all that would be required. But in a truly quantum world where SCT holds, an "analog" computer is only a computable approximation. (Full disclosure: I guess....)

Udik 9y ago

> I don't have much justification, but I believe it's false. There is a lot more to the universe than computers. Computers cannot simulate even elementary physical systems accurately. Correct me if I'm wrong, but wouldn't a system that computes a non-recursive function be some sort of box where, given the same inputs, you invariably obtain the same outputs; however there is no way of finding any mathematical or algorithmic expression that could, in any finite amount of time, predict the same result? To find yourself in that situation, you need a physical process that is intrinsically non-computable; being unable to compute the sum of computable processes is not enough.

wnkrshm 9y ago
A problem that I see in simulating the universe (i.e. the sum of computable processes) is that in quantum mechanics, you can't simply isolate yourself from the system under scrutiny. I.e. to compute and predict the state of the universe a computer would have to take into account its own internal present and future state which was the aim to compute in the first place.