Hacker News Reader

Comment by krastanov | Hacker News Reader

"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

View on HN

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.

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.

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.

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.

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?

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

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.

I think most of my colleagues that care about such distinctions would say that in the most reductive form one does not need an operator or a goal for the computation. This is the typical assumption I would have when discussing this formalization of the laws of physics.

By the way, if you are fan of SciFi, Greg Egan has very fun stories that play with these ideas (nothing rigorous or seriously scientific, but certainly fun).

Reply on news.ycombinator.com