Non-computable numbers in Physics

Question

It is known that there are real numbers that can't be calculated (non-computable numbers). Quite probably that some physical phenomena (it is possible still undetected) depend on this numbers. Whether means it, what we can't construct the theory of this phenomenon and-or (if probably to construct) to do predictions (i.e. to check up this theory in practice)?

Answer 1

When you think of a physical parameter which is "uncomputable", what precisely do you mean? For us to know that it is uncomputable, it has to arise somehow, on theoretical grounds, from e.g. a compu­tational process which is equivalent to the Halting Problem of theoretical computer science; so that we could not compute it from first principles. But any non-computable number can still be approximated, to arbitrary precision, by computable (even rational!) numbers: we've just stipulated that within the theory itself, those rational approximations are hard to come by and cannot be obtained systematically.

But there's another way of obtaining those approximations: experimentally! Ultimately what fixes constants is not theory, but observation. Even if you have a computable constant, if there's consistent experimental evidence against the theory, it's probably the theory which is wrong. Experiment then becomes a way of trying to fix the value of the uncomputable number. In order to prevent that, there would also have to be (at the least) theoretical grounds why any procedure for measuring it would also amount to solving an uncomputable problem: e.g. that any sequence of experimental set-ups, each revealing the mystery constant with higher precision, must either fail or would amount to a model of computations strictly stronger than Turing Machines.

Even if there was a theoretical justification for why the constant would be experimentally unmeasurable, that claim itself would have to be tested experimentally. What should we expect from experimentally unmeasurable parameters? Well, we don't mean that we can't measure it to any precision, just that there are real obstacles to measuring it to any substantial precision (like being stuck on "3.2" as an approximation to π, and unable to get a better result). If that were the case, attempts to measure to high precision should yield results which are routinely inconsistent with one another; and experiments to get high-precision values should be extraordinarily difficult to devise. (Though how you know that it's "hard enough", for a finite number of attempts to suspect the parameter might be uncomputable isn't an obviously answerable question.)

Edited to add: It's worth noting that — as Peter Shor noted in the comments — there may be other aspects of the physical theory which might prevent precision measurements of any purportedly uncomputable constants. For instance, in any detector which is meant to make precision measurements of energy, the time you allow for this measurement becomes crucial to the precision of the measurement, by the uncertainty principle. Even if by some masterstroke you manage to supercede quantum theory and bypass the uncertainty principle (which would be quite an unlikely theoretical breakthrough!), the new superceding theory may involve new uncertainty principles of its own, which would limit the precision to which you could measure constants. In that case, the precise-but-unmeasurable value would be about as good as any number of finite-precision rational approximations.

Finally — and in a similar vein as the remarks above regarding limits on measurements of constants imposed by uncertainty relations — in the case that the real world did operate on the basis of a constant that was neither theoretically nor experimentally determinable, it is quite likely that the uncomputability of the constant would not have any discernable effect. After all: if its specific value played an important role in physics, we would be able to measure it by observing physical phenomena! If the value of a constant is so inaccessible that its value cannot be pinned down by experiment, or even just passive cosmological observation, it can't really be significant. It certainly doesn't seem like it would be a scientific theory. Not if the physics depends on the constant in any more-or-less continuous way, anyway...

In short, unless you're interested in diving into joint philosophical underpinnings of physical science and computability theory, I wouldn't be too concerned about the possibility your raise.

Answer 2

Noncomputable numbers are defined by infinite sequences of approximations. One such number is the number whose n-th binary digit is 1 if n is the concatenated ASCII code of a halting computer program and zero elsewhere. If you knew this real number, you solve the halting problem.

Almost all the real numbers that arise in physics are approximations, valid for finite time measurements. You have to idealize to infinite times in a physical model. But you can ask, for our known physical laws, assuming we can do measurements for an infinite amount of time, can we generate an uncomputable number?

There is a simple example. Every random number is non-computable. So if you measure the spin of a quantum system in a nontrivial superposition, and write down 1 in the n-th binary digit if you see spin up, and 0 if you see spin down, you get a noncomputable real in the limit. This means that if quantum mechanics is exact, one can easily generate numbers which are not output by any Turing machine, but these types of real numbers are output by a probabilistic computer, a probabilistic Turing machine.

I suppose though that you are interested in generating actual non-trivial non-random non-computable numbers. If you build a computer, then in the limit of infinite running time, you can write down the Halting number, but you write it peicemeal as each program halts. The question is then whether there is a more efficient way to write down the halting number than waiting for each program to halt, using random numbers, or using quantum mechanics. I think that this is not known.

The basic definitions of mathematics regarding computability basically coincide with the classical physics notion of system behavior, since you can simulate a classical physics system, and you can build a computer out of the motion of classical particles. Quantum mechanics is different computationally, as demonstrated most conclusively by Peter Shor, who showed that a quantum computer can solve the integer factoring problem, while a classical computer cannot. But for the purposes of decidability questions, not efficiency questions, quantum computers are equivalent to classical probabilistic computers. The probabilistic computer can output a sequence of random digits, and so can generate a non-computable real, as above.

Answer 3

This would most likely violate the Church Turing Thesis, namely that everything that is computable is computable by a turing machine. If we could measure this parameter, we could construct a machine that could measure it to arbitrary precision, we would have hypercomputation, which we do not believe exists.

Answer 4

There's a difference between noncomputable and limit computable real numbers. A limit computable real number is a real number which can be expressed as the limit of a computable sequence of real or rational numbers. Limit computable quantities abound in physics, but noncomputable ones violate the Church-Turing hypothesis which in essence states the universe can be simulated on a computer.