Does evolution lead to greater complexity? It is obvious that it can, but it would be erroneous to believe that there is a general trend in evolution toward greater complexity. In fact evolution also leads to greater simplicity.
Genetic variation is generated through essentially random processes. Thus the generation of novel genotypes should not be biased toward either greater or lesser complexity. Natural selection could very well be biased, however, there are abundant examples of selection leading to less complexity. Parasitic digital organisms are good examples.
In the organic world, many kinds of parasites have evolved into relatively simple forms, as they rely on their host for certain services. For example, gut parasites do not require a digestive system, and have evolved very simple body plans. The eyes of some cave dwelling animals have evolved into rudimentary non-functional structures. Viruses must have arisen from renegade DNA of cellular organisms, perhaps from transposons. Thus viruses must be much simpler than their ancestors, having become metabolic parasites at the molecular level.
Probably the best way to view the issue is to note that evolution is always pushing the boundaries, in all directions, of any measure. If we look at complexity of organisms over the history of life on Earth, we clearly see a large increase over time. However, this does not necessarily arise from an inherent directionality. It may also arise from the fact that the original organisms were extremely simple, thus any moves in the direction of greater complexity are readily noted. Meanwhile, later evolutions in the direction of less complexity do not push the envelope of pre-existing complexity levels, and are easily lost amidst the background of pre-existing simpler organisms. Because the original organisms were so extremely simple, only evolutions to greater complexity push the envelope of life, and are readily noted (the origin of viruses may be a counter-example).
This study cited some examples of the evolution of more complex algorithms. These algorithms achieve high levels of optimization through a technique called ``unrolling the loop''. In the ancestral algorithm of instruction set four, the ``work'' part of the copy loop consists of only two instructions: dec and movii. Therefore the unrolling of this loop through the duplication of these two instructions would seem to be not too evolutionarily challenging.
However, in the ancestral algorithm of instruction set one, the ``work'' part of the copy loop consists of four instructions: movii, dec_c, inc_a and inc_b. Due to other circumstances that occurred in the course of evolution, this set of work instructions became slightly more complex, requiring two instances of dec_c. Thus, the ``work'' part of the evolving copy loop requires the proper combination and order of five instructions. Yet the organism 0072etq shows this set of instructions repeated three times (with varying ordering, indicating that the unrolling did not occur through an actual replication of the complete sequence).
These algorithms are substantially more intricate than the unevolved ones written by the author. The astonishing improbability of these complex orderings of instructions is testimony to the ability of evolution through natural selection to build complexity.