I've been Cantoring about set theory for a few posts now and I can't find any obvious inconsistencies. No holes, no places where 135 years of brilliant people pounding on it have left in-roads.
There are aspects of the way set theory handles various infinities that I wonder about, but within the context of set theory itself, it all appears consistent.
Still, this is unsatisfying because it never really answered my questions about infinities. I got curious about the structure of the reals precisely because I couldn't picture any way that a structure could head off to multiple infinities in a way that can't be enumerated. No matter how many infinities, it should be possible to place a finite limit on all of them, and then just parcel them out, one by one.
Well, in that sense it sounds simple. However, when it comes to actually dealing with the infinite paths that make up the real numbers, there does seem to be a few added problems. A few that are surprisingly deep.
Strangely, there is a well-known structure to hold the representations of all of the permutations for R, for which mathematicians agree that it does in fact express all of the possibilities. In A Very Large Structure, I go through the basis of taking one of these base10 real representation trees, called P0 and along with an infinite node parent tree, create a structure T that (in theory) contains all of the real values.
The problem with that post was that given the unknowns in the underlying structure, it is assumed that the constructed sets P0, Pn and T are all uncountable. We can construct the sets, but we cannot count the elements in those sets.
Still, it is a good first step, in that at least R is contained in a set T, and we now have someway of visualizing the different elements in R.
INFINITE CONSTRAINTS
A point that will come up again and again in this post is how to constraint a set of multiple infinite values (on different "axises"). If we do have things stretching off to some large number of different infinities, we can limit each one, and then permute them, one at a time.
In this way, we can count things. An example is being able to count the cells of a bi-infinite spreadsheet, it stretches off into four different directions, on two different axis (vertical and horizontal). We can count the cells by circling around the center, slowly increasing the size of the circle. In a regular spreadsheet that only goes off to the right and to the bottom, we still have two axises, and we can use just diagonals to count everything.
Another example is how I was enumerating the right hand side of the example in the post on Magic Sequences. It's another diagonal example. Yet another example was in the original Infinite Node Tree post. Again, we essentially circle around the inside of the tree, gradually opening the different infinities, one at a time.
It works out that so long as we have some type of 'memory' or stack, we can constrain any number of infinities (even an infinite number of them, it's just more memory), parceling out the elements, one-by-one, and gradually opening up the size of the bounds. There is likely a nice way to prove this, but all on it's own it is mostly self-evident.
And it's exactly this point that keeps driving me to find out why everybody believes that the real values seem to have a way to counter this. The essence of 'uncountable' seems to come not from the structure of thereals, or the number of embedded infinities, but from how they are related to each other in a combinatorial sense.
I kept assuming that the structural attributes would take precedence. After all, if we can pack all of R into some fixed structural representation, then there ought to be a large number of different alternative structures. One of them must be countable.
FUNNY NUMBERS
Another issue that we can deal with early on is this post is that 1.0 = 0.9999... Personally I see this as an abuse of the way infinities work. In the proof listed inWikipedia:
http://en.wikipedia.org/wiki/0.999...
I don't think the subtraction at line 3 in the Digit Manipulation section is particularly valid. The missing difference is caused by a subtle shift in the way the finite representations are being handled. The two infinities are slightly offset from each other. But that's not a popular opinion in mathematical circles.
Another way of looking at this is that the following very small number:
0.000...001
is considered to be just too small to be a real number. Which is kinda mean, don't you think? I mean, so it is tiny, sure, but does that somehow invalidate its existence?
If we have an example, such as a base10 tree, we see that at any node, at any time, anything can just peel off. Even if it's extremely small. We can go down a near infinite number of zeros, and then just start winding around.
It similar to how we often get junk digits hidden below floating point numbers in a computer after a large series of arithmetic operations. Mostly it is worth ignoring, but in this case while the paths lead to very small numbers, they are still valid paths in the tree, and by (some) definition every path in the tree is a unique number.
Still, if we have a set with:
S = { 1.0, 0.99999... }
we can allow it to be either be two elements or just a single element. Set theory neatly hides this for us.
It makes no real practical difference. Everybody is allowed to have their own viewpoint, and it won't affect the overall results. There is enough space in this area of mathematics to support minuscule-number-haters. :-)
Although I didn't investigate deeply, one would expect that if there is one case of this with little numbers, there are probably an infinitely large number of cases. It should likely be possible to build up a large number of little differences, and prove something horrible like 1=2, or some other fun result like that.
TREE TIPPING
Getting back to reals, if we have all of the reals in a base10 structure, then we should be able to manipulate it. This is a popular place for cranks to start from, because the base10 version seems to be easily complete. The problem with the base10 structures is that they leave the real numbers as endless paths. That makes them more or less impossible to count directly, so we ought to try some funny business.
P0 is our base10 representation tree, over the range [0,1).
We can fiddle with this tree, but I'll switch it to base2 (binary) first because it's a little easier to deal with:
So we have a tree called B2, which is:
- a binary tree
- root is labeled 0
- all children have a left child labeled 0 and a right child labeled 1
- covers the range [0,1)
If we run down an infinite winding path and finesse it into a base2 number, we get:
0.11 0010010000 11111 10110 …
This is actually Pi shifted right twice (Pi/4 ?), so we know this is an infinite string of non-repeating digits.
Now, it is well known that the nodes of a tree are enumerable, but the actual paths themselves are not. Being sort of clever, I first figured that I could just "tip" the tree onto its side, so that the nodes no longer held the representation of the path. Instead, each node could hold a complete infinitely long real value.
If I have such a tree of reals, each completely contained in its own unique node, then I can enumerate all of the nodes, and thus all of them...
Tipping is easy, so long as we have an infinite node tree to tip it into. We just take the far left path:
0.000000000...
As the root node, and then we add in all of it's children. In this case, the children are the infinite list of any nodes that wind off to the right from the above path,ie:
0.100000000...
0.010000000...
0.001000000...
...
Now, for each one of these children, starting with 0.100000... we can add in all of their right children:
0.110000000...
0.101000000...
0.100100000...
...
Etc.
In that way, if we follow the first child down a level, for each level we go, we will get more and more strings of 1.
So now as we approach infinity, we get an infinity large tree, where each node holds an infinitely long real value.
This almost seems like it would work, but there are two very serious problems:
0.1111111111... is never in the tree.
0.11 00100100001111110110… isn't either.
This happens, because no matter how deep we go, our path is made up of only a finite number of transformations. That is, it is an endless string of all zeros, with some "head" string placed in front by the permutations.
By definition we essentially get a permanent tail of all zeros. And it is the tail of zeros that keep either of the two above numbers from ever appearing in the tree.
So the numbers:
0.111111111100000000...
0.11 0010010000 1111110110 00000 00000 00000 …
Are in the tree, but the actual infinite right branch and all of the irrationals are not.
Just to recap, if I tip a tree like my P0, from my other article, the irrationals, which where basically the last elements in P0, never make it into the the tipped version of the tree. We can count the new tree, but only because the difficult nodes are missing.
In a sense, this implies that the original base10 representation trees never even really held numbers like Pi/10. Well, they did, because they were defined that way, and we can transfer these numbers to a set P0, but they remain strangely disconnected because of their infinite, and non-repeating tails.
A TALE OF TAILS
Now it turns out that these "tails" are far more difficult then they first appear. They keep coming back to haunt me in different ways.
In fact, the real complication in R being uncountable isn't rooted in the way it goes off to three different infinities all at once, it's really just finding a deterministic way of permuting between the different tails that makes it difficult.
That is, the problem isn't that we can't find a structure large enough to handle the reals, it is that we can't bind them all together in a way to make it easy to get from one to another. We can't find a bridge between them. They are disconnected.
Some interesting things about tails:
- they don't have to go through all of the possible permutations. They can miss some.
- they can repeat a nearly endless number of times, only to peel away at the last second, and still be considered non-repeating.
- they can have any number of little junk bits at the end (if you're not a minuscule-number-hater :-)
Still tails and the permutations on them have some issues:
- finite changes to a tail leave it as an irrational
- infinite, but repeating changes to a tail also leave it as irrational
- irrational changes can leave the tail as either a rational or another irrational
- the difference between two distinct tails is an infinite permutation of an infinite number of changes.
In that last point, we have to make an infinitely large number of small changes to align two distinct tails together, all of the way to infinity. Pi/10 -sqrt(2)/10 looks like:
0.314159265...
-.2
+.03
-.003
+.0003
-.00003
-.000008
+.0000001
-.00000001
+.000000001
...
0.141421356...
Where the differences are non-repeating.
To get from one to the other requires an infinite number of changes, stretching all of the way back to the deepest darkest corners of infinity. It would be nice if there were only a finite set of changes between them, but it doesn't work that way. The tails are distinct, and remain so forever.
What is interesting to note from the third point above, is that Pi/10 - sqrt(2)/10 is itself another irrational:
0.172737909...
That is, if we have two independent irrationals, the difference is a third one.
RANDOM CHANCE AND WALKS
A possible way to enumerate the different real values is to bounce around, one at a time, using random numbers. If we just pick randomly from the original base10 representation tree, then maybe our problems go away?
We can get each infinite path from the tree one at a time, by using the following random generation:
0.[0-9][0-9][0-9][0-9][0-9]...
where [0-9] is some random digit between 0 and 9.
For each iteration, we just pick another random number. Since we are picking them one at a time, if as we get to infinity we have a good chance of picking all possible numbers, then we can count them as we pick them.
The big issue is determining whether or not all of the permutations will get selected at some point. When dealing with probabilities like flipping coins, we can always turn to the Law of Large Numbers:
http://en.wikipedia.org/wiki/Law_of_large_numbers
which says that given enough samples, eventually the actual flips will gradually approach the expected value.
That is, if we flip a coin enough, then 50% of the time it will be heads, and 50% of the time it will be tails. In the short run, the percentages may be skewed one way or the other, but eventually they will work out close to the expected value.
Using the law of large numbers we realize that we can get:
- all single random values to be between 0 and 9
- all nodes in the path to be between 0 and 9.
- all all pairs, triplets, etc. to eventually exist for all finite combinations
That seems fine, but again what works for finite problems quickly runs into trouble with infinite ones.
We don't know whether or not we'll get all infinite permutations, and we have no way of working that out. We may miss a few.
That's fatal, because the different between Pi/10 and sqrt(2)/10 is an infinite set of permutations. It's exactly that infinite permutation that we are trying to consistently generate. That's what ties all of the seeds together.
I took a quick look at Markov chains, hoping that might help. If we consider each random path to be a state of some type, and each state to only be dependent on the last one, we can see a random walk through the whole space as a Markov chain.
However, chains with infinite state space, such as this, don't seem to be as well understood, or at least I had trouble finding any reference materials.
Still, you would expect to run into problems trying to calculate probabilities for infinite events. Most of that branch of mathematics seems geared towards finite things, winning game shows, or proving that not everyone can go bankrupt all at once :-) (OK, I admit that's not fair, it was amis-use of actuarial science, or so I was told ...)
SEEDS
What we really have is a large set of independent tails, each belonging to what we can see as discrete seeds with some combintorical relationship between them.
That is, we can start to classify all of the reals as either:
- finite
- repeating
- irrational seed
- the permutation of an irrational seed.
We don't care about the rationals (finite and repeating) because we already know they are easily countable. We know how to step one by one through all of their possible permutations and combinations (we even know how to over-count them :-) They are just included in the base10 structure along with the more difficult irrationals.
To clarify we can define these irrational seeds to be combinatorically independent (algebraically independent?) non-repeating irrational elements, for which there is an infinite number of finite permutations separating any two elements. The term "distinct" is probably an easier way of saying it.
BASIC PERMUTATIONS
In Crank it Up, I built up an infinite spreadsheet with a bunch of simple permutations. The post started with using Pi as the seed, and then applied two different families of permutations on the entries to generate a whole lot of irrationals. Many people pointed out that this was only a slice of the possible reals, but it was interesting anyways because it was a fairly large slice.
Since all of the permutations were either finite, or infinitely repeating, the result of any operations on an irrational is another irrational. That is, so long as there is a definitive pattern to the change, the change itself will not be able to unwind the non-repeating nature of the original number. Non-pattern trumps pattern. Initially that was a bit of a problem, but it can also be beneficial.
We can work out the basic permutations on irrationals as being:
- finite or infinite
- addition/subtraction or multiplication/division
- reconstructive
Using those possibilities, and guessing at a few others, we can define a larger set of different permutations:
- finite changes, example +0.1
- infinite repeating changes, example +0.101010101....
- right/left shift or divide/multiple by 10
- divide/multiple by repeating 0.1010101....
- block swap (re-arrange blocks)
The first three are from the earlier post. The infinite divide is just another possible permutation.
The last change comes from realizing that an irrational with the blocks swapped subtracted from itself will result in a finite number, making the swap itself just a basic permutation.
In fact, this category includes any permutation where the start is an irrational, the finish is an irrational and the difference is a finite set of finite or simply repeating rationals ...
If we take a seed, and apply any finite number of these different types of permutations, the results are a countable set, because we apply them one at a time.
If we apply an infinite number of such permutations, the results are also countable, and countably infinite. An example of this being a countably infinite set is in the bi-infinite spreadsheet. We applied the first three permutations listed above, but by circling around, we can avoid the infinities and gradually count all of the elements.
Strangely, we can apply an infinite number of different combinations of permutations, and assuming that we do so, one at a time, and limit how we span across infinite sets, then the results are still a countably infinite set.
So, there appear to be a finite number of different types of permutations, that can be applied in an infinite number of different ways. And in this way we can generate really large sets of related real numbers from a seed that are all countably infinite by construction.
SEED PERMUTATIONS
Now it's interesting to note that if we subtract two seeds from each other, we either get zero, a finite set of permutations, or we get a new seed. This is true for all of the different operators (+ - / *) on thereals, not just subtraction.
If we get a new seed, we can define this to be a 'seed permutation', not just a basic one.
So if two seeds are related, their difference is either 0, a finite number or a repeating rational. This means that they are combinatorically related in some way, the results of some type of basic permutation, not a seed one.
If not we get a new unique irrational number.
For the operators in R:
- the difference between two seeds is either finite or a seed: A - B = C
- the addition is either finite or a a seed: A + B = D
- the multiplicand is either finite or a seed: A * B = E
- the dividend is either finite or a seed: A / B = F
That is, for Pi/10 and sqrt(2)/10, we get:
0.314159265... - 0.141421356... = 0.172737909...
0.314159265... + 0.141421356... = 0.455580621...
0.314159265... * 0.141421356... = 0.044428829...
0.314159265... / 0.141421356... = 2.221441470...
0.141421356... / 0.314159265... = 0.450158157...
Which is a new set of five different irrationals. When the result is a new irrational then we can consider the permutation type to be a seed permutation. That is, a permutation that allows us to jump from two non-repeating seeds to a new seed.
Now, we know for some types pf permutations that seeds themselves are the sum of the permutations between other seeds. That sense of infinite, likely means that although we can identify a finite set of seed permutations, it may be impossible to identify all of them, since there may actually be an infinite number of different types. But I am not sure about that.
The really big problem is that the seeds are very independent from each other. We can't just apply simple numbers to them to get to the next set of seeds. We must look for permutations from a higher level, that is the types that are needed on the seeds themselves to get to each other.
Some known seed permutations:
- limited symbols (numbers using only 2, 3, ..., 9 symbols)
- cut out finite blocks/add in finite blocks
- cut out infinite repeating blocks/add in repeating blocks
- irrational changes (infinite, non-repeating).
- irrational operations (+ - * / on two independent irrationals).
Given a few seeds, can we find all of the possible seeds that are between the seeds? It seems likely, since there are ways to permute between some seeds, but it certainly isn't an easy question.
How do we know we've hit all seeds? That is the hardest problem. There are likely some major permutations, seed and basic that I am missing. Still my current set is fairly large and still useful. Is it complete? I think that would take further research.
If we apply seed permutations to a set of countably infinite seeds, then the results are still countably infinite. Because we get a new seed, and we can swap back and forth between them. That means we can take an countably infinite set of seeds and generate a much larger set of seeds that is still countably infinite.
COMBINATORICALLY COMPLETE SETS
Now, we can look at this all from a much higher perspective.
If we apply all the basic permutations, we can construct countably infinite sets that hold large numbers of real values. The bi-infinite spreadsheet is an example of this.
We want to define a 'combinatorically complete' set to mean a set of real numbers, based around a seed(s), and permuted with all of the known, possible general permutations possible, but still being countably infinite by definition.
Start with an real element E0
We can create:
set C0 as a combinatorically complete set based on E0
Now, since we have a complete set, we apply Cantor's diagonal construction to that set, and it will produce a new value that is not in our original set. That is, Cantor's will act as a bridge and give us an element from some othercombinatorically complete set.
E1 is the new seed from C0 created by Cantor's diagonal construction.
set C1 is from the permutations on E1
We can now combine these two base sets:
CC0 = C0 ∪ C1
Since CC0 is a complete set, we can apply Cantor's again which will produce a new element from outside the set:
E2 is another seed from CC0 create by Cantor's
We can keep this up for the sets:
En, Cn and CCn
Where CCn is:
CCn = CCn-1 ∪ Cn
We can see that this is growing, very fast.
For fun, we can add in applying all of the seed permutations SPn as well, and thus any new Cn sets on any new created seeds. Thus we can create something like:
CCSn = CCSn-1 ∪ CCn ∪ SPn
We can take the union of all of these possibilities, both basic and seed permutations and then apply Cantor's to generate a new seed outside of the initial set. We can keep this up for infinity.
Thus our set CCSn is getting quite large. Of course, we can continue this on indefinitely allowing n to approach infinity.
WHAT'S MISSING
While our rapidly growing union of combinatorically complete sets is growing massively and quickly, it is not sufficient to just assume that it will encompass all of the real values. Instead we need to prove that there are is no E'0 that is left out.
Start with an E'0 that is defined to be missing. We know that we can get to this value by any basic permutation, so we have to include that:
U0 is the combinatorically complete set from E'0
Now, for each E'n in U0, it is possible that some set of values UU will generate E'n when using Cantor's diagonalization construction. Since we are interested in making sure those values are uncountable, we have to consider UU to be a possible pathway to E'0, so, it has to stay outside of CCSn.
UU0 is the set that will generate U0,
But each element in UU0 itself could possibly be generated through a bridge from Cantor's, so we have to really consider
UUn
Now there is always at least one element E'n, not in any UUn, so we have to include all of those values into our uncountable set as well.
We have to be careful that any of the seed permutations will not create a path to E'0 either. So we need to consider:
UUSn = UUSn-1 ∪ UUn ∪ USPn
Now, interestingly enough, because we are working backwards from Cantor's, there is no way of being sure that different subsets ofUUSn don't just generate each other's values. Thus it is possible for UUSn to be infinite, but not growing sufficiently larger like CCSn.
The nature of the two sets is quite different.
TOTAL REMAINING SPACE
While we can create a UUSn, we have a problem. UUSn itself is actually countably infinite because of its construction. We can easily count it.
Still there must be uncountable sets so that means there are a whole series of UUSnm sets which are distinct from each other. That is, there is no bridge between them.
That means that there have to be a whole series of un-related UUnm sets,
R = CCSn ∪ UUSn0 ∪ UUSn1 ∪ ... ∪ UUSnm
Still even that provides a problem, since even an infinite number of UUSnm sets is still countable, and now all of our uncountable values are actually countable in some way. So it must actually be something like
R = CCSn ∪ UUSn0 ∪ UUSn1 ∪ ... ∪ UUSnm ∪ ...
Where that final ... is somehow a way of keeping the first part of R -- which although it is disconnected is still countable -- uncountable in some way.
So, now lets take some element Ek. This element might be in CCSn, if it is, then it is countable.
If not, then it might be in UUSnm, and so it is found and counted.
But if it is in neither, it is in the "..." part, then by definition it belongs together with all of its permutations, and all of the seed permutations as a new setDDSn.
But if DDSn is not equal to or a subset of CCSn, and it is not equal to or a subset of any UUSnm, then it must be another element of UUSnm, because it is disconnected from all of the other UUSnm sets.
Because of that, for all Ek, they must belong to either CCSn or the UUSnm sets, which means that R must be laid out as follows:
R = CCSn ∪ UUSn0 ∪ UUSn1 ∪ ... ∪ UUSnm
This means that there must just be the two different types of sets and nothing else. Since each of these is countably infinite by definition, and there are a countable number of them, then the union of all of them is also countably infinite.
Now, the construction and countability remains the same, even if we remove using seed permutations. It's also the same if we remove all of the basic permutations and just build up the elements one at time, however it is far easier to understand when it is applied to large 'pools' of dependent elements.
ANOTHER PERSPECTIVE
There is another way to look at this. We can start with a T, which we assume to be uncountable. Within T were the Pn sets, each of which is also assumed to uncountable. That stands to reason, since at least one subset of any uncountable set must be uncountable itself.
But if we follow that subset deconstruction downward, we quickly start to get rid of a lot of elements. That is for a set U that is uncountable, we need a series of subsets:
U0, U1, U2, ..., Un ...
of uncountable subsets, all of the way down to an infinite, but very small subset. However there can be no smallest uncountable set, and certainly there can be no finite set at the bottom of everything.
But, at the very bottom, there must be some set of elements. And they must be brought together in some way to form the larger sets:
..., Un, ..., Cn, ...
That is, there can be no smallest quanta in the system, such that it is countable. But everything has to be built up from something.
If we map this back onto our base10 representation tree, we have this structure that is shooting off to infinity in a large number of paths, and for each path. If we prune some nodes from this tree, this essentially says that whatever is left is essentially isomorphic to the original tree.
That is, no matter how many branches you prune, the tree just grows right back. However, one can guess that we should be able to prune faster than the tree can grow, and as such at some point we'll get down to something that is countable, but if we do, then the entire tree was countable.
Not only that, but if we keep pruing the tree, then there needs to be some sort of 'asymmetry' in the tree that causes its uncountable property.
But the base10 tree is really simple, grows uniform and except for being massive, is not really all that complex. At least, not complex enough to hide some asymmetry that accounts for it being impossible to enumerate.
THE HALLWAY ANALOGY
There is another way to look at base10 structures. It is as if you were standing in a very long hallway. There is a door down at one end, but the other end stretches off to infinity. In the hallway are a clump of wires. As each wire runs down the hallway, it becomes many more wires. That is, the clump of wires in front of you, if you are facing the door, is way smaller than the clump next to you, which is smaller than the clump behind you.
If you reach out and grab the clump of wires, there are a finite number of them, and they can easily be counted. Now, if you take a step backwards, and grab the next clump, there are more wires but still finite in number. As we work our way backwards down the hall, we can count more and more of the wires.
In a sense, a base10 representation tree is a rather fixed structure. Its difficulty comes from the fact that it is what I've been calling 2D. That is, there are two separate types of infinities built into the tree: the number of branches, and the length of the branches themselves. We don't need to enumerate both infinities, we only need to know how many infinite branches there are (or could be).
The problem comes from the idea that branches such as the irrationals are not actually in the tree until latter, but again we're only concerned with counting all of thereals , not just the irrationals. The wires running down the hallway are the parents of both, even if they are not full 'infinite' until much later. We don't need to know how long the wires are, we just need to know how many of these are splitting off to infinity.
SEED PERMUTATIONS
It seems likely that seed permutations should also be able to generate everything. That is, there is only one reason why some complete set of seed permutations shouldn't be able to bridge all of the different seed sets together. An infinite number of different infinite permutations would a pretty solid reason, but if that isn't the case then we can do all of the generation.
Although the infinitely long tails make the conceptualization more complex, underneath, the relationships between the seeds is not that sophisticated. At least not sophisticated enough to be able to prevent counting, or generation of other seeds.
We do know, for instance that we can fit all of the permutations together into a base10 representation tree. Application of a structure, any structure, implies some type of inter-relationship between the elements.
Possibly we can start with the all of the permutations of symbols, and then add/delete all possible infinite pattern representations into the mix to cover the whole spectrum.
Does a simple cut/diff loop generate a lot of seeds? That is, if we start with Pi, and then randomly remove one digit, and subtract the two numbers we'll get another seed. If we keep this up, how much coverage will we get from such a simple algorithm?
Do permuting between all of the different possibly combinations of symbols generate a lot of seeds? Can we just start with all of the two symbol patterns, and move through each different set of permutations?
We know that any seed may or may not go through a specific set of patterns, and it may end up going through the same patterns over and over again, but in a way that doesn't repeat in the long run. In this sense, we could probably generate a giant dictionary of all possible patterns, and then permute them against each other to generate all possible seeds. Of course, as always the weakness is how to handle the infinitely long nature of the patterns.
It's easy enough to use a few methods to permute an infinite number of seeds, an then use the differences to get an even larger infinite number. Continued on infinitely, this may also likely produce full coverage.
If we can see the base10 representation, then our ability to easily jump from infinite branch to infinite branch should not be that complex.
SUMMARY
Tails and infinite permutations in R are a difficult problem. Not because of the complexity of the structures, not even because of most of it stretches out to infinity.
It's hard because there is some combinatorical independence between the different sets. Still, all we need do is tie it all together with a bridge or two.
Cantor's diagonal construction is defined to find things not in a set, therefore it is the perfect bridge builder between sets. Since it can't fail, and it can be used one at a time, we can bounce from countable set to countable set, forever.
Seed permutations should work as well. There is nothing intrinsically complicated about applying permutations to seeds, they're just not as obvious as the basic permutations.
Things should be countable, especially if they can be contained in a structure of some type. Uncountable implies that there is some type of structure that exists, but isn't representable in some strange way; that we can't navigate around it.
It is the structure that has no structure, which is well, rather odd, is it not?
Sunday, January 10, 2010
Wednesday, December 9, 2009
Quickie: Let it be Free
I was thinking about how the "scientists" in the Climategate scandal are hiding their raw data. If the science is really objective, then by its own merits other researchers will reach the same conclusions.
If you're afraid that they won't, then you're hiding something.
As such, no scientific researcher should ever hide their data. Ever! Not only that, but their work should be out there too -- formulas, theories, methodologies, everything -- to be judged not only by their peers, but also by the public at large. If science is a quest for the truth, then the truth has nothing to fear from inspection.
But I realize that it is not just our disgraced climate researchers who have adopted policies of secrecy. You can't, for example, get most of the academic work in Computer Science unless you join the ACM. In fact you can't get most works in academia unless you join some tight-nit clique. It's all closely guarded.
Long ago, I could understand how these organizations needed to charge money in order to recoup the costs of publishing on paper. It makes sense that they shouldn't take a loss. But amazingly that changed in the Information Age, and instead of offering free downloads it appears that most organizations choose to monetize their IP (business speak for "go for the profits").
You could make some well thought-out arguments about how the funds collected go back into the organizations to help spread their good works, but oddly one can easily suspect that most of the income is really used to protect the revenue generation (business speak for "stuff that causes profits") and pay salaries.
Academia -- data, papers, methodology, everything -- should be free and done out in the public. It should be open, and visible. Approachable. Companies hide their research because they are locked in competitive battles. Universities (and other research institutes) are not companies.
Research is not competition, it should be co-operative. And it shouldn't matter who contributes (particularly when we live in a day and age were so many people are both eager to help, but also have the available time).
I should never be told that I can't download a paper unless I pay a big sum of money. It should be free.
If you're afraid that they won't, then you're hiding something.
As such, no scientific researcher should ever hide their data. Ever! Not only that, but their work should be out there too -- formulas, theories, methodologies, everything -- to be judged not only by their peers, but also by the public at large. If science is a quest for the truth, then the truth has nothing to fear from inspection.
But I realize that it is not just our disgraced climate researchers who have adopted policies of secrecy. You can't, for example, get most of the academic work in Computer Science unless you join the ACM. In fact you can't get most works in academia unless you join some tight-nit clique. It's all closely guarded.
Long ago, I could understand how these organizations needed to charge money in order to recoup the costs of publishing on paper. It makes sense that they shouldn't take a loss. But amazingly that changed in the Information Age, and instead of offering free downloads it appears that most organizations choose to monetize their IP (business speak for "go for the profits").
You could make some well thought-out arguments about how the funds collected go back into the organizations to help spread their good works, but oddly one can easily suspect that most of the income is really used to protect the revenue generation (business speak for "stuff that causes profits") and pay salaries.
Academia -- data, papers, methodology, everything -- should be free and done out in the public. It should be open, and visible. Approachable. Companies hide their research because they are locked in competitive battles. Universities (and other research institutes) are not companies.
Research is not competition, it should be co-operative. And it shouldn't matter who contributes (particularly when we live in a day and age were so many people are both eager to help, but also have the available time).
I should never be told that I can't download a paper unless I pay a big sum of money. It should be free.
Saturday, December 5, 2009
Transformers
First, some Administrivia. Given that I haven't sold any copies for quite a while now, I've decided to make the electronic copy of "The Programmer's Paradox" free for a while (a few months probably). It can be found at Lulu:
http://www.lulu.com/content/paperback-book/the-programmers-paradox/178872
Lack of sales is really my fault, as I was never really strong about pushing the book (as it was never edited as well as I would have liked). It was my first real act of writing, so please go easy on me :-)
TRANSFORMATIONS
While I was fiddling with prime numbers, I also had another collection of un-related ideas invade my brain. At the high level, it involves how we have constructed Computer Science as a formal system.
Computers deal with two distinct things: code and data. This is an inherent duality in the basic concept.
However, all of our theoretical models are extremely "code-centric". That is, they focus on the boundaries of the code within a formal system, and leave the data as just a secondary player.
This is true of Turing machines, deterministic finite automata and all of the other formal system's modelling of computing that I am aware of. The data exists, but only as an unimportant set of "symbols" that come and go on some "tape". It's the code we are really studying, not the data.
As I've said before, that is not entirely unexpected as most people's introduction to computers come from a code perspective, and they see the machines in terms of the user functionality and how they can apply it.
Still, the counter-approach of seeing computers in terms of machines that assemble mass piles of data is an equally correct, yet significantly less complex way of visualizing them.
Code is intrisically complex and hard to unwind, data is structurally complex and mostly is normalized by virtue of its usage. That is, there are an infinitely large number of ways to write a program, but there is only a small (and finite) number of reasonable mappings from the internal data back to reality. The data is either correct, or it isn't (not accounting for bugs, of course).
A MODEL
So, I started thinking about some way to model the data "within" the system, without having it overshadowed by the code.
I've worked out a number of the basic elements, but these ideas are far from complete. Because of this, I'll try to include my rational in this discussion, along with the rather sparse ideas in the hope that collectively these ideas will get pushed farther along by anyone interested in them.
Starting at the top, if we aren't interested in the code, then it shouldn't appear in the model explicitly. With that in mind we can define a transform T that maps the data from it's value A to another value B.
T(A) -> B
A transformer is some block of (unknown) code that takes an explicit set of inputs, and returns an explicit set of outputs. To make life easier, there won't be a concept of global variables. Everything necessary for the transformation must be passed in explicitly. And there is also no concept of "side effects". Everything changed in any way is passed back outwards. Transforms can return multiple values.
So we might have something more complex like:
T(a,b,c,d,e,f,g,h) -> A,B,C
A transform that takes 8 parameters, applies some type of algorithm to the incoming data and returns three other new parameters. It's a nice simple start.
Now, none of this would be interesting if we couldn't use this to model something relevant. What might be interesting to know, is "given that there is some infinite number of possible algorithms for a class of transforms (or there are none), what are the bounds of these algorithms as they are running?"
SORTING
I woke up one night, a while back, with an idea about how to use transforms to calculate the bounds on algorithms. While asleep it seemed to be a very strong idea, but awake I've been unable to fully pin in down. It's mostly about continuously decomposing the algorithms, to get a better idea of how they work, but without ever having to examine the inner workings themselves.
The general idea is pretty simple (if it works). While we can't just splat in a bunch of algorithms into the transforms and calculate the bounds, we can sub-divide the transforms into smaller ones (endlessly) until we can use those atom pieces to calculate best and worst performing boundaries.
So for instance, we might be interest in studying the class of "sorting" transformers. That is, any transformer that takes N elements in one arrangement and returns them in another re-arranged "sorted" (lexically, numerically, etc.) order.
If we were going to look at the trivial case, then we find that:
Ts(A) -> A [ O(1) .. O(1) ]
In English, this says that any transform that "sorts" a single entity, requires at minimum "constant time" to sort, and at maximum, also constant time to sort (I used a range notation, but I'd guess that using little o and big O notation may be more expected (acceptable)).
What's really interesting here is to figure out the range of growth of the performance of the family of algorithms. What I'd really like to know is what is the range for:
Ts(A1,A2,...,An) -> Aw,Ac,...,Am
The various different families of algorithms that differently sort through a list of N elements.
We can deal with this by taking the two bounding cases at the same time; the best and worst case.
In the best case, the elements are sorted because the algorithm "knows" the behavior. That is the above algorithm decomposes into
Ts(A1,A2,...,An,L) -> Al,P1
Ts(A1,A2,...,An,K) -> Ak,P2
...
Ts(A1,A2,...,An,M) -> Am,Pn
That is, for each different element (L,K,M) at a time, a transformation takes the whole list, the current element, and returns that element and it's position in the new list.
Since we're still working with the best case, there are N decompositions of the original algorithm that generate N positions, which are used to re-arrange the list. Each decomposition, if we are still in the best case, could use something "intrinsic" from its input to calculate P. As such, the best possible sort algorithm which can use "intrinsic information" from it's incoming data, can only ever re-order the list in n*O(1) time which I think works out to O(n) time.
In the worst case, however, assuming that the code is all practical, and really does things, we can decompose the sort algorithm down into N transforms, each of which has to examine every N elements, in order to calculate P. As such, it works out to n*n*O(1) or O(n^2). So we get something like:
Ts(A1,A2,...,An) -> Aw,Ac,...,Am [ O(1), O(n^2) ]
THE POWER OF SEARCHING
In an analogous manner to sorting we could start examining the class of transformers that take a large number of inputs, and return a subset of "found" outputs. I won't go into too much detail, but at each level of decomposition we can reduce the number of arguments, split off a best and worst case. In that way we might start with:
Tf(A1,A2,...,An,C1,C2,...,Cm) -> (null | Ak,...,Al)
We could simplify this by adding null in as an input:
Tf(null, A1,A2,...,An,C1,C2,...,Cm) -> Ak,..,Al
Then this describes the "find" family of transforms, that takes a set of input, and a set of criteria, and then returns nothing, or some smaller subset of "found" items.
At the very bottom, as a best case, a transform would either "know" about that the data was or was not it what it was looking for. Otherwise the transform would have to look through everything, and determine which were the correct elements.
The best and worse cases are similar to the space for sorting.
SUMMARY
So why do I think this is useful? Primarily because it can be used to draw hard boundaries on a family of algorithms. From the standard Computer Science perspective, you can work with algorithmic complexity to find better algorithms, but you have no way of knowing if you've found the best one.
There is some computational bound which cannot be crossed, and it is nice to know where that bound is.
Of course in my examples, I took the best case to be a trivially not-possible case, but that was primarily because I've really haven't gone deep enough to understand that lower bound in a better fashion. It's likely, from the output, and from decompositions, that we should be able to figure a way to calculate a much more accurate best case boundary.
Another place where I think this could be useful is in studies the computational complexities themselves. We've had categories of complexity for a long time like NP, but we've been unable to make a dent in determining elementary issues like P=NP.
These problems too represent important boundaries on the things that can and would like to do with our computers. Unfortunately now, the studies in these areas have been tied to working with existing algorithmic problems, and with specific algorithms.
If we can work with the complexity classes, without having to descend into finding the actual algorithms themselves, we may be able to construct higher order proofs about our boundaries, without getting too wrapped up in the specifics of existing algorithms.
Another interesting issue about this approach is that it takes us one more step down a path I've talked about before:
http://theprogrammersparadox.blogspot.com/2009/04/end-of-coding-as-we-know-it.html
With our current code-centric perspectives on software systems, it seems as if the systems can quickly exceed everyone's threshold of understanding as they swell in complexity.
What this means in practical terms is that while the system may start under control, with enough people contributing, and enough work getting done, the system rapidly moves into a "stupid zone", where it has become so large and so complex, that nobody can fully understand it anymore.
If nobody can understand it, then nobody can use it (fully), and as such it is just a monolithic nightmare of related functionality.
Once large enough, the only way programmers can deal with adding in new functionality is by carving off little sections and ignoring the rest. This divide and conquer strategy works, but it also means the functionality itself starts becoming disjoint, and the system gets even more complex as a result.
So we get these behemoths that are so large and so disjoint that people can't make use of the available functionality. We pass over some maximum point in combined functionality, where on the other side our usage degenerates horribly.
The perfect example of this is Microsoft Word. Maybe a few decade agos, most users understood most of the functionality and could use it well. Now, the software is so convoluted that most users are forced to use less features just because the interactions between the features rarely does what is expected.
We used to heavily "type" our documents to allow the formater to make them auto-magically consistent. Now, anybody would have to be crazy to turn on the formatting, it hasn't worked (behaved consistently) in years. So we're back to working with our documents in the most crude manner possible.
The general case is that if you keep building on some underlying complexity, at some point the complexity itself will overwhelm what you are doing, and become its own issue.
If instead of building up ever-increasing mountains of complexity, we just worked at one low level abstraction and used the machines themselves to dynamically assemble the complexity, we could avoid a lot of problems.
The abilities of our computers are strong enough that they can be used to map pathways through a sea of transformations. Intellect is necessary for "how" to do the transformations, but it is not necessary to calculate a deterministic path between a large series of them.
We've based our current architectures and technologies implicitly on our existing theories. The Turing machine model drove the hardware construction and that drove the way we've built software. This in turn controls how we see our software problems.
We see every problem as a nail, because we started out with using hammers. And after a very long time of pounding nails into anything that moved, we're now seeing the intrinsic weaknesses in our approach to building things.
If we can't control and contain complexity, we can't exceed a fairly low threshold for the sophistication of our systems. We are stuck, just crudely re-write the same things over and over again, with simple variations on the same underlying technologies. After twenty years, this lack of progress is getting boring.
http://www.lulu.com/content/paperback-book/the-programmers-paradox/178872
Lack of sales is really my fault, as I was never really strong about pushing the book (as it was never edited as well as I would have liked). It was my first real act of writing, so please go easy on me :-)
TRANSFORMATIONS
While I was fiddling with prime numbers, I also had another collection of un-related ideas invade my brain. At the high level, it involves how we have constructed Computer Science as a formal system.
Computers deal with two distinct things: code and data. This is an inherent duality in the basic concept.
However, all of our theoretical models are extremely "code-centric". That is, they focus on the boundaries of the code within a formal system, and leave the data as just a secondary player.
This is true of Turing machines, deterministic finite automata and all of the other formal system's modelling of computing that I am aware of. The data exists, but only as an unimportant set of "symbols" that come and go on some "tape". It's the code we are really studying, not the data.
As I've said before, that is not entirely unexpected as most people's introduction to computers come from a code perspective, and they see the machines in terms of the user functionality and how they can apply it.
Still, the counter-approach of seeing computers in terms of machines that assemble mass piles of data is an equally correct, yet significantly less complex way of visualizing them.
Code is intrisically complex and hard to unwind, data is structurally complex and mostly is normalized by virtue of its usage. That is, there are an infinitely large number of ways to write a program, but there is only a small (and finite) number of reasonable mappings from the internal data back to reality. The data is either correct, or it isn't (not accounting for bugs, of course).
A MODEL
So, I started thinking about some way to model the data "within" the system, without having it overshadowed by the code.
I've worked out a number of the basic elements, but these ideas are far from complete. Because of this, I'll try to include my rational in this discussion, along with the rather sparse ideas in the hope that collectively these ideas will get pushed farther along by anyone interested in them.
Starting at the top, if we aren't interested in the code, then it shouldn't appear in the model explicitly. With that in mind we can define a transform T that maps the data from it's value A to another value B.
T(A) -> B
A transformer is some block of (unknown) code that takes an explicit set of inputs, and returns an explicit set of outputs. To make life easier, there won't be a concept of global variables. Everything necessary for the transformation must be passed in explicitly. And there is also no concept of "side effects". Everything changed in any way is passed back outwards. Transforms can return multiple values.
So we might have something more complex like:
T(a,b,c,d,e,f,g,h) -> A,B,C
A transform that takes 8 parameters, applies some type of algorithm to the incoming data and returns three other new parameters. It's a nice simple start.
Now, none of this would be interesting if we couldn't use this to model something relevant. What might be interesting to know, is "given that there is some infinite number of possible algorithms for a class of transforms (or there are none), what are the bounds of these algorithms as they are running?"
SORTING
I woke up one night, a while back, with an idea about how to use transforms to calculate the bounds on algorithms. While asleep it seemed to be a very strong idea, but awake I've been unable to fully pin in down. It's mostly about continuously decomposing the algorithms, to get a better idea of how they work, but without ever having to examine the inner workings themselves.
The general idea is pretty simple (if it works). While we can't just splat in a bunch of algorithms into the transforms and calculate the bounds, we can sub-divide the transforms into smaller ones (endlessly) until we can use those atom pieces to calculate best and worst performing boundaries.
So for instance, we might be interest in studying the class of "sorting" transformers. That is, any transformer that takes N elements in one arrangement and returns them in another re-arranged "sorted" (lexically, numerically, etc.) order.
If we were going to look at the trivial case, then we find that:
Ts(A) -> A [ O(1) .. O(1) ]
In English, this says that any transform that "sorts" a single entity, requires at minimum "constant time" to sort, and at maximum, also constant time to sort (I used a range notation, but I'd guess that using little o and big O notation may be more expected (acceptable)).
What's really interesting here is to figure out the range of growth of the performance of the family of algorithms. What I'd really like to know is what is the range for:
Ts(A1,A2,...,An) -> Aw,Ac,...,Am
The various different families of algorithms that differently sort through a list of N elements.
We can deal with this by taking the two bounding cases at the same time; the best and worst case.
In the best case, the elements are sorted because the algorithm "knows" the behavior. That is the above algorithm decomposes into
Ts(A1,A2,...,An,L) -> Al,P1
Ts(A1,A2,...,An,K) -> Ak,P2
...
Ts(A1,A2,...,An,M) -> Am,Pn
That is, for each different element (L,K,M) at a time, a transformation takes the whole list, the current element, and returns that element and it's position in the new list.
Since we're still working with the best case, there are N decompositions of the original algorithm that generate N positions, which are used to re-arrange the list. Each decomposition, if we are still in the best case, could use something "intrinsic" from its input to calculate P. As such, the best possible sort algorithm which can use "intrinsic information" from it's incoming data, can only ever re-order the list in n*O(1) time which I think works out to O(n) time.
In the worst case, however, assuming that the code is all practical, and really does things, we can decompose the sort algorithm down into N transforms, each of which has to examine every N elements, in order to calculate P. As such, it works out to n*n*O(1) or O(n^2). So we get something like:
Ts(A1,A2,...,An) -> Aw,Ac,...,Am [ O(1), O(n^2) ]
THE POWER OF SEARCHING
In an analogous manner to sorting we could start examining the class of transformers that take a large number of inputs, and return a subset of "found" outputs. I won't go into too much detail, but at each level of decomposition we can reduce the number of arguments, split off a best and worst case. In that way we might start with:
Tf(A1,A2,...,An,C1,C2,...,Cm) -> (null | Ak,...,Al)
We could simplify this by adding null in as an input:
Tf(null, A1,A2,...,An,C1,C2,...,Cm) -> Ak,..,Al
Then this describes the "find" family of transforms, that takes a set of input, and a set of criteria, and then returns nothing, or some smaller subset of "found" items.
At the very bottom, as a best case, a transform would either "know" about that the data was or was not it what it was looking for. Otherwise the transform would have to look through everything, and determine which were the correct elements.
The best and worse cases are similar to the space for sorting.
SUMMARY
So why do I think this is useful? Primarily because it can be used to draw hard boundaries on a family of algorithms. From the standard Computer Science perspective, you can work with algorithmic complexity to find better algorithms, but you have no way of knowing if you've found the best one.
There is some computational bound which cannot be crossed, and it is nice to know where that bound is.
Of course in my examples, I took the best case to be a trivially not-possible case, but that was primarily because I've really haven't gone deep enough to understand that lower bound in a better fashion. It's likely, from the output, and from decompositions, that we should be able to figure a way to calculate a much more accurate best case boundary.
Another place where I think this could be useful is in studies the computational complexities themselves. We've had categories of complexity for a long time like NP, but we've been unable to make a dent in determining elementary issues like P=NP.
These problems too represent important boundaries on the things that can and would like to do with our computers. Unfortunately now, the studies in these areas have been tied to working with existing algorithmic problems, and with specific algorithms.
If we can work with the complexity classes, without having to descend into finding the actual algorithms themselves, we may be able to construct higher order proofs about our boundaries, without getting too wrapped up in the specifics of existing algorithms.
Another interesting issue about this approach is that it takes us one more step down a path I've talked about before:
http://theprogrammersparadox.blogspot.com/2009/04/end-of-coding-as-we-know-it.html
With our current code-centric perspectives on software systems, it seems as if the systems can quickly exceed everyone's threshold of understanding as they swell in complexity.
What this means in practical terms is that while the system may start under control, with enough people contributing, and enough work getting done, the system rapidly moves into a "stupid zone", where it has become so large and so complex, that nobody can fully understand it anymore.
If nobody can understand it, then nobody can use it (fully), and as such it is just a monolithic nightmare of related functionality.
Once large enough, the only way programmers can deal with adding in new functionality is by carving off little sections and ignoring the rest. This divide and conquer strategy works, but it also means the functionality itself starts becoming disjoint, and the system gets even more complex as a result.
So we get these behemoths that are so large and so disjoint that people can't make use of the available functionality. We pass over some maximum point in combined functionality, where on the other side our usage degenerates horribly.
The perfect example of this is Microsoft Word. Maybe a few decade agos, most users understood most of the functionality and could use it well. Now, the software is so convoluted that most users are forced to use less features just because the interactions between the features rarely does what is expected.
We used to heavily "type" our documents to allow the formater to make them auto-magically consistent. Now, anybody would have to be crazy to turn on the formatting, it hasn't worked (behaved consistently) in years. So we're back to working with our documents in the most crude manner possible.
The general case is that if you keep building on some underlying complexity, at some point the complexity itself will overwhelm what you are doing, and become its own issue.
If instead of building up ever-increasing mountains of complexity, we just worked at one low level abstraction and used the machines themselves to dynamically assemble the complexity, we could avoid a lot of problems.
The abilities of our computers are strong enough that they can be used to map pathways through a sea of transformations. Intellect is necessary for "how" to do the transformations, but it is not necessary to calculate a deterministic path between a large series of them.
We've based our current architectures and technologies implicitly on our existing theories. The Turing machine model drove the hardware construction and that drove the way we've built software. This in turn controls how we see our software problems.
We see every problem as a nail, because we started out with using hammers. And after a very long time of pounding nails into anything that moved, we're now seeing the intrinsic weaknesses in our approach to building things.
If we can't control and contain complexity, we can't exceed a fairly low threshold for the sophistication of our systems. We are stuck, just crudely re-write the same things over and over again, with simple variations on the same underlying technologies. After twenty years, this lack of progress is getting boring.
Subscribe to:
Posts (Atom)