- Thread starter phillip1882
- Start date

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?

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

i admit, it's not perfect, but it should be close enough for most purposes.

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.

en.wikipedia.org

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

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.

en.wikipedia.org

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:

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 .

You can't computably approximate Omega because that would solve the Halting problem. That was proven impossible in 1936. Do you understand this point?then use this to approximate Chaitins Omega .

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:

that;s basically what im doing. im generating a rational number that's approximately equal to chaitins omega.Now what you could do, would be to take the sequence of finite truncations of the digits of 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.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)

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?

can you come up with a finite string of chaitins omega that cannot be converted to a rational number?

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