real count

May 2013
94
10
I've heard that the reals are uncountably infinite.
But I've also heard that you can enumerate over Turing machines.
If that's the case, shouldn't you be able to write a program for every number?
I've heard of non-computable numbers, but I honestly don't think that's possible.
They give the probability of a random program compiling as an example,
but couldn't you write a program that generates random programs, and sees whether it compiles?
 
Aug 2012
2,464
761
I've heard that the reals are uncountably infinite.
Yes. Just means that there's no bijection between the naturals and the reals.

But I've also heard that you can enumerate over Turing machines.
Yes. All the TMs of length 1 followed by the ones of length 2 etc., and within each group, lexicographic (alphabetical) order. Note that there are only countably many TMs, assuming the alphabet is at most countably infinite. There are countably many TMs of length 1, countably many of length 2, etc.; and a countable union of countable sets is countable.

If that's the case, shouldn't you be able to write a program for every number?
No. In fact that's the existence proof for uncountable numbers. There are uncountably many reals but only countably many TMs.

I've heard of non-computable numbers, but I honestly don't think that's possible.
You just gave the proof that they exist!

They give the probability of a random program compiling as an example,
No that sounds like a misunderstanding. You might be thinking about Chaitin's omega, which gives the probability that a random TM halts. But compilation isn't a concept in TM theory at all. Compilation is only relevant to real-world languages and doesn't affect computability at all.

Chaitin's constant - Wikipedia


but couldn't you write a program that generates random programs
That's what entry-level programmers are for!

And seriously, the subject of whether it's possible, even in theory, for a program to do anything randomly is a deep question of physics and philosophy, far out of scope in this conversation.

But remember a TM is completely deterministic. TMs don't have access to sources of randomness at all. Any TM must be deterministic. At best a TM could generate a pseudorandom number, which is in fact a deterministic process.

and sees whether it compiles?
Don't know where you got this idea about compilation. That's way off the mark.

Can you clarify some of your ideas?

tl;dr: Uncountably many reals; countably many TMs over a countable alphabet; therefore uncomputable reals exist. There aren't enough TMs to compute all the reals.
 
Last edited:
  • Like
Reactions: 2 people
May 2013
94
10
Okay, so it should be the probability that a TM halts rather than compiles.
Technically you're right about random number generation, but there are pseudo random number generators with over 10^80 length cycles, ISAAC for example.
That should be random enough to get a fair gauge whether a TM is random.
There's a quote, "if you go large enough, the primes seem to crop up randomly, but we're not quite sure what random means."
So, for example, you could write a TM that goes through numbers one at a time starting from some large value, and whether or not it's prime could be used to generate randomness.

My query is, can you definitively come up with a number that is non-computable?
Can you give me an example?
 
Aug 2012
2,464
761
My query is, can you definitively come up with a number that is non-computable?
Can you give me an example?
It's Chaitin's Omega again.

Chaitin's constant - Wikipedia

If Omega were computable, you could use it to solve the Halting problem, which Turing proved impossible.

Technically, your right about random number generation, but there are pseudo random number generators with over 10^80 length cycles, ISAAC for example.
That should be random enough to get a fair gauge whether a TM is random.
What do you mean by a random TM? Every TM is strictly deterministic. There are in fact nondeterministic automata, but they have the same computational power as deterministic ones. [They may be more efficient though].

Checking 10^80 cycles isn't enough to determine if a TM halts. And pseudorandom generators are deterministic.
 
Last edited:
Jun 2014
650
54
USA
Okay, so it should be the probability that a TM halts rather than compiles.
Technically you're right about random number generation, but there are pseudo random number generators with over 10^80 length cycles, ISAAC for example.
That should be random enough to get a fair gauge whether a TM is random.
There's a quote, "if you go large enough, the primes seem to crop up randomly, but we're not quite sure what random means."
So, for example, you could write a TM that goes through numbers one at a time starting from some large value, and whether or not it's prime could be used to generate randomness.

My query is, can you definitively come up with a number that is non-computable?
Can you give me an example?
The computable reals are enumerable as are the set of computable infinite binary sequences. I choose to use binary sequences because there are two representations for each dyadic rational in binary but there is only one representation per infinite binary sequence.

To show the existence of some non-computable infinite binary sequence, just consider a listing of the computable binary sequences (note that such a listing generally requires the axiom schema of specification or some choice I believe because the halting problem essentially ensures that there is no explicit function for generating the listing despite the listing absolutely being countable.):

$t_1 = t_{1,1}, t_{1,2}, t_{1,3}, ...$
$t_2 = t_{2,1}, t_{2,2}, t_{2,3}, ...$
$t_3 = t_{3,1}, t_{3,2}, t_{3,3}, ...$
.
.
.
Using Cantor's diagonal method, create a new infinite binary sequence that isn't in the list. To do this, let $s(t_{i,j}) = 0$ if $t_{i,j} = 1$ and let $s(t_{i,j}) = 1$ if $t_{i,j} = 0$:

$a = s(t_{1,1}), s(t_{2,2}), s(t_{3,3}), ...$

We now know that $a$ is different than every member of the list. If the list includes all computable infinite binary sequences, then $a$ must further be a non-computable infinite binary sequence.

Hope that helps!
 
Last edited by a moderator:
May 2013
94
10
Yes. All the TMs of length 1 followed by the ones of length 2 etc; and within each group, lexicographic (alphabetical) order. Note that there are only countably many TMs, assuming the alphabet is at most countably infinite. There are countably many TMs of length 1, countably many of length 2, etc.; and a countable union of countable sets is countable.
Couldn't the same thing be said of real numbers?
There are a countable number of reals that are 1 digit long, 2 digit long, 3 digit long, etc.
 
Oct 2009
927
351
Couldn't the same thing be said of real numbers?
There are a countable number of reals that are 1 digit long, 2 digit long, 3 digit long, etc.
Correct. But there are also real numbers with infinite digits, like pi. You don't have Turing machines of infinite length.
 
May 2013
94
10
But there are also real numbers with infinite digits, like pi. You don't have Turing machines of infinite length.
True, but you have infinitely many Turing machines that can produce infinitely many numbers of infinite length.
For example, there are Turing machines that can calculate pi and e with the same machine to the desired accuracy.
 
Last edited by a moderator:
Aug 2012
2,464
761
True, but you have infinitely many Turing machines that can produce infinitely many numbers of infinite length.
For example, there are Turing machines that can calculate pi and e with the same machine to the desired accuracy.
True. But there are at most countably many TMs. Say each one produces (the digits of) two computable reals. That won't help because two times countable is countable.

Ok what if each TM cranks out a million computable reals, a zillion, a googleplex of them? Still doesn't help, finite times countable is countable. (All proofs are easily found on the web or any book on elementary set theory).

So you go, ok, how about if each TM cranks out countably infinitely many distinct computable reals? Well then it STILL won't help, because a countable union of countable sets is countable.

The only way you can make your idea work is to stipulate that at least one TM can generate uncountably many noncomputable reals. Then you don't even need the other TMs! One will do, if it can generate an uncountable infinity of outputs.

Now of course no TM can possibly do that. Regardless, the burden would be on you to argue that one can.
 
Last edited by a moderator:
Jun 2014
650
54
USA
True, but you have infinitely many Turing machines that can produce infinitely many numbers of infinite length.
There are only countably many Turing machines though (do you agree?), which is why we can assert the set of computable infinite binary sequences is at most countable (do you also agree?). I used a hypothetical listing of the computable infinite binary sequences above to create an infinite binary sequence that was not computable. Did that make sense?

For the sake of argument, assume the list of computable infinite binary sequences is itself computable (again, it's not due the halting problem generally). We would then be able to take the diagonal that I showed you above and it would also be computable. The diagonal cannot be computable because it isn't in the list, however, so we have a contradiction. We know then that our assumption, that the list of computable infinite binary sequences was computable, was false.
 
Last edited by a moderator: