I once thought (tweeted) that physics is 'explaining the explainable (computable) part of the universe' as the rest can be seen as random. Now I'm not sure about this anymore.

The simplest example of non-computable physics I could think of is a realworld super-Turing machine, i.e. a physical law that states that certain physical essembles, which are parametrized by finite strings, behave in a certain experiment in correlation with the halting property of the program described in the string. In a sense, there is similarity to computable physics, as we can start an infinite experiment using infinite ressources, where we ask the system for the halting state of every problem while simultaneously running the programs and see if they halt. If the theory holds true, we would expect to see an infinite number of confirmations (programs halting where the experiment says they would) and no refutation.

But as we can never confirm the law in the cases of programs which don't halt and no proof exists for their non-halting, we could also assume that the output for those programs is random.

Would that turn our theory into a computable (but non-deterministic) one? What frameworks exist to evaluate those questions? How would Solomonoff induction treat a realworld super-Turing machine?

  • Do you mean by "our theory" our theory of physics, or our theory of computation? – kutschkem Apr 15 '20 at 14:23
  • I mean the theory that this physica process descroves a super-Turing machine. – fweth Apr 15 '20 at 15:05

I once thought (tweeted) that physics is 'explaining the explainable (computable) part of the universe' as the rest can be seen as random. Now I'm not sure about this anymore.

Yes, because it is wrong. There are real processes (particle decay, quantum stuff) that are inherently not deterministic, but we can still describe the statistics of these processes. That is also physics. There are laws, they are just statistical.

If you wanted to model those statistics in a non-halting turing machine, then you need to define it in a way that gives sensible statistics. Just saying "random" is not doing justice with regard to what you can still say about the randomness of a process.

  • Isn't the Schrödinger equation perfectly deterministic? It's measurement that's uncertain, not the universe itself. Is my understanding wrong? – user4894 Apr 15 '20 at 21:41
  • Yes, as far as current theories are concerned that understanding is wrong! Read up on Bell's theorem and Heisenberg uncertainty. Also I think double-slit experiment would be hard to explain deterministically. I am not a physicist though, but over on physics.SE there are lots of questions around the subject, and lots of people who can answer these kinds of questions. – kutschkem Apr 16 '20 at 6:31
  • Heisenberg uncertainty is about measurement, so I can't help feeling you confirmed rather than refuted my point. Regarding your belief that I need to go to another site, YOU are the one making what I believe to be an inaccurate claim that you can't support with evidence. Heisenberg is an epistemological limitation, not an ontological one. Which is exactly my point. – user4894 Apr 16 '20 at 7:28
  • @user4894 Again, I am computer scientist and not physicist, so I am more qualified to talk about the turing machine part of the question than the physics part. My understanding is: Heisenberg uncertainty tells us something about intrinsic uncertainty in measurements, where measurements really means any kind of particle interaction. So no matter whether the wavefunction develops deterministically in between interaction, as soon as interaction happens a statistical process is happening. – kutschkem Apr 16 '20 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.