Abstract Complexity

The power of mathematics comes from it's continuous aspiration for abstraction. We've explored complexity, and different complexity measurements such as space and time. However, there is a more fundamental question - a more abstract question. What does Complexity really mean? What do all the various measures have in common? This is an aspiration to construct a definition of complexity with the rigour of axioms.

Manuel Blum, in the late 70's explored an abstraction of complexity in his Thesis. He formulated two very intuitive axioms. We state these in the language of partial recursive functions, and explain them later. Let $\Phi_j(i)$ be the function which computes program $j$, and let $C(j,i)$ be some complexity measure.

1. $C(j,i)$ is defined $\iff$ $\Phi_j(i)$ is defined.
2. The predicate $C(j,i) \leq y \in \mathbb{Z}$ is recursive and $false$ when $C(j,i)$ is undefined.

Now, this might sound like a whole lot of garbage. But in actual fact, the axioms are quite simple. The first says that we can only measure the complexity $C$ if and only if the program halts. So, we can only compute the elapsed time iff the machine halts, or count the number of blocks used by the program iff the program halts.

You might argue that even though a program might never halt, we can actually count the number of squares used by it, say. However, we can't actually know how many squares it used until it halts - since it may use $x$ squares now, but soon after use $x + 1$ squares. We just can't get an upper bound. Besides, this is abstract complexity, it has to relate to all complexity measures. We might be able to get an approximate upper bound on space, but how about time?

The second axiom says that we can ask the question is $C(j,i)$ less than some number $y$. This is a decision problem. Now, this decision program can only be answered (decided) properly if the machine halts.

These axioms, albeit intuitive and simple, give rise to rather obscure and unexpected results. To name a few: The Gap Theorem and The Speed Up Theorem. This material is interesting stuff. If this read has been inspiring enough, I leave it up to you, the reader, to do a few of the questions in the next section, and move on to delve deeper into Complexity by following up with the referred materials.