Choose any arbitrarily small segment of the real line, all those numbers will be uncomputable almost everywhere
While there are many (often equivalent) definitions of what a computable number are. And easy to grasp informal explanation is that a number is computable if you can write a function/algorithm f(n) such that it returns the n-th digit in a finite amount of time.
For Pi as an example: f(3) = 4 (from 3.14)
Almost all applies to the elements of an uncountable set except for countable subset.
As the reals have a cardinality of 2^aleph_0 or aleph_1 (uncountable), but the Natural Numbers, Integers and Rationals are aleph_0 (countable), you have to find some many to one reduction.
Chaitin's constant is uncomputable because it is effectively random, and no random problem is decidable, or (co)recursively enumerable)
It gets mapped to the halting problem, because that is the canonical example but you could use the system identification problem, symbol-grounding problem, open frame problem etc....
But to answer your question, in the real interval [0,1], the computable numbers have measure zero, and the uncomputable numbers have measure one.
So right there is an uncountable infinity of non-computable numbers.
I should've been more clear. The Reals are very unsettling because there are supposed to be so many of them, but nobody has used, named, or described more than a few which aren't computable. They are angels dancing on a pin which we've never seen and probably don't need for any of applied mathematics.
No, all the numbers most anyone actually uses are computable, and it'd say something weird about determinism if they weren't. The word "need" was carrying some weight, as in necessary vs sufficient.
It's not about individual numbers. Most applied maths fields (including physics) use the real numbers and the properties of real numbers as a complete field are implicitly assumed all the time (e.g. for differential equations). It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable.
If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing. That's probably possible although I doubt that it would be very elegant. But it's simply not what people use.
> If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing.
That wasn't my original intent, but I think it's a legitimate stance. The Reals are bizarre (Banak Tarski, etc...), and we practically never use the non-computable ones.
> It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable.
Lol, who else WOULD care? :-)
> That's probably possible although I doubt that it would be very elegant.
That's an aesthetic judgment. Someone else might argue that sticking to the numbers we actually use and can calculate is simpler/cleaner/more elegant/whatever. And besides, I'm guessing you could replace ℝ with T (for Turing) and most of the proofs would go just fine.
(Although the Computables have plenty of weirdness to them too...)
> And besides, I'm guessing you could replace ℝ with T (for Turing) and most of the proofs would go just fine.
This is wrong. LUB doesn't hold for the computable reals, and this means that a lot of classical proofs straight up don't work anymore.
That's not to say you can't build a different kind of real analysis built only on the computable reals, some mathematicians have tried to do similar things in the past, but it's going to be a different framework with not exactly the same theorems and not exactly the same proofs; for example, there are no discontinuous functions anymore.
Yeah, I'm sure there are some holes (poor attempt at a pun), but you already know you can get arbitrarily close to whatever bound with rationals, much less computables, so it seems like someone better educated than me could shore that up.
Anyways, the computables have unfortunate properties too (not knowing if you'll eventually need to carry for addition, or when to stop testing for equality), so I'm left wondering if some genius in the future will come up with a new way to build the numbers which are more satisfying.
These are distinct senses of "random". Pi is conjectured (but not proven) to be a so-called normal number, which means that n-grams have uniform frequencies, so if you slide a window of size n over the digits, then every sequence of n digits will come up with equal frequency in the limit.
Chaitin's omega is "random" in a stronger sense. There is no finite algorithm that can produce the digits. There's no compact, finite representation from which you could "unpack" those digits. The digits are what they are, the best way to represent them is simply to list them.
Pi's digits are very "regular", but the pattern is not about repetitions in digits or skewed frequencies of certain digit sequences but that the digits follow from simple rules. A short program can generate those digits to arbitrary length. So in some sense they have redundancy, a kind of pattern to them.
π is a transcendental number meaning that it is not algebraic
It is NOT an algorithmically random sequence.
Chatlin's halting probability is normal, transcendental, and non-computable.
https://arxiv.org/pdf/0904.1149
> Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach., vol. 22, pp. 329–340,
1975] introduced Ω number as a concrete example of random real.
Being non-algebraic is not the same as being algorithmicly random in the formal sense.
