4 ms·

To an extent, but I think there is still a counter example that gets to why this is such a subtle distinction (computable vs "reducible to a mathematical proced

To an extent, but I think there is still a counter example that gets to why this is such a subtle distinction (computable vs "reducible to a mathematical procedure"). Consider an "analog" computer that is in principle noise-free (i.e. elementary operations like addition on this hardware are performed by adding up two analog quantities, e.g. voltages or currents, and these quantities are infinitely smooth, not discreticized/digital, and not disturbed by hardware imperfections and noise). I can create a model of such a device in theory and if I use only the axioms of classical physics (which we now know are wrong), then such a device will be capable of computing and representing numbers that can not be expressed by a Turing machine (i.e. it would be not just faster than a Turing machine or a quantum computer, it will be capable of things that a Turing machine can not ever do). This is a device that one can imagine existing, and to quote you it is "reducible to mathematical procedure with definite outcomes". It just happens to be a mathematical procedure we find to be rather unreasonable for our universe (because of unavoidable classical thermal noise and non-classical quantum effects that cause discretization). Some physicists and computer scientists (me included) like to take this as a starting point, as a reason for why certain theories of physics are probably wrong. I personally find this to be a very elegant, powerful, and subtle approach, up there with Noether's theorem or the second law of thermodynamics. "A theory of physics can not be true if it permits the construction of a computing device that can solve the halting problem" seems pretty much on par with "A theory of physics can not be true if it disobeys conservation laws / causality / locality / entropy considerations". All of this with the caveat that one should not be dogmatic about these vague statements, rather just take them as a general guideline.

h0l0cube 6y ago
I agree with what you're saying (as much as one can as an outsider). But, going back to the original claim, could you say the physical systems that bind our particular universe could be classed as executed 'computation', given that they likely could be computed by a Turing machine? Side-question: is computation, by definition, strictly limited to that achievable by a Turing machine?
- krastanov 6y ago
  I do not think we have an answer to the first question. At the end it does not really matter whether our universe runs on an actual computer or is simply equivalent to a computable process (as opposed to an uncomputable one). However, for aesthetic reasons some scientists guide their work in theoretical physics by studying specifically only physical laws that are, in principle, computable. Said in other words, some scientist take the "Extended Church-Turing Thesis"[1] as an axiom of physics and work from there. To the side question, yes, that is a typical definition of "computable" (usually what a CS theorist means by the word). The reason we believe it is a useful practical definition is that (1) such a definition ends up equivalent to a number of other interesting definitions and such a net of equivalences usually ends up being interesting and empowering (2) Turing machines form a "universal" modality of computation because we have proofs that they can "efficiently" simulate other theoretical models of computation (3) We simply do not know of other modalities of computation that can exist in our universe (which is a bit of a circular statement in the context of this conversation) (4) It simply seems to be a useful formalism that enabled us to prove a ton of useful results, so even if it was not as elegant as I claim, it definitely ended up being a productive and practical way of thinking. Side note: Quantum computing muddles the water a bit in terms of what is efficiently computable, but if something is not computable for a Turing machine it is still not computable for a quantum computer (however there are a few things that seem to take exponential time on a Turing machine while taking only polynomial time on quantum computer). [1]: https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
  - h0l0cube 6y ago
    Thanks for your long-form reply. Super informative and entertaining. For #1, wasn't speaking of the 'universe as simulation' hypothesis specifically, I think an assertion either way is indefensible. It was more about unpacking semantics, i.e., what is the most reductive form of a computation? Does there need to even be an operator that seeks to know an answer? Is computation something that only exists in human context, or can it simply be the unfolding consequences of the 'seed' of the universe? Just rumination on abstract inconsequential ideas :) #2. I'm familiar with some of the nomenclature is regards to 'computing' complexity, and my question, in retrospect, seems a little silly. Computation is computation. I still only have a lay understanding -- as much as I need to know for perf and the differences between algorithms -- and I'll have a look at that paper and hopefully understand the subject a little deeper. Thanks again.

h0l0cube 6y ago

I agree with what you're saying (as much as one can as an outsider). But, going back to the original claim, could you say the physical systems that bind our particular universe could be classed as executed 'computation', given that they likely could be computed by a Turing machine? Side-question: is computation, by definition, strictly limited to that achievable by a Turing machine?

krastanov 6y ago
I do not think we have an answer to the first question. At the end it does not really matter whether our universe runs on an actual computer or is simply equivalent to a computable process (as opposed to an uncomputable one). However, for aesthetic reasons some scientists guide their work in theoretical physics by studying specifically only physical laws that are, in principle, computable. Said in other words, some scientist take the "Extended Church-Turing Thesis"[1] as an axiom of physics and work from there. To the side question, yes, that is a typical definition of "computable" (usually what a CS theorist means by the word). The reason we believe it is a useful practical definition is that (1) such a definition ends up equivalent to a number of other interesting definitions and such a net of equivalences usually ends up being interesting and empowering (2) Turing machines form a "universal" modality of computation because we have proofs that they can "efficiently" simulate other theoretical models of computation (3) We simply do not know of other modalities of computation that can exist in our universe (which is a bit of a circular statement in the context of this conversation) (4) It simply seems to be a useful formalism that enabled us to prove a ton of useful results, so even if it was not as elegant as I claim, it definitely ended up being a productive and practical way of thinking. Side note: Quantum computing muddles the water a bit in terms of what is efficiently computable, but if something is not computable for a Turing machine it is still not computable for a quantum computer (however there are a few things that seem to take exponential time on a Turing machine while taking only polynomial time on quantum computer). [1]: https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
- h0l0cube 6y ago
  Thanks for your long-form reply. Super informative and entertaining. For #1, wasn't speaking of the 'universe as simulation' hypothesis specifically, I think an assertion either way is indefensible. It was more about unpacking semantics, i.e., what is the most reductive form of a computation? Does there need to even be an operator that seeks to know an answer? Is computation something that only exists in human context, or can it simply be the unfolding consequences of the 'seed' of the universe? Just rumination on abstract inconsequential ideas :) #2. I'm familiar with some of the nomenclature is regards to 'computing' complexity, and my question, in retrospect, seems a little silly. Computation is computation. I still only have a lay understanding -- as much as I need to know for perf and the differences between algorithms -- and I'll have a look at that paper and hopefully understand the subject a little deeper. Thanks again.