Universal Decision Elements in 4-valued LogicHow many first order Universal Decision Elements of four argument places are there in 4-valued logic? It is certainly more than 430, over 1 quintillion (1 x 1018), and possibly considerably
more than that.
Due to a lack of computer power our project to discover the number, described below, did not run to completion.
If anyone knows the number perhaps they'd get in touch.
TheoryIn 2-valued logic Unary Functors are easy to understand. For example NOT(0) is 1 and NOT(1) is 0. "NOT" is a Unary Functor: a function that acts on one operand. If we choose P to represent the operand, when P is 0, NOT(P) is 1; when P is 1, NOT(P) is 0. If we write this as a "truth table" we get:
In 4-valued logic each operand can have 4 values, say 0,1,2,3. Unary Functor number 6, for example, which we will write as U6, has this truth table:
In 4-valued logic there are 256 Unary Functors. The output of each Unary Functor is simply one of the 256 possible combinations of 0,1,2,3. The first few and the last of the 256 Unary Functors are:
A first order Universal Decision Element of 4 argument places is a formula containing 4 variables F(P1,P2,P3,P4) (where the Ps can have the values 0,1,2,3 or P, and there must be at least one P) which can simulate all 256 Unary Functors. For example, say F(0,3,1,P) gives the result 0,0,0,2 when P takes the values 0,1,2,3 respectively.
I.E: This is the same result as U3(P). And let's say that substituting F(P,P,3,1) in this same formula gives the result 0,0,2,1 as P takes the values 0,1,2,3, which is the same result as U10(P). If this formula F(P1,P2,P3,P4) can thus simulate all 256 Unary Functors it is called a Universal Decision Element (UDE). The question is: how many of these Universal Decision Element formulae are there? One way to find out would be to test all possible formulae and see if each can simulate all 256 Unary Functors. The trouble is there are rather a lot of such formulae: Each formula F(P1,P2,P3,P4)
has 256 lines (we will call the lines "entry points") in its truth table:
Now, the result of line 1 could be 0, 1, 2 or 3, so the first line in the truth table could be:
Since each of the 256 results in the truth table can take the value 0,1,2 or 3, the number of possible truth tables is 4x4x4... 256 times. I.E. there are 4256 F(P1,P2,P3,P4) possible truth tables. That is a huge number - more atoms than there are in the universe - and testing each one to see if it is a UDE would take for ever: the calculations would still be running long after the end of the universe. So a faster method is required. Suppose, for a given F(P1,P2,P3,P4) formula we substitute 0,0,0,P in place of
P1,P2,P3 and P4.
This substitution uses entry points 1,2,3 and 4 in the truth table:
as P takes the values 0,1,2,3, F(0,0,0,P) becomes F(0,0,0,0), F(0,0,0,1), F(0,0,0,2), F(0,0,0,3).
Further, suppose that this substitution gives the result 1,3,2,0 for values 0,1,2,3 of P.
(Which, by the way, is the same result as Unary Functor number 120.)
The first 4 of the 256 lines in the truth table for this particular formula
F(P1,P2,P3,P4) would be:
Clearly, every substitution will give the same result as some Unary Functor or other, but for the formula to qualify as a Universal Decision Element (UDE) each of the 256 Unary Functors must be simulated by at least one of the substitutions. However, there are 369 possible substitutions of 0,1,2,3,P in F(P1,P2,P3,P4) such that there is always at least one P, e.g. F(0,0,0,P), F(P,P,3,1), F(P,P,P,P). But there are only 256 Unary Functors. So a UDE will simulate some of the Unary Functors with more than one substitution. For illustration:
Now, in the above illustration, Unary Functor 3 is simulated by substitution number 1 which is F(0,0,0,P). [* See Numbering.]
This substitution uses entry points 1,2,3 and 4 in the truth table. I.E the first 4 lines in the truth table
for this particular UDE are:
If we now mark off all the entry points that are used by Unary Functors that are simulated by only one substitution, and we strike these Unary Functors from the list of Unary Functors, we would be left with a list of Unary Functors which are simulated by more than one substitution, and the list of entry points showing which has been used by Unary Functors that are simulated by only one substitution. The remaining Unary Functors are simulated by two or more substitutions. Suppose we now simulate these remaining Unary Functors by choosing, wherever possible, substitutions that only use entry points that have already been used by the Unary Functors that were simulated by only one substitution. When we have thus judiciously chosen a substitution for all of the 256 Unary Functors it could be that some entry points have not been used at all. And indeed this turns out to be the case. So let us suppose that for a particular formula F(P1,P2,P3,P4)
we can simulate all the Unary Functors without using entry point 1.
We can therefore put any value we like in entry point 1 and the resulting 3 additional formulae will all still be UDEs:
However, we can now take each of the 3 new formulae and start the process again, calculating which Unary Functor each substitution simulates. We know that all 3 of these new formulae can simulate all 256 Unary Functors, but let's say that one of the new formulae can do so using entry point 1 but leaving entry points 8 and 174 unused. That means we can now change the values at those two entry points in the new formula which will yield a further 16 formulae (one of which is the one we started with). Clearly, by repeating the above process we can generate more and more new UDEs. Though it's a little more complicated than the above would suggested. Suppose Unary Functor 1 can be defined either by substitution 254 or 39. Further, suppose using substitution 254 leaves entry points 4 and 163 unused, and using substitution 39 leaves entry point 80 unused. Choosing to use substitution 254 means we can generate 16 UDEs by varying the values at entry points 4 and 163, and choosing substitution 39 means we can assign any of the values 0,1,2,3 to entry point 80. So that's 20 new UDEs in all - though two of these will be the formula we started with. And of course it could well be that there are several Unary Functors each of which can be simulated by several substitutions.
This implies many permutations of substitutions are possible to simulate those Unary Functors,
each permutation potentially delivering a set of unused entry points.
ProgramTo find all the UDEs in 4-valued logic one could take the following approach: Generate as many UDEs as possible from the first UDE, generate all possible UDEs from those, compare to those already generated and store any that are new, and so on until every UDE has been examined. This approach, although simple, is very time consuming. Some UDEs generate over 200,000 new UDEs and comparing them to those already generated to eliminate duplicates takes a long time. If, say 10,000,000 UDEs each generated an average of 100,000 new UDEs, that's 10,000,000 x 100,000 x 5,000,000 (average number already stored) compares: 5 x 1018 compares of 256 digit numbers. A bit too much for a laptop. The search for duplicates could be speeded by sorting the UDEs. However, since the above paragraph was initially written it has become clear that the number of UDEs is measured in quintillions, so even storing them would be impractical on a laptop. Instead, our program analyses the starting UDE and determines the sets of unused entry points it yields. Each of these UDE/unused-entry-point sets is stored. Then each stored UDE/unused-entry-point set is analysed to produce more UDE/unused-entry-point sets, each time comparing new UDE/unused-entry-point sets to those already stored to avoid storing duplicates. One further wrinkle: a given formula F(P1,P2,P3,P4) will usually produce several sets of unused entry points, eg:
But the UDEs produced from set 4, which only contains entry point 172, will also be produced from set 2 (80, 172, 202). So the set consisting just of entry point 172 can be ignored. Similarly set 1 (80, 215) is a subset of set 3 (80, 94, 215). So only sets (80, 172, 202) and (80, 94, 215) need to be stored. I.E. for any given starting UDE we ignore subsets of unused entry points. The Process UDE/unused-entry-point sets are read from file into an in-memory array. [** See Initialisation.] Each set is held as a set of 256 digits each having values 0,1,2 or 3, along with a list of its unused entry points. The first as yet unprocessed UDE/unused-entry-point set in the array is found. From this starting UDE/unused-entry-point set, new UDEs are generated by assigning all possible combinations of values to its unused entry points. For example, if entry points 132 and 319 are unused, we will generate 16 UDEs. (Point A) Each generated UDE is analysed in turn using the following process: Each of the 369 substitutions is examined to see which Unary Functor it makes the UDE being examined simulate.
For example, let us look at substitution F(1,P,0,P). Assigning each value of P yields:
We look up what the value of the UDE is at each of these entry points. Let us suppose that for the UDE being examined the values at these four entry points are 0,0,0,3. That corresponds to Unary Functor number 4. I.E. for this UDE, this particular substitution simulates Unary Functor number 4. By examining all 369 substitutions we build a table showing, for each Unary Functor, which substitution(s) simulate it. (We then check that all 256 Unary Functors have at least one substitution, i.e. that this UDE is indeed a UDE. This MUST be the case if the program is working properly - this was a useful check during program development.) The table of Unary Functors and substitutions is examined. For Unary Functors that have only one substitution, the entry points used by its substitution are marked as used, and those Unary Functors are marked as defined. Next, each of the Unary Functors which have more than one substitution is checked to see if any of its substitutions use only entry points that have already been used. If so, those Unary Functors are also marked as defined. For each Unary Functor that is still undefined, all of its substitutions are examined to see if they all use one of the as yet unused entry points. If they do, clearly that entry point will have to be used, so it is marked as used. The step described in the previous paragraph is then repeated to see if any of the as yet undefined Unary Functors can now be defined using the enlarged list of used entry points. If so, they are marked as defined. (Performing this paragraph's action before the action of the previous paragraph would avoid repeating the previous paragraph's step, but that way actually requires more calculations and runs slower: many more UFs would have to be examined in this step.) We are now left with a number of as yet undefined Unary Functors and a list of as yet unused entry points. For example. Let us suppose that the process above has defined all but three Unary Functors, 27, 34 and 217, and that they could be defined by the following substitutions: UF Substitutions
These 3 last Unary Functors could be defined using substitutions 2, 67 and 15; or 2, 67 and 34, for example. Clearly, there are 24 (3x4x2) ways these last Unary Functors can be defined. Each permutation of substitutions is examined to see which of the as yet unused entry points it would use. If, after defining these last few Unary Functors with one of the permutations, there are still some entry points unused we have found a UDE/unused-entry-point set. So say, in our example, the first of the 24 permutations leaves entry points 57 and 255 unused. This UDE/unused-entry-point set is compared to sets previously found and added to the in-memory array if it is not already there and it is not a subset of one already there. The process is reapeated for each of the (in our example 24) permutations of substitutions. We then return to Point A above to generate the next UDE from our starting UDE/unused-entry-point set. When all (16 in our example) UDEs generated from the starting UDE/unused-entry-point set has been examined we return to the paragraph just above Point A where the next as yet unprocessed UDE/unused-entry-point set is read from the in-memory array. After processing a certan number (set by a parameter) of UDE/unused-entry-point sets, the in-memory array is "subsetted": Each UDE/unused-entry-point set that has been added to the array since the last subsetting is checked against pre-existing entries to see if any pre-existing set is a subset of the new set. If so, it is deleted from the array. The in-memory array is then written to file: UDE/unused-entry-point sets with the most unused EPs are written first. At the start of the next loop, the file is read into the in-memory array and the first as-yet-unprocessed UDE/unused-entry-point set from the array will be processed. In this way, UDE/unused-entry-point sets with the highest number of unused EPs will be processed first. Writing to the file every so often also provides a checkpoint restart capability. Eventually, when all the UDE/unused-entry-point sets on the file have been processed, a calculation is made of how many
UDEs these stored UDE/unused-entry-point sets would generate.
[*Numbering: The numbering of entry points, unary functors and substitutions is arbitrary. We have chosen entry point 0000 to be number 1, unary functor 0000 to be number 1 and substitution 000P to be number 1.] [**Initialisation: The process was initialised by using an initial known UDE supplied by J.Loader. It was J.Loader
who originally devised the method of discovering UDEs described in this paper.]
Outcome This paragraph should be all about the results produced by the programs.
However, at the moment it is looking as if the number of UDE/unused-entry-point sets (let alone the number of UDEs)
is far too vast to be discoverable on a laptop.
Notes on results so farA UDE/unused-entry-point set with 6 unused entry points will produce 46 i.e. 4096 UDEs. Each of these 4096 UDEs may generate many sets of unused entry points, usually a few thousand though in some cases rather more. One particular UDE/unused-entry-point set, which had 6 unused entry points, produced over 63 million permutations of substitutions. Most of these were duplicates or subsets amongst themselves or duplicates of UDE/unused-entry-point sets already generated, but it becomes clear that a lot of processing power is required to complete the process. And 63 million was then surpassed by a UDE/unused-entry-point set (with 7 unused entry points and thus 16K UDEs) that produced over 278 million permutations of substitutions amongst those 16K UDEs. And while UDE/unused-entry-point sets typically have up to 6 unused entry points, a few have 7, 8 or even 9. And so far two have been found that have 11 unused entry points which will of course produce 4,194,304 UDEs, each of which can then generate many UDE/unused-entry-point sets. Update: And since writing the above paragraph a few days ago, UDEs with 14 unused EPs have started to appear, UDEs with 13 are plentiful, a lot have 12, and the 11s are now ten a penny. Each 14 unused EP UDE produces 268 million UDEs each of which will typically produce thousands of permutations of unused EPs which implies billions of UDE/EP sets. Impractical without a supercomputer. The hypothesis that UDE/EP sets with 13 or 14 unused EPs would be supersets of previously generated UDE/EP sets, and thus dramatically reduce the ranks of UDE/EP sets (subsets get deleted), turns out to be not the case. In the circa 100,000 UDE/EP sets produced so far, 222 of the 256 entry points have been unused on at least one occasion and it looks as if eventually all will feature as unused. The most popular entry point has so far found itself to be unused over 20,000 times - ie it is an unused entry point in around 20% of all the sets so far found. UDEs with 15 unused entry points are now turning up. Each produces 415 universal decision elements which is around a billion. So the answer to the question at the top of the page is many billions certainly. And, a few days on, 15s have become commonplace. There are now a couple of thousand UDEs with 16 unused EPs
and a few, currently 14, with 17 unused entry points. The program has been modified so that the potentially billions of
permutations of substitutions for any one UDE do not all get generated: only those that will yield a unique
set of unused EPs. Even so, some UDEs generate thousands of these. So now, to keep the volume
of data to manageable proportions, only UDE/unused-entry-point sets with 16 or 17 EPs are saved.
At the moment there is no sign that UDEs with more than 17 unused EPs are going to appear.
Change of DirectionThe original purpose, to generate all UDE/EP sets and thus to discover how many UDEs there are, would seem to be impractical given the huge numbers involved. The aim now is to analyse all UDEs with 16 and 17 unused EPs to determine if they will produce a manageable number of UDEs with 16 or 17 unused EPs, and to see whether any UDEs with more than 17 unused EPs will appear. Further update. A couple of UDEs with 18 unused entry points popped up which prompted more 18s to be produced and then a couple of UDEs with 19 unused EPs appeared. Currently there are 22 UDEs with 19 unused EPs and 479 with 18 unused EPs and over 1500 with 17. The 18s and 19s produce many 17s so the program has again been modified so that now it only stores UDEs with 18 or 19 unused EPs. What a difference a day makes. Got up this morning to find the program has had a busy night. It has now discovered
4,403 UDEs with 19 unused EPs and 159 UDEs with 20 unused EPs. And there are now 35,937 with 18.
The program has again been modified to store only UDEs with 19 or more unused EPs.
And a few hours later 21s appeared, and then a few 22s. There are now 12 UDEs with 22 unused EPs.
ConclusionOne week on from the above, UDEs with 23 unused entry points have been generated. So far 367 have been produced and there are now over 8000 with 22 unused EPs. Despite extensive - though nothing like exhaustive - analysis of these UDEs, no UDE with more than 23 unused EPs has appeared. And even in long runs examining the UDEs with 22 and 23 unused EPs, the rate of production of new UDEs with 22 or 23 unused EPs has now slowed to a trickle. Each UDE with 23 unused EPs is equivalent to 423 (64 trillion, 64 x 1012) individual UDEs. Although there are 367 UDEs with 23 unused EPs, they will produce many fewer than 367 x 423 unique UDEs. In addition, there is of course a large and unknown number of UDEs with fewer than 22 unused EPs. The conclusion, therefore, is that there are at least 64 trillion first order universal decision elements
of 4 argument places in 4-valued logic and, perhaps, none has more than 23 unused entry points.
Not so fast...A cock up on the coding front deleted many of the hard won 367 23 EP UDEs. The program was set to run again to get them back. After painfully slow production of the 23s, UDEs with 24 EPs appeared, then with 25. And now with 26 unused entry points. UDE/unused-entry-point sets with 24 or fewer entry points have become so numerous they are no longer recorded.
There are already hundreds with 26 and thousands with 25.
And finally...?UDEs with 27 unused entry points have appeared - twenty six of them. And there are now 4463 with 26 unused EPs. Despite some long runs, no UDEs with more than 27 unused entry points have appeared, though this could well be due to an inability to analyse even a meaningful fraction of the 16 quadrillion UDEs that each UDE/27-unused-entry-point set can generate. Running has now ceased. If anyone has a supercomputer and would like to run the (Fortran 95) program on it, please get in touch.
One Year Later (December 2013)An email on an unrelated subject spurred renewed interest in this program. A modification was made to the program: There were 26 UDEs with 27 unused entry points(EPs). Seventeen of the unused entry points were the same in all UDEs. Based on the hypothesis that ALL UDEs with 27 unused EPs will have these same 17 unused EPs, the program was changed to leave the values at these 17 EPs at 0 (on the basis that value in these EP does not matter if they will be unused in the resulting UDEs) and then try all combinations of values in the other 10 unused EPs. It is practical to analyse all of the (410) resulting UDEs. Unfortunately this did not yield any further UDEs with 27 unused EPs. However, it did trigger a new idea: rather than trying to run all combinations of values in unused EPs, how about assigning values 0,1,2, or 3 randomly to all of the unused EPs? And rather than trying to test the impossibly large 427 UDEs that result from running all combinations of values in the 27 unused EPs, just run a small number of these random value combinations. In the first run, for each starting UDE/unused-entry-point set, an experimental 1100 combinations of random values in the 27 unused EPs were tested. Very surprisingly it worked. In the first run the number of UDEs with 27 unused EPs went from 26 to 157, and the number of UDEs with 26 unused EPs went from the 4600 previously discovered to over 15,000. The hypothesis that 17 of the entry points will be the same in all UDEs with 27 unused EPs is disproved. Amongst the 157 UDEs with 27 unused EPs, only 5 EPs are shared by all of them. A UDE with, say, 27 unused EPs will not generate another UDE with 27 different unused EPs. Perhaps 25 will be the same and only two EPs in the new UDE will be different. This implies that the values in the 25 EPs that will be unused in the new UDE are irrelevant. Only the values in the two EPs that will not feature in the new UDE are significant. There are only 16 combinations of values for those two EPs. Assigning 50 sets of random values gives over 96% probability that all 16 combinations will be generated in those (and any other pair) of EPs. Trying to generate all combinations of values in 27 EPs would require an impossible 427 combinations to be tried. Yet a mere 50 random combinations gives good results. Indeed, runs trying 1000 random combinations which follow runs that have tried 50, yield very few additional UDEs. Experiments continue.
Conclusion?One week on from the above, experiments have shown that trying as few as 30 combinations of random values in the 27 unused EPs for each starting UDE/unused EP set, is effective at generating new UDE/unused EP sets. In fact in runs trying 30 random values, more new UDE/unused EP sets were being produced than were being analysed, making it impossible to analyse all sets at that rate of production. After another week, many more runs have been done. The rate of production of new UDE/unused-entry-point sets has slowed. Despite extensive running no UDE with more than 27 unused entry points has been found. There are now 5620 UDE/unused EP sets with 27 unused EPs, and over 390,000 with 26 unused EPs. Given the past pattern, where once a UDE with n unused EPs had been found, sets with n+1 unused EPs did not take long to emerge, one tentatively reaches for the conclusion that perhaps there are no UDEs with 28 unused entry points. If that is the case, the number of first order Universal Decision Elements of four argument places in 4-valued logic may not be very many orders of magnitude greater than 427. The 5620 UDEs with 27 unused entry points share many of those unused entry points, so the number of unique UDEs they will generate is far fewer than 5620 x 427 and nearer 3x. Although there are huge numbers of UDEs with fewer than 27 unused EPs, a large proportion of them will be duplicates of those generated by the UDEs with 27 unused EPs. One may speculate, therefore, that the number of first order Universal Decision Elements of four argument places in 4-valued logic may be in the region of 428 (which is ~7x1016). A version of the program was run which generated random truth tables by putting 0,1,2,3 in each of the 256 entry points.
Despite running millions of tries, no UDEs were found. This is perhaps not surprising as the number of possible truth
tables is 4256 and the number of these which represent UDEs only ~428.
Oh No!Having run the program several times, no more than 5620 UDEs with 27 unused entry points appeared, so running was ceased. However, going back to basics, a look at the breakdown of how many substitutions use each entry point in the truth table revealed something interesting. Four entry points are each used by 15 substitutions. The remaining 252 entry points are used either by 4, 5, 6 or 8 substitutions. (This data - the entry points used by the 369 substitutions - is constant and does not change with the UDE being examined.) One might expect that entry points used by 15 substitutions have less chance of being unused than EPs used by fewer substitutions. This is indeed the case: examining all the UDEs with 26 or more unused EPs revealed that none of the four EPs that are used by 15 substitutions was ever unused by them. As a corrollary, one might expect the entry points that are only used by 4 substitutions to be often unused by UDEs. This too proved to be the case: all of them were unused by one or more UDEs. However, there were several entry points that are used by 5 substitutions that were not unused in any of the UDEs having 26 or more unused EPs. However, looking back at UDEs with fewer that 26 unused EPs (which are no longer included in runs as there would be far too many of them) revealed some did have some of these EPs unused. This prompted an experiment. Half a dozen of these UDEs with only 23 unused EPs which had unused EPs that are used by only 5 substitutions were put as the only input to the main program. Within an hour of running they had bred not only many UDEs with 24, then 25, then 26 unused EPs, but also some with 27 unused EPs. This is a vindication of the random value in unused EP approach: it accomplished in an hour what it had taken weeks of running with the initial version of the main program. However, none of the UDEs with 26 and 27 unused EPs had the used-by-5-substitutions unused entry point that was present in the seed 23 unused EPs UDEs. But much more significantly, within 2 hours of running, UDEs with 28 unused EPs appeared. And soon thereafter UDEs with 29. The current count is 4 with 29, 398 with 28 and 17790 with 27 (versus the 5620 it had taken a week to produce above). So, having manually selected some 23-unused-EP UDEs and had such surprising results there is clearly much more work to do: to go back and find UDEs which between them have as unused, all the EPs used by 5 substitutions and see if any of them also breed new families of UDEs with high numbers of unused EPs. Having thought (not for the first time) that the end of the road had been reached, there is clearly a lot of exploring still to be done. At some point this article may be tidied up to be less of a winding tale of discovery and more a statement of final results.
Revised ApproachA revised and much faster method is now being used. The program now runs at least ten times faster for the following reasons. Previously, the program was allowed to generate
and record any UDE with the requisite number of unused EPs. So in a run recording UDEs with, say, 15 or more
unused EPs, all (non-duplicate, non-subset) UDE/EP sets with 15+ unused EPs were recorded.
But now, the file of UDE/EP sets is examined and a list is produced of EPs that are not unused by any of the UDE/EP sets***.
Newly generated UDEs are only recorded if they have one of the EPs on the list.
This greatly limits the number of UDE/EP sets that get recorded, which greatly speeds up the process by which
duplicates and subsets are eliminated (because there are so many fewer to process).
Further, the test of whether the UDE being examined has one of the EPs on the list is applied at the point in the process when EPs that must be used have been identified, but before permutations of substitutions are generated and examined. Since this is by far the most processing-intensive part of the process, eliminating it for the vast majority of contenter UDEs speeds up the processing greatly. UDEs that pass this test proceed to the permutations of substitution part of the process, and each set of unused EPs thus produced is again examined to see if it still contains at least one of the EPs from the list. Only if it does does the UDE/EP set get recorded. This increase in speed, combined with the switch to using random values in unused EPs, means the program is now something like 100 times more productive than it was originally. This means far more UDE/EP sets can be generated thereby increasing the size and diversity of the UDE/EP sets gene pool from which high-unused-EP UDEs might evolve. Indeed, the limitation now is not the speed at which UDE/EP sets can be analysed and generated. It is the size of the compiled program: an array of 700000 256 digit UDEs is about the limit for this laptop's memory. In the light of this newly evident limit, the program could no doubt be revised. The challenge is storing large numbers of UDE/EP sets and the time it takes to compare each new UDE/EP set to previously found sets to see whether it is a duplicate, subset or superset of an previous set. The process was restarted by going back to files containing previously found UDEs with as few as 15 unused entry points. The program was run until 15-unused-EPs-UDEs had been generated which between them had all but 4 of the 256 EPs unused: An examinaton of the table of which EPs were used by which substitutions revealed that EPs 1, 87, 171 and 256 were used by 15 substitutions. Because these EPs are used so frequently (none of the other 252 is used by more than 8 substitutions), they are very unlikely to ever be unused. Indeed, no UDE with 15 or more unused EPs has been found which uses any of these 4 EPs. When 15-unused-EPs UDEs had been generated amongst which all of the other 252 EPs were unused at least 40 times, the run was stopped. The program was run again, this time focusing on 16-unused-EPs UDEs until all 252 EPs were unused 40 times by them. This was repeated for UDEs with 17, 18, 19, 20, 21, then 22 unused EPs and worked well. However, for 23-unused-EP UDEs, despite several long runs, none was found with a further two EPs (170 and 187, making 6 in total) unused. For the 24-unused-EP UDEs, a further 4 (13, 49, 70 and 167) were never unused. The aim is to produce UDEs which between them have as many as possible unused EPs. In previous runs there were many EPs that were never unused, limiting the gene pool from which to generate UDEs with higher numbers of unused PEs. This would explain why an earlier run stalled at UDEs with 27 unused EPs. UDEs with n unused EPs tend to be generated from UDEs with at least n-2 unused EPs. In other words, UDEs with 16+ unused EPs will generate UDEs with 18 unused EPs, but UDEs with 15 are unlikely to. So, to keep the file of UDE/unused-EP sets down to processable numbers (up to 1,000,000), for a run to generate UDEs with 22+ unused EPs, UDE/unused-EP sets with 19 or fewer unused EPs are removed from the file. When 23+ unused EP UDEs which use all 252 EPs have been generated, UDEs with 20 unused EPs are removed from the file. Etc. As of December 17th 2013, there are 4 UDE/EP sets with 29 unused EPs, 520 with 28 and 23,819 with 27. Despite having thousands of combinations of values tried in their unused EPs, the 29s show no sign of multiplying, nor do the 28s or 27s seem able to produce more of the 29. So a new experiment is underway which starts with a single UDE which has only 1 unused EP.
The program only allows a UDE/EP set to be recorded if it has an unused EP that has been unused fewer than
(an arbitrary) 1000 times.
The program is then modified to record UDE/EP sets which have at least 2 unused EPs
but again only if the set has an unused EP that has been unused fewer than 1000 times by UDE/EP sets which have at least
2 unused EPs. Etc.
The aim is to arrive at high unused EP sets (27+) with as wide a spread of unused EPs between them as possible.
Since a UDE/n-unused-EP set is almost always generated by sets with at least n-3 unused EPs, when UDEs
with 20 unused EPs for example are being sought, UDE/EP sets with fewer than 17 unused EPs are dropped from the file. This
keeps the file down to a number that does not slow processing too much.
The EndThe program has now produced 929 UDE/EP sets with 29 unused EPs and 66632 with 28 unused EPs. The program has been modified to use 1 byte INTEGER variables to store UDEs - this (with hindsight obvious) improvement means the program can now handle up to 1.7 million UDE/EP sets. Over 1.4 million UDE/EP sets with 27 unused EPs have been found but recording of these has been restricted as the number would otherwise grow rapidly and becoming unmanageable. The UDEs with 27, 28 and 29 unused EPs had all but 33 EPs unused between them. The not-unused EPs are all used by 8 or 15 substitutions except Entry Points 10 and 249, which are used by five substitutions. After very extensive running when it appeared that no UDE with more than 29 unused EPs would appear, a single UDE with 30 unused EPs was generated. Subsequent running yielded no further UDEs with 30 unused EPs. This could be significant: previously, as soon as one UDE with a given number of unused EPs is generated, others with that number of unused EPs immediately start to be produced. Generating UDEs with 30 or more unused EPs is like looking for a needle in a haystack. It seems to depend upon producing a 'magic' UDE with, say, 28 unused EPs which has the ability to generate one with 30. And of course producing that 'magic' UDE with 28 unused EPs relies upon producing one with 27 or 26 unused EPs that can produce it. The UDE/EP sets that have been generated and stored on the file have been fully milked: they no longer produce new sets with 28 or more unused EPs. So further progress relies upon producing additional sets with 27 unused EPs. However, the program is already pretty much at the limit of the number of UDE/EP sets it can handle and the number of UDE/EP sets with 27 unused EP that could be generated would appear to be enormous: analysing 1000 UDE/EP sets with 27 unused EPs produces well over 1000 new ones and the rate of production shows no sign of slowing. Running has now ceased.
February 2014A solution to the running out of space problem has been found. Previously, UDE/EP sets were held in memory both as a 256 one digit array and as a 256 character field. In addition, a list of unused EPs was held for each. About 570 bytes in all for each UDE/EP. The program has now been changed to hold each UDE/EP set compressed into 20 four byte integers, reducing the memory required for each UDE/EP set to 80 bytes. Slightly more processing is required but it does not slow the program too much. However it does mean that several million sets can now he handled, though processing gets progressively lower as numbers increase. The file size on disk has also reduced, by over 40%, saving some read/write time. The program is now being run to look for UDE/EP sets with 27 or more unused EPs. As the gene pool of the 27s is no longer restricted it will be interesting to see how many 27s will now be generated and whether any of them will generate significant numbers of new sets with 28 or more unused EPs. Despite the extra capacity, no UDEs with 31 unused EPs have been found. There are now 7 with 30 unused EPs, 2,132 with 29,
162,118 with 28 and 3,682,898 with 27. The number of UDEs with 27 unused EPs being produced shows no sign of slowing.
May 9th 2012 - February 2014 (on and off) |
|