(continued from previous post)
Let H0 be the hypothesis: `the real world is non-computable’ (popularly speaking, see previous post), and H1 be PCTT+ (also see the previous post).
For comparison we introduce the hypothesis H2: `the real world produces only rational (real) numbers’.
H2 is assumed to have been the original world view of ancient Greek mathematicians (Pythagoreans), before their discovery that is irrational (which is `rumoured’ to have caused a shock but I cannot find a reliable historical reference for this).
The rational numbers in have Lebesgue measure , so we can start constructing such that has Lebesgue measure less than , and such that contains all rational numbers in .
If we then take our coin-flip-randomly produced , I personally don’t think that we will encounter an for which we see that contains .
This opinion is supported by the fact that we can easily construct a non-rational number…at least in theory. Take for instance , the basis of the natural logarithm, which equals . We can in fact construct in such a way that does not contain , and assume this to be the case here.
On the one hand, this does not depend on infinity, since we can simply look at approximations of . We construct such that for any the binary approximation to is positively apart from . On the other hand, any finite approximation to is still rational…and so we can only construct as an irrational number in the sense described above.
With regard to the existence of non-computable reals, the situation in my humble opinion is very different. We cannot construct a non-computable real, as result of the Church-Turing Thesis (which I have no reason to doubt). Any construction of a real which we recognize as such will consist of a finite set of construction instructions…in other words a Turing machine.
So to make a reasonable case for the existence of non-computable reals, we are forced to turn to Nature. In the previous post, we flipped our coin to produce a random in . We argued that finding for which contains would force us to reject the hypothesis H0 (`the real world is non-computable’).
So what result in this coin-tossing experiment could force us to reject H1, the strong physical Church-Turing thesis (PCTT+, `the universe is a computer’)?
To be able to reject H1 in the scientific hypothesis-testing way, we should first assume H1. [This might pose a fundamental problem, because if we really assume H1, then our perception of probability might change, and we might have to revise the standard scientific hypothesis-testing way which seems to be silently based on H0. But we will for the moment assume that the scientific method itself needs no amendment under H1.]
Under H1 has to fall in some . Failure to do so even if we let grow very large, might indicate H1 is false. For scientific proof we should avail of some number such that (under H1) the probability that is not in is less than .
This reverse probability has had me puzzled for some time, and sent me on the quest for a probability distribution on the natural numbers. In the thread `drawing a natural number at random’ I argued that some indication could be taken from Benford's law, and for discrete cases from Zipf’s law. Anyway, very tentatively, the result of this thread was to consider relative chances only. If for we denote the relative Benford chance of drawing vs. drawing by: , then we find that . The relative Zipf chance of drawing vs. drawing would be given by .
In both cases, the relevant density function is . The important feature of this distribution is twofold:
1) The smaller natural numbers are heavily favoured over the larger. (`Low entropy’).
2) There is no such that even the relative probability of drawing larger than becomes less than . (Because tends to infinity).
Fools rush in where angels fear to tread. I know, and so let me fall squarely in the first category. Yet this train of thought might provoke some smarter people to come up with better answers, so I will just continue. I do not believe these relative chances can simply be applied here, there are too many unknowns and assumptions. But it cannot do harm to try and get some feel for the reverse probability needed to disprove H1.
For this tentative argument then, disregarding some technical coding issues, we consider (under H1) our coin-flip random to equal some computable computed by a Turing machine with random number , drawn from some extremely large urn with low entropy (favouring the smaller natural numbers).
Even with this favouring of the smaller natural numbers, still we cannot begin to indicate such that (under H1) the probability that is not in is less than . Perhaps if we would know the size of the urn (which in this case would seem to be the universe itself) we could say something more definite on . But all things considered, it seems to me that could easily be astronomically large, far larger than our limited computational resources can ever handle.
In other words: all bets are off, to disprove H1.
And so also, if H1 is true, it could very well take our coin-flip experiment astronomically long to find this out.
But I still think the experiment worthwhile to perform.