The computable universe hypothesis, states that every operation and phenomenon in the universe is computable. So if you can describe all the phenomena in state s1 of some part of the universe (or of the whole universe), then you can compute the physical operations in any state si that is a successor of s1.
An equivalent hypothesis is that every set of physical operations can be simulated by a Turing machine or an automaton. This means that there is a Turing or some other computational machine that will accept as input the data that describe these operations and will output the result of them and then it will halt. The two hypotheses are equivalent as the simulation of every operation by a Turing machine implies the computability of the transition from state s1 to any state si.
These hypotheses also support the idea that the universe is deterministic. The transition from s1 to si is computable and as a result predictable which makes it deterministic.
There are many papers and textbooks that propose theories that are based on these hypotheses, there are also many that oppose such ideas. My opinion is against the idea of a computable universe, the reasons for this are: randomness, incompleteness and uncomputability.
The existence of randomness in physical processes remains a debate among scientists. Einstein rejected it, as he believed that universe is deterministic and stating that "God does not play dishes"; a phrase that marked the debate. The truth is that there are many indications that some physical operations must be random.
Any not trivial system of logic is incomplete. This is a very simplified description of the incompleteness theorem stated and proven by Kurt Godel which is one the most important theorems in science.
Any system physical or not that operates under certain laws may be efficiently described by mathematics and more specifically by some system of mathematical logic using propositions and axioms. If the system of logic is not trivial (is not very simple) then there are true statements in it that may not be proven as true; the system is incomplete. This results that there are phenomena that may not be computed by mathematics.
This lecture of Hawking approaches incompleteness theorem from a physicist perspective reaching the same conclusions.
The issue that we face is that in order to compute some mathematical object O we need to use or to build some proper mathematical structure. But no matter how this structure will be it will always be incomplete, so a part of O will not be able to be proven using our mathematics.
The theoretical background of uncomputability in Computer Science is related to Godel’s incompleteness theorem and states that there are instances of computational problems that may not be computed by a machine or a human. Computational procedures may be simulated by Turing Machines that perform them and then halt, so we usually state that a problem P is uncomputable if there is not a Turing Machine that may compute all the instances of P and then halt. Equivalently, if you input some data in a Turing Machine you may not know if it will halt or not.
The foundation for this was set by Alan Turing before the first general purpose computer was ever built.
Its affect in programming is something that we experience every day. No matter how hard have you worked on a piece of software you can never be sure that it will work as expected.
A parallelism in physics that I have thought is included in the question
An equivalent hypothesis is that every set of physical operations can be simulated by a Turing machine or an automaton. This means that there is a Turing or some other computational machine that will accept as input the data that describe these operations and will output the result of them and then it will halt. The two hypotheses are equivalent as the simulation of every operation by a Turing machine implies the computability of the transition from state s1 to any state si.
These hypotheses also support the idea that the universe is deterministic. The transition from s1 to si is computable and as a result predictable which makes it deterministic.
There are many papers and textbooks that propose theories that are based on these hypotheses, there are also many that oppose such ideas. My opinion is against the idea of a computable universe, the reasons for this are: randomness, incompleteness and uncomputability.
Randomness
The existence of randomness in physical processes remains a debate among scientists. Einstein rejected it, as he believed that universe is deterministic and stating that "God does not play dishes"; a phrase that marked the debate. The truth is that there are many indications that some physical operations must be random.
Steven Hawking provides some very convincing arguments in one of his lectures. According to Hawking the way the universe evolves seems to be not deterministic, moreover the existence of extreme objects in it like the black holes and the Uncertainty Principle makes accurate computations and predictions impossible. Although in computer science we can only use pseudo-random operations in order to approach true randomness, in other fields true randomness seems to be present. Quantum mechanics build probabilistic models in order to study quantum phenomena that are believed to evolve truly randomly.
Incompleteness
Any not trivial system of logic is incomplete. This is a very simplified description of the incompleteness theorem stated and proven by Kurt Godel which is one the most important theorems in science.
Any system physical or not that operates under certain laws may be efficiently described by mathematics and more specifically by some system of mathematical logic using propositions and axioms. If the system of logic is not trivial (is not very simple) then there are true statements in it that may not be proven as true; the system is incomplete. This results that there are phenomena that may not be computed by mathematics.
This lecture of Hawking approaches incompleteness theorem from a physicist perspective reaching the same conclusions.
The issue that we face is that in order to compute some mathematical object O we need to use or to build some proper mathematical structure. But no matter how this structure will be it will always be incomplete, so a part of O will not be able to be proven using our mathematics.
Uncomputability
The theoretical background of uncomputability in Computer Science is related to Godel’s incompleteness theorem and states that there are instances of computational problems that may not be computed by a machine or a human. Computational procedures may be simulated by Turing Machines that perform them and then halt, so we usually state that a problem P is uncomputable if there is not a Turing Machine that may compute all the instances of P and then halt. Equivalently, if you input some data in a Turing Machine you may not know if it will halt or not.
The foundation for this was set by Alan Turing before the first general purpose computer was ever built.
Its affect in programming is something that we experience every day. No matter how hard have you worked on a piece of software you can never be sure that it will work as expected.
A parallelism in physics that I have thought is included in the question
“How can you be sure that for operation H there is a Turing Machine that will halt on input of the description of H?”
The above arguments may seem to be weak but there is a stronger one for which I talked about in a previous post.
Causation (or else causality) refers to the cause-effect relation that may exist between two events or phenomena. The causal inference problem regards the determination of causation between events.
In my previous post I present a proof on which Causal Inference is logically and computationally undecidable. Relations among phenomena and physical processes are important factors in the structure of the universe. The Causal Inference undecidability results that there are physical phenomena for which we may not decide or compute if they are related to each other or not. This makes a part of the universe uncomputable and unexplained using logical arguments.
The above arguments may seem to be weak but there is a stronger one for which I talked about in a previous post.
Causation (or else causality) refers to the cause-effect relation that may exist between two events or phenomena. The causal inference problem regards the determination of causation between events.
In my previous post I present a proof on which Causal Inference is logically and computationally undecidable. Relations among phenomena and physical processes are important factors in the structure of the universe. The Causal Inference undecidability results that there are physical phenomena for which we may not decide or compute if they are related to each other or not. This makes a part of the universe uncomputable and unexplained using logical arguments.
