real count

May 2013
94
10
i mean yes technically its deterministic, but i bet you can't predict the hundredth value before hand without doing the math.
 
Aug 2012
2,464
761
i mean yes technically its deterministic, but i bet you can't predict the hundredth value before hand without doing the math.
How does that make a difference to your argument? You have a deterministic algorithm that claims to compute the digits of Chaitin's Omega. That contradicts a result established in 1936. That's 83 years ago. Nobody's found a flaw in Turing's argument in all this time. Are you saying Turing's wrong? Or that Chaitin's wrong? Or what exactly?
 
May 2013
94
10
my argument is: you can a) generate pseudo random turing machines b) estimate whether they halt, and c) use that data to determine an approximate value for chaitin's omega.
i admit, it's not perfect, but it should be close enough for most purposes.
 
Aug 2012
2,464
761
my argument is: you can a) generate pseudo random turing machines b) estimate whether they halt, and c) use that data to determine an approximate value for chaitin's omega.
i admit, it's not perfect, but it should be close enough for most purposes.
Ok first, what is a pseudo-random TM? There is such a thing as a nondeterministic TM in which at each state, all possible paths are taken. It's already been proven that nondeterministic TMs have no more computational power than deterministic ones. That is, the set of functions that each class of machine computes is exactly the same.

Now it MAY be the case, though even this is not yet proven, that a nondeterministic TM might be asymptotically faster than a deterministic TM in the sense of the famous Big-O notation, which is used all over computer science but was originally invented by mathematicians.


So there are two different subjects: computability theory, which says whether a given task can be computed; and complexity theory, which is about how efficiently a given computation scales with input size. Nondeterministic TMs have the exact same computational power as deterministic TMs; though it's believed but not proven (as far as I know, I might be fuzzy here) that nondeterministic TMs can be more efficient on some problems.

The point being that even if you had a true random number generator -- bearing in mind that it's an open question as to whether such a thing even exists in our universe -- it wouldn't help your argument.

And your argument is even weaker, because you are using the Python random() function, which is known to be deterministic. You'd be better off claiming that you have some function reallyReallyRandomNumber() that returns the low order bit of the femtosecond timestamp of the next neutrino to pass through a special detector located high in the Himalayan mountains and tended night and day by Buddhist monks with doctorates in physics -- AND that this is TRULY random in the sense that it was not already determined at the moment of the Big Bang but somehow (how, exactly??) decided at the last minute when the neutrino made up its mind. I hope you see that I've made a philosophical point, which is that belief in true randomness entails belief in panpsychism. This is actually a theorem of physics. If we have free will, then (subject to some assumptions) so must elementary particles.


To sum up, if you had a true random number generator, which may or may not exist; your argument would still be wrong, because you would not gain any computational power over not having one at all.

Disclaimer: Any corrections from actual computer scientists greatly appreciated. This is all stuff I've picked up the past few years reading Scott Aaronson's blog.
 
Last edited:
May 2013
94
10
a pseudo random turing machine for example python's random function is a turing machine that can generate a sequence that looks random.
in general for binary RNG, you have rougjy 50/50 chance of getting a 1 or a 0. yes its deterministic in the pure sense but again you can't predict it without doing the math before hand.
i don't see why this is problem.
i'm not arguing that my program has more power than a TM, I'm arguring you can generate "random" TMs. A TM that makes TM's. then run each TM untill it either uses too much memory, or lasts a long time, or hits a Halt state. then use this to approximate Chaitins Omega .
 
Aug 2012
2,464
761
then use this to approximate Chaitins Omega .
You can't computably approximate Omega because that would solve the Halting problem. That was proven impossible in 1936. Do you understand this point?

Now what you could do, would be to take the sequence of finite truncations of the digits of Omega. That would indeed give you a sequence of computable (in fact rational) numbers that converge to Omega. But all that shows is that you have a Cauchy sequence of computable numbers that does not converge to a computable number; showing that the computable reals are not Cauchy-complete. This is a problem for constructive mathematicians, who have to devote a lot of effort to getting around this problem. Is this the kind of thing you have in mind? I'm not really understanding the point you're making since you seem to be contradicting a well known fact.
 
Last edited:
May 2013
94
10
Now what you could do, would be to take the sequence of finite truncations of the digits of Omega.
that;s basically what im doing. im generating a rational number that's approximately equal to chaitins omega.
(say equal to the first 20 binary bits, and then diverges)
 
Aug 2012
2,464
761
that;s basically what im doing. im generating a rational number that's approximately equal to chaitins omega.
(say equal to the first 20 binary bits, and then diverges)
Ok. But you're a long way from your original post. I don't think I understand exactly what your point is anymore. There is no TM that can approximate Omega to arbitrary precision. We seem to be agreed on that now. Or not. I'm no longer sure what we're talking about.
 
May 2013
94
10
my point is: you can generate a rational number to any degree accuracy of chaitins omega.
can you come up with a finite string of chaitins omega that cannot be converted to a rational number?
 
Aug 2012
2,464
761
my point is: you can generate a rational number to any degree accuracy of chaitins omega.
can you come up with a finite string of chaitins omega that cannot be converted to a rational number?
Of course you can approximate any random bitstring with finite truncations. But to do that you already have to have the entire bitstring at your disposal. How do you do that if the bitstring is random? How do you determine the first digit?

Suppose I give you the first six digits of Omega. How do you determine the 7th?