- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Any number with infinitely many digits and no algorithm with which to generate them.
Here's the method to find one:
0. start from zero
Note that you can never get past step 3.
Step 4 exists for the chance that the random algorithm happened to generate a number such as infinitely many 3s with no other digits. There is a 0 percent chance of this happening, but it's still important to be thorough.
Admin
Filed under: I thought of this before you posted it, but forgot to actually write the post, so I can't prove I thought of it first. :(
In step 1, it is necessary that the digits be truly random, not pseudorandom, or else you could represent the number by describing the PRNG that generates the digits.
Admin
True, but a PRNG which always generates that exact set of numbers given the exact same seed would therefore always fail the condition in step 4, resulting in another infinite loop.
Admin
Yes, exactly. Any number that can be generated by the PRNG can be represented by the PRNG algorithm and seed, and therefore is not a member of the set of unrepresentable numbers.
Admin
In probability theory, this is non-equivalent to "impossible", btw..
Admin
You might as well go straight to that and leave out the stuff with asking whether it has infinitely many digits: the finite numbers embed trivially within the infinite numbers.
Admin
How would you observe the difference?
Admin
What is the use of talking about infinities in a finite universe anyway?
Admin
That depends on what you mean by finite.
Admin
Take a random number from the unit interval (
[0,1]). The chance of the number being exactly equal to0.5is zero. But it is not impossible.Admin
Not if the random numbers are taken out of a finite set of representable numbers.
Admin
The term you are looking for is “infinitesimal” and you need to ask what is the probability that the chance that something infinitesimally small is exactly equal to zero? ;)
Admin
I learned zero.
Admin
You learned wrong. :stuck_out_tongue:
Admin
No. Zero is right. Infinitesimals don't exist in the field of real numbers. You have to extend that field, but I don't know if that is still measurable.
Admin
It's not like the original question makes much sense anyway. Exact equality isn't actually well-defined on the reals in the first place.
Admin
(Do you mean "on the reals" or "on the surreal"?) On both sets equality is exactly defined, for all that I know. A real number can be defined as a set of rational numbers (or a pair of sets of rational numbers, which is equivalent). Surreal numbers similar.
Admin
OK, then is 0.5 equal to 0.4999… (with an infinite number of nines)? If not, how can you tell the difference?
I assume that a number must have identity independent of its representation.
Admin
Yes. Yes, it is.
There are more pages on the Internet discussing the question whether or not 1 equals 0.9999... (with an infinite number of nines) than you can read within a human lifetime.
Edit (added): The problem is that the concept of real numbers as such can't be grasped by the human mind any more than a fourth spatial dimension; we have to rely entirely on definitions, theorems, and other abstractions.
Admin
Those are different representations for the same number.
Admin
Actually, no they aren't. As I understand it, there does exist a consistent framework for working with infinitesimals as distinct from the value whose limit they approach, in something called 'hyperreal' numbers, though I could not even begin to understand much less explain them. As a practical matter, infinitesimals are the basis of differential calculus (at least in Newton's original formulation - Leibnitz had a different form, but it was basically the same concept, and formulations of the calculus that avoid limits didn't appear until the late 20th century), which has proven to be pragmatically useful if nothing else.
Admin
You can use extensions of the field of the real numbers to do calculus in the "intuitive" way Leibniz did (I'm not so sure about Newton's "fluents"), and it can be easier to do calculus rigorously with them instead of the usual limit approach.
Nevertheless, the hyperreals are still an extension, that is, not the same as the real numbers. Just like integer numbers are an extension of the natural numbers, rational numbers of the integers, complex of the real, and so on. (Every extension adds a layer of abstraction that makes it a bit more difficult for the human mind to wrap around that contraption.)
There is no way to distinguish between 0.4999... (infinite number of 9s) and 0.5 within the real numbers, therefore we call them equal.
In the same way, we call 2 * 1/2 the same as 1, for in the theory of rational numbers, there can't be a way to distinguish them, although it is clear that, in nature, there is no way to put two half eggs together to one complete egg. (Or, even if we could, we can't pull three apples out of a bag containing exactly two apples, then put one apple back, and have an empty bag.)
In hyperreal numbers, surreal numbers or other similar extensions of the real numbers, there is a defined difference between a number that one would naïvely write as 0.49999... (infinite number of 9s) on the one hand and 0.5 on the other hand. But that number is not represented by the sequence 0.49999... but rather by (the equivalence class of) the sequence {0, 0.4, 0.49, 0.499, ...}.
Admin
OK, you are correct, it is outside of the set of reals. I defer to you're greater knowledge regarding the representations, as I am not familiar with that aspect of hyperreals.
Admin
There are infinitely many representable numbers in any given interval. (And infinitely more non-representable numbers; in fact the majority of them are non-representable, but the number of representable numbers is nonetheless infinite.)
In computing, maybe, but why wouldn't exact equality be defined on reals?
0.5 and 0.4999... are two different ways of representing the same exact number in base-10. So yes, 0.5 is exactly equal to 0.4999...
Admin
Why is a set of numbers that are less real than ordinary real numbers described as hyperreal? :trolleybus:
Admin
"hyperreal" is a contraction of "hyperactive" and "for real".
Admin
Admin
what? like π?
we can describe it, and we know how to calculate it, and we've calcualted it far enough that the error for a circle the size of the observable universe would be IIRC about 5 angstroms (a very small error indeed) but we'll never be able to completely and accurately represent the actual number
Admin
Correct. If a real number can be described by, say, a decimal number with infinitely many digits, there must be a sequence that describes those digits, an algorithm for producing those digits. If those algorithms are themselves of finite length, they must be enumerable and so countable (i.e., mappable to the integers; see the works of Church, Turing, Gödel and Kolmogorov for details).
Hence we know there must be real numbers with infinitely many digits whose digit production algorithm is itself infinite, i.e., that their complexity and their representation can be considered to be unified. This might be achieved by making the sequence truly random I guess. Moreover, there must be a lot of such numbers…
Admin
Admin
No, because for all that that is a transcendental number, there's an algorithm which can calculate the digits of it; it's algorithmic complexity is much lower than that of a truly random number.
Admin
You seem to know the answer to your second question.
Admin
ah. you mean that sort of number.
yeah.... good luck with that. inorder to identify the number we must be able to describe it. So in order to create an indescribeable number you would need to create a number such that the algorithm describing it is on the order of $n^{10^{100^{g_{64}}}}$ complexity
(and because mathjax was disabled...... here's a png render of that formula) [image]
Admin
That sounds like something describable.
http://scienceblogs.com/goodmath/2009/05/15/you-cant-write-that-number-in/
Admin
true, but good luck writing the algorithm for more than a couple of digits.... that's one hell of an exponent on the digit count.
it would literally be more space efficient to just write the number out and never stop writing.
Admin
In base 10, that may be true. In base π, on the other hand... :stuck_out_tongue:
Admin
[quote="boomzilla, post:187, topic:50418] http://scienceblogs.com/goodmath/2009/05/15/you-cant-write-that-number-in/ [/quote] One of the comments just blew my mind by throwing Cantor's diagonal argument into the list of describable numbers. Is the resulting number on the list? Surely I just described it...
Admin
Yes, but how difficult it is to do isn't important to whether it's describable or not.
Did you really
write outdescribe all those numbers when you made your list?Admin
Admin
Write an algorithm to create the list of describable numbers. Job done!
Admin
Surely the very definition of 'indescribable numbers' is, in fact, a description? So indescribable numbers can in fact be described, and as such are not actually indescribable numbers, given that you can describe them as indescribable.
Admin
That might depend a bit how we look at it. (I haven't thoroughly thought through it yet)
The only way Cantor's diagonal argument makes sense, is to have a countably infinite set of real numbers.
Yes, you did.
And thereby proved that
if the set of describable numbers is infinite, it must be uncountably infinite
if the set of describable numbers is finite, it must be infinite,
Therefore the set of describable numbers is is actually uncountably infinite.
We can't do more for we can't apply Cantor's diagonal argument to uncountably infinite sets - because this argument numbers an infinite set of lines by the natural numbers, so the set of lines is of course countably infinite.
We could try the set of numbers that can be described with finite length descriptions. This is countably infinite, too (see the proof that the set of polynomials with rational coefficients is countably infinite). So this set won't do either (see above).
So we could either take the set of numbers that is describable with countably infinitely long descriptions. Whether this is consistent or not, depends on whether we take the axiom of choice for granted or not (and thereby the possibility of well-ordering this set).
If we assume that we can well-order that set, we can talk about the first number in the well-order that is outside that set, so this can't be done either. Implication: the class of describable numbers is not a set (see the proof that the class of ordinal numbers is not a set).
What remains is, we talk about numbers that can be described with a description of a (previously) given maximal length. This is consistent, even with the possibiliby of well-ordering any set, for saying "The first number outside that set" implicitly contains the definition of "that set" and is therefore longer.
I think this is very closely related to programming languages that allow loops only if the maximum number of loop passes is defined before the loop is entered. Those languages are not Turing complete, though.
Well, I just wrote what came on my mind, I apologize in case it was too complicated.
Admin
No, that's more of a nickname. :smiley:
A number (with an infinite number of digits) is probably best considered to be indescribable if it has no shorter description (i.e., algorithm for digit production) than the number itself. Thinking about what such a beast might look like is brain-bendingly hard, but “it looks really random” is a really good approximation: less random things probably have a finite algorithm for generating them.
Admin
Nope, it's a definition of the set, not a definition of the elements within.
Admin
I can't decide if you're serious or not. Given past math discussions, I'll assume you are.
Yes, that is a description. Just not the type of description that would put the number into the set of describable numbers.
Admin
Pedants! [image]
Admin
Look...it's math, for crying out loud. It's the only proper way to talk about it. Even if you insist on calling it maths.
Admin
Edit: And even when I post I was taking the piss, people are still biting...
Admin
The set of indescribable numbers can. Not the individual numbers that are elements of that set.
But otoh, in mathematics, you can never be sure there isn't a contradiction somewhere, so it might be that we actually were able to prove that at least one number of the set of indescribable numbers can be described if only we knew how. Wouldn't be the first time we had to rethink an entire branch of mathematics.
Maybe if we take/assume the axiom of choice as granted (and therefore that the set of indescribable numbers can be well-ordered), we can run into a contradiction:
We take any well-order of that set, and then we talk about the first number of that well-order (which exists by the definition of a well-order), which is a description of a number that is element of that set. This is a contradiction indeed.
Implication: Either there are no indescribable numbers (which can't be the case, as we have strong evidences if not a proof), or the class of indescribable numbers is not a set (which would imply that the class of numbers is not a set either, for the class of describable numbers is a set), or there exists a well-order of that set but we can't describe it (which implies there exists a well-order of real numbers, but there is no way to describe one).
Admin
The best part? IIUC, there is a good chance that the question of whether indescribable numbers exist as a sub-set of numbers is undecidable. What fun!