3 ms·

"Computable" is a bit more strict than "logical and mathematical". We can define many perfectly consistent processes with perfectly consistent "observable value

"Computable" is a bit more strict than "logical and mathematical". We can define many perfectly consistent processes with perfectly consistent "observable values", which are inherently uncomputable (as in, there is no algorithm, even an inefficient one, that runs on Turing machines, capable of calculating the observable). Here is my favorite example: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant

h0l0cube 6y ago
I guess much of what I'm saying counts on hard determinism, and computation that isn't limited to what can be achieved with boolean logic. I'm talking out my ass here a little, but I picture quantum annealing as a form of computation where quantum physics effects are the actual execution engine.
- krastanov 6y ago
  Quantum effects are still things we can simulate on a Turing machine with a program that halts (just inefficiently slow given our current knowledge of complexity theory). Bringing in quantum effects does not make things uncomputable.
  - h0l0cube 6y ago
    I now see the distinction you're trying to make about computability, so does this revised claim satisfy you? > if all calculation of physical effects are found to be reducible to mathematical procedure with definite outcomes, then aren't real-world physical effects execution of computation? There's probably room for semantic disagreements here. It does seem that the definition is somewhat tautological, but I'd claim that that's because the two are equal.
    - krastanov 6y ago
      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

h0l0cube 6y ago

I guess much of what I'm saying counts on hard determinism, and computation that isn't limited to what can be achieved with boolean logic. I'm talking out my ass here a little, but I picture quantum annealing as a form of computation where quantum physics effects are the actual execution engine.

krastanov 6y ago
Quantum effects are still things we can simulate on a Turing machine with a program that halts (just inefficiently slow given our current knowledge of complexity theory). Bringing in quantum effects does not make things uncomputable.
- h0l0cube 6y ago
  I now see the distinction you're trying to make about computability, so does this revised claim satisfy you? > if all calculation of physical effects are found to be reducible to mathematical procedure with definite outcomes, then aren't real-world physical effects execution of computation? There's probably room for semantic disagreements here. It does seem that the definition is somewhat tautological, but I'd claim that that's because the two are equal.
  - krastanov 6y ago
    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