4

The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine.

Let us create a machine that, for example, outputs the digits of the fine-structure constant. The Fine-structure constant is measurable, and does not depend on the units of measure.

This would seem to imply, via the physical Church Turing thesis, that the fine-structure constant is computable by a Turing machine! This seems unlikely, since only countable many numbers have that property.

Christopher King
  • 481
  • 2
  • 13
  • 3
    I challenge you to devise a physically possible experiment that gives me the 1000th digit of the fine structure constant. (We don't even know the 12th digit.) Why are you assuming that it's physically computable? – Peter Shor Mar 21 '18 at 01:56
  • 3
    "This seems unlikely, since only countable many numbers have that property." I don't understand this reasoning. Only finitely many numbers have their own Wikipedia page, and I'm willing to bet the overwhelming majority of them are Turing-computable. Do we have reason to believe the Fine structure constant was randomly sampled in a particular way? – Yonatan N Mar 21 '18 at 02:07

2 Answers2

10

You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact value of the fine-structure constant, it cannot predict the outcome of an arbitrary experiment.

I don't believe (b) is the case. Generally, the way that constants are measured is by measuring the ratios of some physical quantity that we can measure directly, like time, and using this ratio to compute the constant. The smallest unit of time that exists is believed to be on the order of the Planck time, which is $5.39 \times 10^{ −44}$ s. The age of the universe is $4.32 \times 10^{17}$ s. Thus, if we constrain our experiment to take no more time than the age of the universe, we can measure time to at most 61 digits of accuracy, so this is the limit of accuracy for the fine structure constant. This constant can easily be hard-coded in a Turing machine.

Is (a) the case? That may be a matter for philosophers. If changing the 100th digit of a physical constant has absolutely no impact on the dynamics of the universe, does that constant really have an infinite nuber of decimal places?

UPDATE: The best you could hope for (and I don't believe physicists currently know how to do this) is an experiment that measured $k$ digits of the fine structure constant in time $2^k$. In this case, the strongest version of the physical Church-Turing thesis would imply that the fine structure constant is computable. But you would be able to simulate an experiment that took $2^k$ years to carry out by using an oracle that gave you $O(k)$ bits.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 2
    "Thus, if we constrain our experiment to take no more time than the age of the universe" doesn't that make the physical turing thesis trivial? – Christopher King Mar 21 '18 at 21:43
8

Yes, if you somehow had a scheme that allows to compute/measure more and more digits of the fine-structure constant $\alpha$ then $\alpha$ should be Turing computable according to the Church-Turing thesis.

But in practice, $\alpha$ is based on some measured quantities, we have no Theory of Everything (TOE) for physics, and it is not clear that $\alpha$ is a constant with infinite precision the way that $\pi$ is.

Perhaps in an eventual TOE, $\alpha$ turns out to be a computable or noncomputable number. Or perhaps it turns to only be a constant in some approximate sense.

Jose Felix Costa has many papers about the relationship between measurable and computable numbers.

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40