Most algorithms are outside the scope of Computer Science.
They are also outside the scope of any other scientific or engineering field. And that will never be fixed, no matter what new theories are developed. This outside-ness is instead an observation about the nature of rational understanding and algorithms themselves.
First let me make a bold claim without support: computer science, as a There appears no agreement as to which branch CS belongs, but it seems to be generally accepted that it lies near these three. mathematical, scientific, or engineering discipline, is concerned with understanding. If we cannot provide understanding for a particular artifact, it is not yet in the domain of science or engineering. It may be an interesting element for further study in an effort to bring it into a scientific discipline, but until understanding is present it is not part of that discipline.
The above claim is fairly important. If you don’t accept it, quit now.
In the following I will depend strongly on the meaning of the word “understanding”, which I will not define formally. Sorry. Instead I will assume that each reader has some idea of what understanding means and give a number of informal statements to support that idea.
When someone understands something, in English we say she has “wrapped her mind around” it or “comprehends” it. Both phrases seem to imply she has been able to fit the entire thing inside her mind at one time. And this is not the same as memorization: the mere storage of material within the brain is not sufficient for comprehension.
There appears to be two ways to understand something, and only two ways (as far as I can tell) in rational thought. It may surprise my reader to discover that, while I fancy myself a decent logician and mathematician, I don’t actually like rational thought much. However, this is hardly the place to go into my personal metaphysics… One way is to internalize a concept, make it an atomic element of thought: I think most people internalize the idea of counting numbers. The other way is to create a mental model of the idea that can fit inside the mind: I think that those people who comprehend complex numbers understand them via this kind of mental model. For the most part, science and engineering fields are striving for this second type of understanding. They achieve it by applying abstractions.
Abstraction is a technique by which a set of ideas too large to fit into one’s mind is augmented by two smaller ideas. I am intentionally not defining “smaller” or “simpler” here. I will give some thoughts on these terms later on in this post. One smaller idea is a simpler model: instead of a myriad individual air molecules, we speak of “a gas”. The other smaller idea is a mapping between the simple model and the large one.
A successful abstraction is one where
There are plenty of bad abstractions which fail in any or all of the above criterion. Modeling the air as some nitrogen molecules co-located with some oxygen molecules fails to simplify things enough for comprehension. Modeling an algorithm as a binary executable is a good abstraction for executing the algorithm, but a bad abstraction for understanding anything else about it. Modeling an algorithm as a magical truth-teller is bad because it provides no tools to verify that the abstraction is correct.
Now we come to my first substantive proposal. Abstractions are compression of conceptual size.
Conceptual size is hard to define, but roughly means the largest number of thoughts needed simultaneously as you come to understand a system.
Here comes the algorithms stuff…. For the non-CS people, a dataflow network is like a bunch of paper-pushers. When a person (node) receives a piece of paper (data) she writes on it (computes) and then may send one or more pieces of paper to other people (edges). It’s composable if instead of people we have departments, where each department is itself a dataflow network. Consider a composable system, where processing nodes in a dataflow network can be grouped into higher-level abstractions. The conceptual size of such a system is something like the maximum of
I assert, without example, that a similar model of conceptual size can be applied to any type of abstraction. I do this without example because I cannot even imagine trying to delineate every possible abstraction and propose a size model for each. If any of my readers think a particular abstraction does not admit a size estimate I would be interested to hear what that abstraction is.
Given any fixed set of abstraction tools, each given system has a minimal abstraction size. A well-known example of this is minimal boolean circuits, which are the minimal size of boolean functions under the abstraction of logic gates and wires.
The above statement is almost vacuously true, since it allows the minimal size of every single system to be 1. Hence, I make the following stronger statement:
Lemma: Given any fixed size x, there are systems that have a minimal conceptual size greater than x.
I’ll offer three hand-wavy supports for this lemma.
First, consider the innate notion that some ideas are more complicated than other ideas. There doesn’t seem to be any reason to believe that there is a “most complicated” idea.
Second, let me point out the prevalence of fundamental trade-off laws. For example, in selecting the nodes to divide a composable system into I am forced to make a trade off between the number of nodes I pick and the complexity of the information on each edge between the nodes. There’s no free lunch: I can’t make a clean separation into fewer nodes than the particular system allows.
Third, for any given abstraction set you can construct hard-to-abstract systems by avoiding the kinds of patterns in systems they are designed to exploit. Just take the parts of the abstraction and stick millions of them together randomly. If the abstractions handle statistical qualities of random composition then reject combinations that would exhibit those particular qualities.
I almost decided not to include this statement, but for completeness here is my second lemma:
Lemma: For each mind, there is some (fuzzy) capacity, beyond which systems with larger size cannot be understood. They might be memorized, simulated, etc., but not understood.
I am personally fascinated by the question, how fast does a mind expand? Can a 60-year-old comprehend concepts twice as difficult as a 30-year-old can comprehend? This, however, is of no consequence to the main thrust of my argument. That minds are limited should come as no surprise; even if they grow throughout life, life is finite and thus so are they. A subtler point is that it is much easier to simulate a system than it is to understand it. This is a corollary of the Church-Turing Thesis, which expressed how to simulate any arbitrary process but did not thereby bestow understanding of every single process.
Postulate: Algorithms whose minimal size is larger than any mind are not in the realm of science/engineering. In particular, they are not in the scope computer science. Most algorithms will always be larger than any mind.
There is an important assumption incorporated into the above postulate, which is that adding more minds does not help the problem. This is a matter of definition as much as observation: if neither you nor I understand a system, what does it mean for us “as a team” to understand it? We may be able to make correct statements about it, but we will not be able to understand why those statements are correct.
Note also that adding new abstractions won’t make this go away. Pigeon-hole principle: Any compression algorithm is either lossy, in that it cannot distinguish between meaningfully different inputs, or it makes at least as many inputs larger as it makes smaller. This may be defended by the pigeon-hole principle: since a set of abstractions is means of reducing conceptual size, it is a compression algorithm and must make some ideas conceptually larger to make others smaller.
The final part of the postulate states that most algorithms will always be larger than any mind. This follows from the observation that there more large things than small things. It does not assert that any one particular algorithm will forever defy understanding; rather, it states that no set of abstractions will be able to reduce the overall number of non-understandable algorithms.
Allow me to re-state the flow of the preceding portions of this document to facilitate understanding:
As I see it, there is one important open question which will decide if the above postulate is practically important or of only philosophical interest. That question is this: I considered phrasing this question, “Are there Mystery Solutions?” which has a certain pizazz, but that isn’t really the most important question.
Do human-defined problems ever have only larger-than-mind-sized solutions?
I will try to look at some of the possible impacts of different answers to this question.
The cleanest answer would be that no, all human-defined problems that have any algorithmic solution have at least one human-sized algorithmic solution. I say this is cleanest because it means we’ll never need to consider mystery solutions. Techniques for designing understandable solutions will be sufficient for any problem we care to solve.
Within the clean universe we might have two cases: in one, call it the “very-clean universe”, all solutions to human-sized problems are human-sized; in the other “clean-enough universe” there are also conceptually-big solutions to conceptually-small problems. This distinction is also at least slightly practical: in the very-clean universe, generating algorithms randomly will be guaranteed to provide only understandable solutions.
The least favorable answer from an engineering perspective would be yes, some human-defined problems may only be solved by algorithms too large to be understood. This might be true in several levels.
Classical computability theory tells us there are some questions that can never ever be answered by any algorithm. Most of these are encodings of various paradoxes: “Algorithm X: If algorithm X has property Y, do something that violates property Y. Otherwise, do something that satisfies property Y.” X creates a paradox, which means checking to see if an algorithm has property Y must be impossible. If computability is frustrating, then there is also a class of problems that humans can define for which there are no algorithmic solutions humans can understand. This seems like a highly unlikely scenario, since almost any question we care to ask is either classically undecidable or can be resolved by some kind of guess-and-check.
Computability theory contains a marvelous result known as the polynomial hierarchy. It splits problems into various categories (P, NP, and NP-complete are the best known) and states that it there is an efficient solutions to any problem in certain categories then efficient solutions to every problem in every category must also exist. Most everyone believes these efficient solutions do not exist, but no one has yet proven that result.
I would consider complexity theory to be a frustrating field if it turned out that these efficient solutions exist only in the form of mind-boggling-complicated algorithms. I picture myself sitting at a conference where some researchers present a binary that solves SAT in quintic time but, when asked how, they simply state “we have no idea how. It just does.” Once you had that program you could use it to generate a proof of its own correctness (which could be verified by algorithms we do understand) and still come away with no idea how it works. I really hope that never happens.
The last case I want to consider is the “yes, but only in a small way” case. Maybe there’s a problem where the best human-sized solution is O(n2.6) but there’s a boggling solution that’s only O(n2.5). Or maybe it’s just in the constant term and not in the complexity class at all. Either way, having to choose between an algorithm you can understand and one that is fast is an annoying trade-off. However, it is one people get used to making when they use library code they don’t understand and it would not significantly impact the bulk of computing.
Looking for comments…