Here are some equivalent statements; maybe one of them is more amenable to solution...
The integral from 0 to N of mod(floor(x/dj)-floor(x/dj+1),2) with respect to x is n.
The symmetric difference between the unions of those members of the respective equivalence classes mod dj and dj+1, in which odd multiples less than N of dj or dj+1 (respectively) appear, has cardinality n.
Well maybe it's best to start at the beginning...and the end.
There are two general cases to deal with: One in which N/dj and N/dj+1 have the same parity, and one in which they have opposite parity.
Same Parity
The Hamming distances between the first and last runs of length dj+1 in its associated pattern, and the runs of that same length in the previous pattern, are each equal to D, defined as dj+1-dj; then using this algorithm on the sub-patterns obtained by removing the aforementioned runs from the originals, the Hamming distances between the runs of aforementioned type are each equal to dj-(3dj-2dj+1)=2dj+1-2dj=2D.
The algorithm will terminate when a run of length 0 (even parity) or of length dj+1 (odd parity) is left, and in the latter case, the last Hamming distance is again D.
In each of these runs of length dj+1, the Hamming distance is between D and dj, because in general dj+1 is less than 2dj, with exception only when dj=1; in that case, equality is achieved, and the fact of total Hamming distance equaling n is easily seen.
Now let us tackle the kth runs of length dj+1 in this case, where k is less than or equal to n/dj+1; the fact I mentioned above means that at most one full run of zeroes or ones will appear in the respective run for the pattern based on dj. Then let's look at A=mod(m*dj,dj+1) for the smallest value of m such that m*dj is greater than or equal to k*dj+1; if k and m have the same parity, then the Hamming distance for the kth runs is equal to A+max(dj+1-dj-A,0); otherwise it is dj.
This sketch is rambling quite a bit, but I think this argument could be adapted to work in the general case, starting from the runs of length dj+1, without division into cases based on parity; anyway, for the case of...
Odd Parity
The first and second runs of length dj+1 have Hamming distances D and 2D, as before, while the last and second-to-last runs have Hamming distances dj+1-D=dj and dj+1-2D; if N/dj+1 is odd, then the middle runs of length dj+1 have Hamming distance dj+1/2.
Maybe in the general case, the Hamming distance between the kth runs of length dj+1 is equal to dj if it divides k*D, and mod(k*D,dj) otherwise...maybe the sum of these numbers as k ranges from 1 to N/dj+1 is n?
The statement is actually false as stated: for a counterexample, try N=30.
For those posting below me, prove that the Hamming distance between the sequences corresponding to (not necessarily consecutive) factors d and d' is N/2 if and only if the greatest powers of 2 dividing d and d' are not equal.
Good point: At first I was thinking "ok somehow we'll need to use the fact that two consecutive divisors of an even number cannot both be odd" only to remember that that statement is false if N=30.
Hypothesis: If the decimal representation of a number has M decimal digits after the decimal point (the last one being non-zero, of course), if you raise the number to the (integral) power of N, the result will have M*N decimal digits after the decimal point.
(So, for example, 12.3415 will have 2*15 = 30 decimal digits after the decimal point.)
Is this hypothesis correct?
Split the number into its last digit and everything before that. Write it as
(A + B)
with
A = a * 10^(-M+1)
B = b * (10^-M))
with a being an integer, 1 <= b <= 9
Now if we raise this binom to the power of N, we can trivially write it as a sum with 2^N terms. (We could use use pascal's triangle and combine them to N+1 terms, but that doesn't really help). We'll get summands of the form:
A ^ (k) * B ^ (n-k) = a^k * b^(n-k) * 10^(-N*M + k)
For k >= 1, these terms cannot influence the N*Mth digit of the result (or any beyond that), since a and b are integers.
For k = 0, we'll get b^n * 10^(-N*M). This cannot influence any digits beyond the N*Mth, so the result has at most N*M digits.
The difficult question is: can the last digit of b^n equal zero? Not in a decimal system. To end in a zero, the factorization of b^n has to contain a 5 and a 2. Since 1 <= b <= 9, that's not possible.
So the hypothesis is true in base 10. It would be false in base 9.
Joined: 8/6/2006
Posts: 784
Location: Connecticut, USA
Is it possible to somehow reference any number one wants (no matter how large), or is there a certain point past which naming or referencing conventions fail and it's simply impossible to sufficiently define a number other than the fact that it's "very large"?
I'm thinking it's impossible, since I'm basically asking if one could "overcome" the concept of infinity, and there are numbers so large that even the most efficient data storage would have to use more than the combined resources of the entire universe to handle the idea of these numbers.
As far as naming conventions go, we can name numbers extremely high easily. For example, a googol is a one followed by a hundred zeroes. Piggybacking off this, a googolplex is a one followed by a googol zeroes. Continuing this way, it's easy to see how fast this grows.
Similarly, I can define numbers like (a googolplex)^(a googolplex)^(a googolplex)^... and grow even faster, but even methods like this eventually require too much thought or data (although you're counting ridiculously high in an incredibly short amount of time).
Thoughts on this? It might be a simple topic, but I find it kind of interesting.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
This reminded me of this XKCD comic (3rd panel).
Graham's number is very very large. Knuth's up arrow notation is used to describe how large this number really is. Multiplication is just repeated addition of one number again and again and again, the same way exponentiation is repeated multiplication again and again. Knuth decided to extend this concept to tetration, which is repeated exponentiation, and so on and so forth:
a+a+a...a+a+a = b*a (multiplication)
\-----v-----/
b many a's
a*a*a...a*a*a = b^a (exponentiation)
\-----v-----/
b many a's
a^a^a...a^a^a = b^^a (tetration)
\-----v-----/
b many a's
a^^a^^a...a^^a^^a = b^^^a (ect.)
\-------v-------/
b many a's
Forgive my horribly ASCII curly brackets. Grahams number is defined as such:
So it is very large indeed. Then putting it into the ackermann function (which increases very fast) is horrifying prospect. Even so, there is another notation, called conway's chained arrow notation which makes numbers increase even faster. Even so, these numbers are computable and real and can be referenced.
This brings me to the topic of some truly terrifying numbers which grow larger than any computable function in existence: Busy beaver numbers. The halting problem in mathematics has been proven to be incomputable. The problem is whether or not a turing machine with n operational states will ever halt. The problem is proven impossible for any computer to figure out.
The busy beaver number is the number of operations it takes for the longest running program on a turing machine before it halts. Therefore, we know that if a turing machine runs longer than this, it will never halt, and run indefinitely.
If we knew what the busy beaver number was for an n state turing machine, we could simply run the program, and if it runs for more operations than that number, we know it will never halt. Thus we would have a foolproof solution to the halting problem. Unfortunately, we already know a solution doesn't exist, so we can't know what these numbers are. Similarly, if we could compute a number larger than the busy beaver number, we could use that number instead to find a solution to the halting problem. Therefore, the nth busy beaver number is larger than any computable number with an n state turing machine.
If we could implement chained arrow notation or up arrow notation in an n state turing machine, then we already know that the nth busy beaver number will be larger than any number possible with chained arrow, or up arrow notation, (or any other notation for large numbers).
So yes, in a way, there are numbers that are finite, but not reference able. (by the way, busy beaver numbers do in fact exist, and they are finite, the first four are 1, 4,6,13, and the next one is at least 47,176,870)
Is it possible to somehow reference any number one wants (no matter how large), or is there a certain point past which naming or referencing conventions fail and it's simply impossible to sufficiently define a number other than the fact that it's "very large"?
I think that what you are asking is if the set of numbers is countable.
The question is: Which numbers?
Obviously all integers can be represented: Just write them eg. in base-10. Likewise all rational numbers can be represented: Write them as two integers in base-10. This is because these sets are countable.
All real numbers cannot be all represented because it's an uncountable set. (This is relatively easy to prove, even.)
Is it possible to somehow reference any number one wants (no matter how large), or is there a certain point past which naming or referencing conventions fail and it's simply impossible to sufficiently define a number other than the fact that it's "very large"?
I'd assume the latter. There is only a finite amount of mass in the universe and it can only be arranged in a finite amount of ways (planck constants). As such, even when we use the entire arrangement of the universe as the representation of a number, we can still only represent a finite amount of numbers.
Joined: 8/6/2006
Posts: 784
Location: Connecticut, USA
Warp wrote:
I think that what you are asking is if the set of numbers is countable.
The question is: Which numbers?
Obviously all integers can be represented: Just write them eg. in base-10. Likewise all rational numbers can be represented: Write them as two integers in base-10. This is because these sets are countable.
All real numbers cannot be all represented because it's an uncountable set. (This is relatively easy to prove, even.)
Well, in my example and my thought process I was thinking about the naturals. I could extend the thought to the rationals to include incredibly small numbers which would amount to the same discussion... as you mention, the reals are not countable since they are dense (and like you mentioned, an easy proof).
But my question was more about pitting human ingenuity in mathematics and naming conventions against the fact that numbers can get infinitely large. Who would win? Like I mentioned (and as Scepheo and andymac mentioned) I feel as though we can get as clever as we want with the most advanced computers, but there are always numbers that are just not able to be represented in any meaningful way due to their magnitude.
But my question was more about pitting human ingenuity in mathematics and naming conventions against the fact that numbers can get infinitely large. Who would win? Like I mentioned (and as Scepheo and andymac mentioned) I feel as though we can get as clever as we want with the most advanced computers, but there are always numbers that are just not able to be represented in any meaningful way due to their magnitude.
I'm not sure I understand your question. We already have a system to represent any natural number. We have had such systems since antiquity.
But my question was more about pitting human ingenuity in mathematics and naming conventions against the fact that numbers can get infinitely large. Who would win? Like I mentioned (and as Scepheo and andymac mentioned) I feel as though we can get as clever as we want with the most advanced computers, but there are always numbers that are just not able to be represented in any meaningful way due to their magnitude.
Well, within finite natural numbers: This problem seems similar to data compression.
Taking the viewpoint of Kolmogorov complexity: For each number, there exists a program that computes the number (in finite time, but possibly requiring insane amounts of time and space). Now, there is certain minimum length for such program.
Now consider huge finite numbers. Some such numbers have quite short programs (e.g. g_64). But even very near (relatively)[1] of such numbers are lots of numbers that have huge minimal representative programs.
So some huge numbers are easily representable, but most aren't.
[1] E.g. Within [1-10^-10^10^10^10*g_64,1+10^-10^10^10^10*g_64].
I'm not sure I understand your question. We already have a system to represent any natural number. We have had such systems since antiquity.
Assuming you mean "writing it down", that system fails horribly very soon.
Even if you were able to write a digit on every atom in the observable universe, you couldn't write out a googolplex.
As such, you need to use other systems to denote such numbers. In this case we decided to use either 10^100 in a system where we can raise to power or the system where we named a 1 with a googol zeroes a googolplex.
But, assuming the system definition itself is part of a system (otherwise we could just take the representation "x" and let loose infinite systems on it to get all numbers), we run into a problem. I think you'll agree with me that in this universe, we can only create a finite number of representations in any given system. As we need to define the system within this universe as well, we can only define a finite number of systems and create a finite number of representations for these systems. As such, it's impossible to denote all numbers (be it natural, real, complex, even or whatever) regardless of system.
Here's the thing about the concept of 'naming a number'.
If you have a number in mind - e.g. you could compute and write down all its digits if asked - then trivially it has a name. Even the most monstrously large finite number with no seeming method to compute it has a name - its decimal representation.
If you can't, then its 'name' is actually some algorithm that will compute it - and depending on what you're after (e.g. as stated earlier, busy beaver numbers) the algorithm for it may not be guaranteed to finish in finite time. Such a number is 'uncomputable', not because it can't be named, but because you can't figure out deterministically what all its digits are. But you can talk about it by name.
You're both making valid points but I think you're both talking past each other.
Warp et. al. are saying that we can create a definition natural numbers such that any natural number can be expressed. So if we have, for example (purposefully incomplete):
1) 0 is a natural number.
2) For any natural number n, S n is a natural number.
(For those not familiar with this notion, S stands for Successor.)
Then, by definition, any natural number is expressible as S S ... S 0, because if it weren't then it wouldn't be a natural number per the axioms. (And we could further define some rules that turn S S 0 into 2, and vice versa.)
Scepheo et. al. are saying that it is impossible to actually completely write an arbitrary natural number. In other words, the ellipses I wrote above can contain arbitrarily many S's, yet at some point it is impossible for me to physically write down that many S's.
This "paradox" comes from the fact we can claim a function has a certain kind (also called sort or type in other formal contexts) of value, yet not calculate that value. For example, Graham's number. We can say this is a natural number without actually writing it down: S S S ...(many many!) 0. Whether or not we should be allowed to make these kinds of claims is (to some) up for debate.
The idea that numbers should not be considered extant if they cannot actually be written down is called "Ultrafinitism" or "actualism". So while you can express an algorithm for calculating Graham's number, you cannot say the result of this algorithm is a natural number until you write it down.
I personally find this point of argument meaningless, from both sides. Mathematics is a tool. If assuming I can operate on results I cannot write down as if I could is useful to me, then I will make that assumption. If it turns out this assumption introduces problems that make my system no longer suitable to me, I won't. Either way, to claim a certain mathematical system is the "right" one is just nonsense.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
Uncomputable functions such as busy beaver numbers have proven to grow faster than any computable function in existence. If such a number existed that was so large that it could not be referenced, then it would have to be uncomputable, since these are the largest kinds of numbers. We need to search not only for a number which is uncomputable, but in order to find a number that is uncomputably referenced, it's name has to be uncomputable itself. I think by their very nature, these numbers may be difficult if not impossible to prove to exist at all, however, I can still define a theoretical finite number N, the smallest uncomputably named number in existence, and if it exists, I have just given it a name, however, it seems to me that there is no probable way of proving whether or not these numbers exist at all.
I think this may be similar to the idea of a "super" turing machine. A machine which is capable of solving the halting problem. The busy beaver numbers for those machines are in a way uncomputably named.
Scepheo et. al. are saying that it is impossible to actually completely write an arbitrary natural number. In other words, the ellipses I wrote above can contain arbitrarily many S's, yet at some point it is impossible for me to physically write down that many S's.
I think you have misunderstood my point. I don't mean that you actually need to write down a number for it to "count". I consider formal expression just as valid.
Let's consider my view of the "size" (let's go with s(n)) of a number. Let's have a look at a big number and express it in a number of ways:
- 2147483647
- 8th Mersenne prime
- Int.MAXVALUE
- 2^31 - 1
The point is, no matter what formal expression we choose, we still need some amount of characters to express it. Now I consider the size of a number to be the least amount of "units" with which I can express it.
Let's also assume, for the sake of argument, a system in which we can express our numbers. Obviously, our current system is shit as it uses a crapload of pixels (or ink or whatever) to even express something as simple as 0 or 1. We could obviously do better by letting "absolutely nothing" represent 0 and we'll have a single Higgs Boson be 1. Then we'll need to define quite a few primes so we'll define the function m(n) (the nth Mersenne prime) and we'll have it be represented by a neutrino. Now we can get our number by having a neutrino followed by eight Higgs Bosons!
Obviously we can do better than this, so we'll just assume our system S is the optimal system. That is, in our system the size (as defined before, units being elementary particles in this case) of any given number is the minimum of all possible systems.
I've tried, I've honestly tried. I have the best system possible. But I still end up with an infinite amount of numbers that are all non-zero size. I also seem to have an upper limit (u) to my size: the amount of elementary particles in the universe. But as there's infinite numbers, there exists at least one number c for which s(c) > u. Crap, I can't express that number.
GMan wrote:
I personally find this point of argument meaningless, from both sides. Mathematics is a tool. If assuming I can operate on results I cannot write down as if I could is useful to me, then I will make that assumption. If it turns out this assumption introduces problems that make my system no longer suitable to me, I won't. Either way, to claim a certain mathematical system is the "right" one is just nonsense.
I'm not claiming any system to be better than any other system. In fact, I don't see anyone doing this. Where did you get that idea? But still, my point is that no matter how hard you try, there will always be numbers you can't operate on.
I'm not sure I understand your question. We already have a system to represent any natural number. We have had such systems since antiquity.
Assuming you mean "writing it down", that system fails horribly very soon.
I didn't say "writing it down". The OP says "express", which is quite an ill-defined and ambiguous term. What did he mean by "express"?
We can "express" all natural numbers. We have a system for that. As I said, for example with decimal digits. We can also "express" all rational numbers likewise. We cannot express all real numbers.
If he meant "physically write it down" then the answer is trivial: No. Obviously there's an infinite amount of natural numbers and a finite amount of space. This question wouldn't make much sense.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
Warp wrote:
We can "express" all natural numbers. We have a system for that. As I said, for example with decimal digits. We can also "express" all rational numbers likewise. We cannot express all real numbers.
What do you mean that we cant express all real numbers?
Do you mean that there is a difference between the idea that we could write down two (possibly preposterously large, but finite) natural numbers to express any given rational, but "most" reals do not have a finite number of digits?
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
I don't remember the initial question asking about the expression of numbers. I thought it was about the naming and referencing conventions. The question was whether or not numbers exist which cannot be named or referenced using a language i.e. they are so large, that you cannot say exactly what the number is. I think depending on your definitions, there are multiple answers to this question.
If we use a symbolic, sequential language to define numbers ( for example, the ASCII alphabet) then the upper bound on numbers that you can express using this language is 256^n where n is the number of symbols you used. the reals are not countable, and so some numbers may require an infinite number of symbols to be expressed.
I brought up the concept of busy beaver numbers, because their digits cannot necessarily be found, also, it is known they grow faster than any computable function, however that does not mean they cannot be written down. A finite amount of resources is required to write down the digits of any busy beaver number, not to mention, you can always say "the 315th busy beaver number" to reference a busy beaver number. Therefore, the largest number referenceable with n symbols (for many languages, not all) will be greater than a busy beaver number.
However, bringing up "super" busy beaver numbers now brings up a new point. Previously, we could run an algorithm that could calculate busy beaver numbers, albeit, it would take an infinite time to do so, hypercomputation is not even conceivable, because it is not possible physically (yet), and definitely not possible by our brains. We have no real conceivable notion about what these machines do, so really, not only do we know that these large numbers exist, we have referenced them in such a way that there is no algorithm at all, not even one that would run in an infinite amount of time that could calculate the value of such a number. Therefore, you may as well have said that these numbers are just "very large" or "larger than the limit of defineable numbers written in n symbols". Such a number is too large for any naming conventions, as it cannot be definitively named.
However, let's say we managed to stumble upon the digits of the nth super busy beaver number, and wrote it down, not knowing that it was in fact the nth super busy beaver number. You could probably use the same number of symbols to define an even larger super busy beaver number. so if we allocate ourselves a finite n, the largest number we can reference definitively, is less than than the largest number we can define, but not find at all (even with an infinite amount of time).
Do you mean that there is a difference between the idea that we could write down two (possibly preposterously large, but finite) natural numbers to express any given rational, but "most" reals do not have a finite number of digits?
Having an infinite number of digits is not a problem per se. For example the majority of rational numbers have an infinite number of digits, yet can be represented with a finite expression (namely, two integer numbers).
Any representation of a number uses a countable amount of symbols. Therefore such representation can only be used to represent countable sets (even if those sets are infinite). The set of real numbers is uncountable, which means that there's no one-to-one mapping between all the real numbers and a set of countable representations. Therefore it's not possible to represent all possible real numbers, no matter what kind of notation you use.
It's not so much about infinity (after all, there's an infinite amount of natural numbers, yet every single one can be represented using eg. the decimal notation) but about countability.
I don't remember the initial question asking about the expression of numbers. I thought it was about the naming and referencing conventions.
Yes it is. However, "the 315th busy beaver number" is, in fact, a formal expression of a number.
Warp wrote:
If he meant "physically write it down" then the answer is trivial: No.
I never said it wasn't trivial.
Also Warp, you're right in pointing out that even with the possibility of an infinte amound of symbols it's impossible to represent the real numbers, but you're assuming your set of symbols is countable (be it infinite or not). If your set of symbols is uncountable you can represent the reals just fine.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
Scepheo wrote:
andymac wrote:
I don't remember the initial question asking about the expression of numbers. I thought it was about the naming and referencing conventions.
Yes it is. However, "the 315th busy beaver number" is, in fact, a formal expression of a number.
... that's what I said.
We move on from busy beaver numbers of turing machines to busy beavers of hypercomputers. My point was that really, if you allocate yourself a finite number of symbols n, then generally, you can reference a number that is a) impossible to find, even given an infinite amount of computing power (so busy beaver numbers do not fall into this category, eventually, if we had an infinite amount of time, we could solve them), and b) larger than any definitively named and referenceable number with n symbols.
Allthough you can still technically name these numbers, the point was that even if the number was written down in front of you, you still couldn't tell that it was the number you were referencing, even if you could solve the halting problem, and also it would be larger than any number you could find definitively. Therefore, referencing a number in this way, you may as well say the number is "very large" because it doesn't provide any more or less information about the size of the number.
http://en.wikipedia.org/wiki/Hypercomputation
If your set of symbols is uncountable you can represent the reals just fine.
That's only always true if the continuum hypothesis is true, and we can't prove that. Generally it's true.
I think you have misunderstood my point. I don't mean that you actually need to write down a number for it to "count". I consider formal expression just as valid.
Let's consider my view of the "size" (let's go with s(n)) of a number. Let's have a look at a big number and express it in a number of ways:
- 2147483647
- 8th Mersenne prime
- Int.MAXVALUE
- 2^31 - 1
The point is, no matter what formal expression we choose, we still need some amount of characters to express it. Now I consider the size of a number to be the least amount of "units" with which I can express it.
Let's also assume, for the sake of argument, a system in which we can express our numbers. Obviously, our current system is shit as it uses a crapload of pixels (or ink or whatever) to even express something as simple as 0 or 1. We could obviously do better by letting "absolutely nothing" represent 0 and we'll have a single Higgs Boson be 1. Then we'll need to define quite a few primes so we'll define the function m(n) (the nth Mersenne prime) and we'll have it be represented by a neutrino. Now we can get our number by having a neutrino followed by eight Higgs Bosons!
Obviously we can do better than this, so we'll just assume our system S is the optimal system. That is, in our system the size (as defined before, units being elementary particles in this case) of any given number is the minimum of all possible systems.
I've tried, I've honestly tried. I have the best system possible. But I still end up with an infinite amount of numbers that are all non-zero size. I also seem to have an upper limit (u) to my size: the amount of elementary particles in the universe. But as there's infinite numbers, there exists at least one number c for which s(c) > u. Crap, I can't express that number.
I don't think this is different than what I said at all, but then obviously that means I'm misunderstanding you. :)
In my head, you're saying (as Warp is) that we have a system S that can in principle write any number. "In principle" meaning given infinite resources and time, every number can be expressed. For the sake of simplicity I want to use the sub-Peano system I defined above, because I think it's safe to say improvements on this (like your particle example) are just scaling factors.
Start with 0. This is the first natural number. Now put an S in front of it: S 0. That's the second. Now put an S in front of that, ad infinitum. For any natural number, this process will eventually write it out, by definition.
What we all agree on is that we, in reality, cannot actually do this process.
Is that correct? When I was reading your response I think I had a glimpse of what you were trying to imply, but I lost it as a thought about it. Could pick out
the wrong part about from above? Sorry for being dense!
Scepheo wrote:
I'm not claiming any system to be better than any other system. In fact, I don't see anyone doing this. Where did you get that idea? But still, my point is that no matter how hard you try, there will always be numbers you can't operate on.
I meant the mathematicians that argue about the things I linked to (it happens). My bad.
If your set of symbols is uncountable you can represent the reals just fine.
Could you explain how a set of distinct individual symbols (that can be used to represent numerical values) can be uncountable? Because I cannot even fathom how. (Granted, I'm not that good at math and grasping things like infinite sets, but still...)
